# Importing packages
import numpy as np
import pandas as pd
import re
import MySQLdb

# Display settings
pd.options.display.max_rows = 6

# Server connection to MySQL:
conn = MySQLdb.connect(host= "localhost",
                  user="yourusername",
                  passwd="yourpassword",
                  db="bdodae_new")

x = conn.cursor()

# Importing SQL data
node = pd.read_sql("SELECT * FROM node;", con = conn)

# Create connection/adjacency matrix weighted with CP costs
cp_connection_matrix = pd.DataFrame(np.zeros((len(node["name"]), len(node["name"]))), index = node["name"], columns = node["name"])

for x, name in zip(node["connections"], node["name"]):
    connections = re.split(", ", x)
    for connected_nodes in connections:
        # Edges going into cities have weight 0 and thus disappear from our graph, but we don't want this to happen
        # So we will instead set their weights to a very small value
        if (node[node["name"] == connected_nodes]["cp"].values[0] == 0):
            cp_connection_matrix.at[name, connected_nodes] = 0.000000001
        else:
            cp_connection_matrix.at[name, connected_nodes] = node[node["name"] == connected_nodes]["cp"].values[0]

# Import networkx
import networkx as nx

# Create graph
G = nx.from_numpy_matrix(np.matrix(cp_connection_matrix), create_using = nx.DiGraph())
# Add node attributes
node_attributes = node[["name", "cp", "area", "type"]].to_dict('index')
nx.set_node_attributes(G, node_attributes)

# Subnode information for subnode attributes and edges
node_subnode = pd.read_sql(
    """
    SELECT node.name, subnode.name AS subnode_name, subnode.cp AS subnode_cp, base_workload, current_workload
    FROM node JOIN subnode ON node.node_id = subnode.node_id;
    """, con = conn)

# Get node ID given a single node's name
def get_nx_node_id(name):
    return([x for x,y in G.nodes(data=True) if y["name"] == name][0])

# Add subnodes to node graph G
for i in range(node_subnode.shape[0]):
    G.add_node(i+1000, name = node_subnode.loc[i]["subnode_name"], cp = node_subnode.loc[i]["subnode_cp"],
               base_workload = node_subnode.loc[i]["base_workload"], current_workload = node_subnode.loc[i]["current_workload"])
    G.add_edge(get_nx_node_id(node_subnode.loc[i]["name"]), i+1000, weight = node_subnode.loc[i]["subnode_cp"])

# Get the total value of each subnode
subnode_values = pd.read_sql("""
SELECT item_yield.node_name, item_price.subnode_id, item_yield.subnode_name, item_yield.cp,
    SUM(item_price.user_average * item_yield.amount) AS subnode_value_user,
    SUM(item_price.recent_value * item_yield.amount) AS subnode_value_recent,
    SUM(item_price.vendor_sell * item_yield.amount) AS subnode_value_vendor
FROM
    (SELECT subnode_item.subnode_id, item.name, prices.*
    FROM subnode_item JOIN item ON subnode_item.item_id = item.item_id
      JOIN prices ON item.item_id = prices.item_id
    ORDER BY subnode_item.subnode_id, item.item_id) AS item_price
    JOIN
    (SELECT subnode.subnode_id, item.item_id, item.name, yield.amount, subnode.name AS subnode_name, subnode.cp, node.name AS node_name
    FROM subnode JOIN yield ON subnode.subnode_id = yield.subnode_id
      JOIN item ON yield.item_id = item.item_id
      JOIN node ON subnode.node_id = node.node_id
    ORDER BY subnode.subnode_id, item.item_id) AS item_yield
    ON item_price.subnode_id = item_yield.subnode_id
        AND item_price.item_id = item_yield.item_id
        AND item_price.name = item_yield.name
GROUP BY item_price.subnode_id
ORDER BY item_price.subnode_id
""", con = conn)

# Add per CP values
subnode_values["subnode_value_user_per_cp"] = subnode_values["subnode_value_user"] / subnode_values["cp"]
subnode_values["subnode_value_recent_per_cp"] = subnode_values["subnode_value_recent"] / subnode_values["cp"]

# Add subnode values to node graph G
for i in range(subnode_values.shape[0]):
    nx.set_node_attributes(G, {i+1000: {"subnode_value_user": subnode_values.loc[i]["subnode_value_user"],
                                        "subnode_value_recent": subnode_values.loc[i]["subnode_value_recent"],
                                        "subnode_value_vendor": subnode_values.loc[i]["subnode_value_vendor"]}})
    
# Adding subnode ranks based on their value per CP
subnode_values["value_rank"] = subnode_values["subnode_value_user_per_cp"].rank(ascending = False)
subnode_values["recent_rank"] = subnode_values["subnode_value_recent_per_cp"].rank(ascending = False)    
    
    
# Add subnode values to node graph G
for i in range(subnode_values.shape[0]):
    nx.set_node_attributes(G, {i+1000: {"subnode_value_user": subnode_values.loc[i]["subnode_value_user"],
                                        "subnode_value_recent": subnode_values.loc[i]["subnode_value_recent"],
                                        "subnode_value_vendor": subnode_values.loc[i]["subnode_value_vendor"]}})

### Helper functions
# Takes in list as input (use get_nx_node_id for a single node). Also only works on main nodes, no subnodes.
def get_node_id(name):
    return([node[node['name'] == x].index[0] for x in name])

def get_node_name(idx):
    return(node.iloc[idx]['name'])

# Gets total CP for a list of NODES only
def get_total_cp(idx):
    return(sum(node.iloc[idx]['cp'].values))

# This would be a simple call to a subnode_id's neighbors if I added them in the graph...
# But since I did not, we have this thing
def get_parent_node(subnode_id):
    return(get_nx_node_id(G.nodes[subnode_id]["name"].split(" - ")[0]))

def get_subnodes(node_id):
    return([x for x in list(G.neighbors(node_id)) if x >= 1000])

import itertools
def get_neighbors(path, depth = 1):   
    """
    Given a path as input, return neighbors with depth/degrees of separation to nodes in the path.
    
    Args:
        path: Any list of nodes that you call a path. In my case, it is the output of networkx's bidirectional Dijkstra.
            Ex. _, path = nx.bidirectional_dijkstra(G, get_node_id(["Calpheon"])[0], get_node_id(["Altinova"])[0])
        depth: Depth/degrees of separation for neighbors of nodes in path. Default depth = 1 because I found that the search
               area for higher depths deviates from our goal of going from start node to end node.
            Depth = 1 returns neighbors of nodes in path
            Depth = 2 returns neighbors of neighbors of nodes in path
            .
            .
            .
            Depth = n returns neighbors of nodes returned by depth n-1
        
    Returns:
        Neighbors with depth/degrees of separation to nodes in the path.
    """
    # Main path will only contain main nodes in our path
    main_path = [x for x in path if x < 1000]
    # Keep track of what neighboring nodes we have seen. Important for higher depth values where we may not choose
    # the first neighbor of a node, but its neighbor's neighbor.
    nodes_considered = []
    if depth == 0:
        return (path)
    # Note that for each depth iteration, we cut off the start and end nodes of our path
    # This is so we do not stray too far from getting to our location
    # Visually creates an elliptical search area between start and end nodes rather than a large circle
    # This does not necessarily mean that our algorithm will not go "backwards"
    for node_id in main_path[1:-1]:
        neighbors = [x for x in set(G.neighbors(node_id)).difference(path) if x < 1000]
        for neighbor in neighbors:
            nodes_considered.append(neighbor)
            
    # Remove duplicates    
    nodes_considered = list(dict.fromkeys(itertools.chain(nodes_considered))) 
    return(get_neighbors(nodes_considered, depth = depth-1))

def optimize_path(initpath = None, start = None, end = None, max_depth = 1, output = False, diagnostics = False):
    """
    Optimizes a path by maximizing value per CP.
    Turn on diagnostics (diagnostics = True) to see the algorithm in action.
    Turn on output (output = True) to see information of the final optimized path.
    
    Args:
        initpath: The path you want optimized. Recommend to use the path generated by networkx's bidirectional Dijkstra.
                  Use this if you have multiple paths you want to optimize on, otherwise specify a start and end node.
        max_depth: Maximum depth our algorithm searches through. See get_neighbors for more information on depth.
                   Recommended max_depth = 1 for the same reasons as in get_neighbors.
        output: Prints information of the final optimized path.
        Diagnostics: Prints the thought process of the algorithm.
        
    Returns:
        1. A path with the best value per CP from start to end, including searching for neighboring nodes up to max_depth.
        2. A dataframe containing information on chosen subnodes that added value to our path.
    """
    
    # If you choose to use start and end
    if (start and end) is not None:
        # Initial path is stored in "initpath", and the iterative path we build is stored in "path"
        # This is because of how I set up the get_neighbors function
        _, initpath = nx.bidirectional_dijkstra(G, get_node_id([start])[0], get_node_id([end])[0])
    elif (start is None and end is not None) or (start is not None and end is None):
        print("Error: You must specify both start and end if you are using them!")
        return ()
    
    # If you choose to use initpath
    # This is useful if you want to have multiple start and end locations. Then create initpath using combine_paths.
    if initpath is not None:
        path = initpath
    
    # Our initial path only contains nodes, so there is zero value
    path_value = 0
    # Get the total node CP cost for nodes in our initial path
    path_node_CP = get_total_cp(path)
    # We start with no subnodes in our path, so we do not have any subnode CP cost
    path_subnode_CP = 0
    # Simple division to get the path value per CP 
    path_value_per_cp = path_value / (path_node_CP + path_subnode_CP)
    # Will contain subnodes the algorithm chooses (i.e. subnodes that increase the path's value per CP)
    subnodes_chosen = []
    # Will be the dataframe for data about subnodes we have chosen
    subnodes_chosen_df = pd.DataFrame(columns = subnode_values.columns)
    # Master dataframe containing data on subnodes in our path and its neighbors
    all_subnodes_df = []

    # Diagnostics
    if diagnostics == True:
        print("Start path value: " + str(path_value))
        print("Node CP: " + str(path_node_CP) + "\tSubnode CP: " + str(path_subnode_CP) + "\tTotal CP: " + str(path_node_CP + path_subnode_CP))
        print("***********************************************************************************************")

    # Loop that gets neighbors up to a certain depth/degree of separation
    for d in range(max_depth+1):
        # Initial path thingy
        for node_id in path:
            path_subnodes_df = pd.DataFrame(columns = subnode_values.columns)
            # Get subnodes in shortest path
            for node_id in path:
                # path_subnodes_df contains all subnodes along our path
                path_subnodes_df = path_subnodes_df.append(subnode_values.loc[subnode_values["node_name"] == G.nodes[node_id]["name"]])    


        # Neighbors and their subnodes
        neighbors = get_neighbors(initpath, depth = d)
        neighbor_subnodes_df = pd.DataFrame(columns = subnode_values.columns)
        for neighbor in neighbors:
            # For higher depths, neighbors of neighbors may contain nodes in our path so we check this
            if neighbor not in path:
                # Get subnode IDs of a neighboring node
                subnode_ids = get_subnodes(neighbor)
                # Get dataframe containing all neighbors' subnode data
                for subnode_id in subnode_ids:
                    subnode_name = G.nodes[subnode_id]["name"]
                    neighbor_subnodes_df = neighbor_subnodes_df.append(subnode_values.loc[subnode_values["subnode_name"] == subnode_name])


        # Put path subnodes and neighbors' subnodes together for comparison later, drop duplicates, order by value per CP
        all_subnodes_df = pd.concat([path_subnodes_df, neighbor_subnodes_df])
        all_subnodes_df = all_subnodes_df.drop_duplicates()
        all_subnodes_df = all_subnodes_df.sort_values(by = "subnode_value_user_per_cp", ascending = False)

        
        for index, row in all_subnodes_df.iterrows():
            # I use a binary variable for not in path as opposed to is in path because I want my binary variable to have
            # value 1 (or True) when the node is not in our path and 0 (or False) when the node is in our path
            # It makes sense when you see how I use it to calculate check_value
            node_not_in_path = get_nx_node_id(row["node_name"]) not in path
            # Get the subnode ID to check if we already added it to the path
            subnode_id = get_nx_node_id(row["subnode_name"])
            # Main node CP for the corresponding subnode
            node_cp = G.nodes[get_nx_node_id(row["node_name"])]["cp"]
            # check_value is value we check, basically a modified "subnode_value_user_per_cp" column for neighbors' subnodes
            check_value = row["subnode_value_user_per_cp"] / (row["cp"] + node_cp * node_not_in_path)
            # Actually I can just use an if/else statement for the above so I might be dumb.

            # If the adjusted value per CP will improve our path value, then add both node and subnode to path
            if (check_value > path_value_per_cp and subnode_id not in subnodes_chosen):
                # If the node is not in the path already, then add it along with its CP cost
                if node_not_in_path:
                    path.append(get_nx_node_id(row["node_name"]))
                    path_node_CP += G.nodes[get_nx_node_id(row["node_name"])]["cp"]
                    # Diagnostics
                    if diagnostics == True:
                        print("Node added: " + row["node_name"])
                # Add subnode to path
                path.append(get_nx_node_id(row["subnode_name"]))
                # Update path value
                path_value += row["subnode_value_user"]
                # Add subnode CP
                path_subnode_CP += row["cp"]
                # Update path value per CP
                path_value_per_cp = path_value / (path_node_CP + path_subnode_CP)
                # Keeping track of chosen subnodes
                subnodes_chosen.append(subnode_id)
                subnodes_chosen_df = subnodes_chosen_df.append(row)
                
                # Diagnostics
                if diagnostics == True:
                    print("Subnode added: " + row["subnode_name"])
                    print("New path value: " + str(path_value))
                    print("Node CP: " + str(path_node_CP) + "\tSubnode CP: " + str(path_subnode_CP) + "\tTotal CP: " + str(path_node_CP + path_subnode_CP))
                    print("Updated path value per CP: " + str(path_value_per_cp))
                    print("_______________________________________________________________________________________________")
        
    # Now let's offload lower value subnodes
    subnodes_chosen_df = subnodes_chosen_df.sort_values(by = "subnode_value_user_per_cp", ascending = True)
    # Basically reverse iteration, going through subnodes that we have chosen to see which ones can be dropped to increase
    # our average path value per CP
    for index, row in subnodes_chosen_df.iterrows():
        if (row["subnode_value_user_per_cp"] <= path_value_per_cp):
            # Remove subnode from path
            path.remove(get_nx_node_id(row["subnode_name"]))
            # Decrease path value because subnode is no longer in path
            path_value -= row["subnode_value_user"]
            # Decrease subnode CP because subnode is no longer in path
            path_subnode_CP -= row["cp"]
            # Recalculate value per CP (it should increase if you need a sanity check)
            path_value_per_cp = path_value / (path_node_CP + path_subnode_CP)
            
            # Diagnostics
            if diagnostics == True:
                print("Subnode removed: " + row["subnode_name"])
                print("New path value: " + str(path_value))
                print("Node CP: " + str(path_node_CP) + "\tSubnode CP: " + str(path_subnode_CP) + "\tTotal CP: " + str(path_node_CP + path_subnode_CP))
                print("Updated path value per CP: " + str(path_value_per_cp))
                print("_______________________________________________________________________________________________")
                
    if output == True:
        print("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%")
        if (start and end) is not None:
            print("Start: " + start + " | End: " + end)
        print("\tNode CP cost: " + str(path_node_CP))
        print("\tSubnode CP cost: " + str(path_subnode_CP))
        print("\tTotal CP cost: " + str(path_node_CP + path_subnode_CP))
        print("\tPath value: " + str(path_value))
        print("\tPath value per CP: " + str(path_value_per_cp))
        print("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%")
    
    # Just reordering subnodes by value per CP, purely optional and up to your preference
    subnodes_chosen_df = subnodes_chosen_df.sort_values(by = "subnode_value_user_per_cp", ascending = False)
    return (path, subnodes_chosen_df)

# Demonstration of optimize_path
_, _ = optimize_path(start = "Calpheon", end = "Altinova", max_depth = 1, output = True, diagnostics = True)

def combine_paths(locations):
    """
    Can take multiple start and end location pairings and will combine all shortest paths between location pairings
    generated by networkx's bidirectional Dijkstra.
    
    Args:
        locations: Pairings of start and end locations. They should both be main nodes.
            Ex. [("Calpheon", "Altinova"), ("Calpheon", "Heidel"), ("Heidel", "Velia")]
        
    Returns:
        One master path that connects all location pairings given as input.   
    """
    master_path = []
    
    for path_location in locations:
        _, path = nx.bidirectional_dijkstra(G, get_node_id([path_location[0]])[0], get_node_id([path_location[1]])[0])
        master_path.append(path)
        
    master_path = list(dict.fromkeys(itertools.chain(*master_path)))
    
    return (master_path)

initpath = combine_paths([("Calpheon", "Altinova"), ("Calpheon", "Heidel"), ("Heidel", "Velia")])

main, _ = optimize_path(initpath, output = True, diagnostics = True)

for id_ in main:
    print(G.nodes[id_]["name"])