# Path: src/core/def_yen.py
# def k_shortest_paths(G, source, target, k=1, weight='weight'):
#     """Returns the k-shortest paths from source to target in a weighted graph flux_graph.
# 
#     Parameters
#     ----------
#     flux_graph : NetworkX graph
# 
#     source : node
#        Starting node
# 
#     target : node
#        Ending node
#        
#     k : integer, optional (default=1)
#         The number of shortest paths to find
# 
#     weight: string, optional (default='weight')
#        Edge data key corresponding to the edge weight
# 
#     Returns
#     -------
#     lengths, paths : lists
#        Returns a tuple with two lists.
#        The first list stores the length of each k-shortest path.
#        The second list stores each k-shortest path.  
# 
#     Raises
#     ------
#     NetworkXNoPath
#        If no path exists between source and target.
# 
#     Examples
#     --------
#     >>> flux_graph=nx.complete_graph(5)
#     >>> print(k_shortest_paths(flux_graph, 0, 4, 4))
#     ([1, 2, 2, 2], [[0, 4], [0, 1, 4], [0, 2, 4], [0, 3, 4]])
# 
#     Notes
#     ------
#     Edge weight attributes must be numerical and non-negative.
#     Distances are calculated as sums of weighted edges traversed.
# 
#     """
#     if source == target:
#         return ([0], [[source]]) 
#        
#     length, path = nx.single_source_dijkstra(G, source, target, weight=weight)
#     if target not in length:
#         raise nx.NetworkXNoPath("node %s not reachable from %s" % (source, target))
#         
#     lengths = [length[target]]
#     paths = [path[target]]
#     c = count()        
#     B = []                        
#     G_original = G.copy()    
#     
#     for i in range(1, k):
#         for j in range(len(paths[-1]) - 1):            
#             spur_node = paths[-1][j]
#             root_path = paths[-1][:j + 1]
#             
#             edges_removed = []
#             for c_path in paths:
#                 if len(c_path) > j and root_path == c_path[:j + 1]:
#                     u = c_path[j]
#                     v = c_path[j + 1]
#                     if G.has_edge(u, v):
#                         edge_attr = G.edge[u][v]
#                         G.remove_edge(u, v)
#                         edges_removed.append((u, v, edge_attr))
#             
#             for n in range(len(root_path) - 1):
#                 node = root_path[n]
#                 # out-edges
#                 for u, v, edge_attr in G.edges_iter(node, data=True):
#                     G.remove_edge(u, v)
#                     edges_removed.append((u, v, edge_attr))
#                 
#                 if G.is_directed():
#                     # in-edges
#                     for u, v, edge_attr in G.in_edges_iter(node, data=True):
#                         G.remove_edge(u, v)
#                         edges_removed.append((u, v, edge_attr))
#             
#             spur_path_length, spur_path = nx.single_source_dijkstra(G, spur_node, target, weight=weight)            
#             if target in spur_path and spur_path[target]:
#                 total_path = root_path[:-1] + spur_path[target]
#                 total_path_length = get_path_length(G_original, root_path, weight) + spur_path_length[target]                
#                 heappush(B, (total_path_length, next(c), total_path))
#                 
#             for e in edges_removed:
#                 u, v, edge_attr = e
#                 G.add_edge(u, v, edge_attr)
#                        
#         if B:
#             (l, _, p) = heappop(B)        
#             lengths.append(l)
#             paths.append(p)
#         else:
#             break
#     
#     return (lengths, paths)


import numpy as np
import networkx as nx
import os
from src.core.def_yen import k_shortest_paths as yen
from def_tools import *
from src.core.def_build_graph import *

    # ----------------------------------------------------------
    # hubs = species whose score is above crit_score

    hubs, iso_kept = find_hubs(score, iso, alpha, gamma)
    n_hub = len(hubs)

    species_kept = dict()
    for hub in hubs:
        species_kept[hub] = dict()        
        species_kept[hub]['by_alpha'] = True
        species_kept[hub]['by_K'] = []
        species_kept[hub]['by_beta'] = []

    if target is not None:


        for hub in hubs:
            if hub not in hub_GP.keys():
                hub_GP[hub] = {}
                hub_GP[hub]['score'] = score[hub]
                hub_GP[hub]['global_path'] = []

            # ----------------------------------------------------------
            # a global path(way), GP, is the pathway, p0, from source to hub, plus the pathway, p1, from hub to target
            # however, we should further ensure there's no cycle in GP

            pp0 = []
            if K > 1:
                dd0, pp0 = yen(flux_graph, source, hub, k=K, weight='1/flux')

# Path: src/core/def_yen.py
# def k_shortest_paths(G, source, target, k=1, weight='weight'):
#     """Returns the k-shortest paths from source to target in a weighted graph flux_graph.
# 
#     Parameters
#     ----------
#     flux_graph : NetworkX graph
# 
#     source : node
#        Starting node
# 
#     target : node
#        Ending node
#        
#     k : integer, optional (default=1)
#         The number of shortest paths to find
# 
#     weight: string, optional (default='weight')
#        Edge data key corresponding to the edge weight
# 
#     Returns
#     -------
#     lengths, paths : lists
#        Returns a tuple with two lists.
#        The first list stores the length of each k-shortest path.
#        The second list stores each k-shortest path.  
# 
#     Raises
#     ------
#     NetworkXNoPath
#        If no path exists between source and target.
# 
#     Examples
#     --------
#     >>> flux_graph=nx.complete_graph(5)
#     >>> print(k_shortest_paths(flux_graph, 0, 4, 4))
#     ([1, 2, 2, 2], [[0, 4], [0, 1, 4], [0, 2, 4], [0, 3, 4]])
# 
#     Notes
#     ------
#     Edge weight attributes must be numerical and non-negative.
#     Distances are calculated as sums of weighted edges traversed.
# 
#     """
#     if source == target:
#         return ([0], [[source]]) 
#        
#     length, path = nx.single_source_dijkstra(G, source, target, weight=weight)
#     if target not in length:
#         raise nx.NetworkXNoPath("node %s not reachable from %s" % (source, target))
#         
#     lengths = [length[target]]
#     paths = [path[target]]
#     c = count()        
#     B = []                        
#     G_original = G.copy()    
#     
#     for i in range(1, k):
#         for j in range(len(paths[-1]) - 1):            
#             spur_node = paths[-1][j]
#             root_path = paths[-1][:j + 1]
#             
#             edges_removed = []
#             for c_path in paths:
#                 if len(c_path) > j and root_path == c_path[:j + 1]:
#                     u = c_path[j]
#                     v = c_path[j + 1]
#                     if G.has_edge(u, v):
#                         edge_attr = G.edge[u][v]
#                         G.remove_edge(u, v)
#                         edges_removed.append((u, v, edge_attr))
#             
#             for n in range(len(root_path) - 1):
#                 node = root_path[n]
#                 # out-edges
#                 for u, v, edge_attr in G.edges_iter(node, data=True):
#                     G.remove_edge(u, v)
#                     edges_removed.append((u, v, edge_attr))
#                 
#                 if G.is_directed():
#                     # in-edges
#                     for u, v, edge_attr in G.in_edges_iter(node, data=True):
#                         G.remove_edge(u, v)
#                         edges_removed.append((u, v, edge_attr))
#             
#             spur_path_length, spur_path = nx.single_source_dijkstra(G, spur_node, target, weight=weight)            
#             if target in spur_path and spur_path[target]:
#                 total_path = root_path[:-1] + spur_path[target]
#                 total_path_length = get_path_length(G_original, root_path, weight) + spur_path_length[target]                
#                 heappush(B, (total_path_length, next(c), total_path))
#                 
#             for e in edges_removed:
#                 u, v, edge_attr = e
#                 G.add_edge(u, v, edge_attr)
#                        
#         if B:
#             (l, _, p) = heappop(B)        
#             lengths.append(l)
#             paths.append(p)
#         else:
#             break
#     
#     return (lengths, paths)


# Path: src/core/def_GPS.py
import numpy as np
import networkx as nx
import os
from src.core.def_yen import k_shortest_paths as yen
from def_tools import *
from src.core.def_build_graph import *


    # ----------------------------------------------------------
    # hubs = species whose score is above crit_score

    hubs, iso_kept = find_hubs(score, iso, alpha, gamma)
    n_hub = len(hubs)

    species_kept = dict()
    for hub in hubs:
        species_kept[hub] = dict()        
        species_kept[hub]['by_alpha'] = True
        species_kept[hub]['by_K'] = []
        species_kept[hub]['by_beta'] = []

    if target is not None:


        for hub in hubs:
            if hub not in hub_GP.keys():
                hub_GP[hub] = {}
                hub_GP[hub]['score'] = score[hub]
                hub_GP[hub]['global_path'] = []

            # ----------------------------------------------------------
            # a global path(way), GP, is the pathway, p0, from source to hub, plus the pathway, p1, from hub to target
            # however, we should further ensure there's no cycle in GP

            pp0 = []
            if K > 1:
                dd0, pp0 = yen(flux_graph, source, hub, k=K, weight='1/flux')

                dd1, pp1 = yen(flux_graph, hub, target, k=K, weight='1/flux')