def test_shortest_simple_paths():
    G = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted")
    paths = nx.shortest_simple_paths(G, 1, 12)
    assert_equal(next(paths), [1, 2, 3, 4, 8, 12])
    assert_equal(next(paths), [1, 5, 6, 7, 8, 12])
    assert_equal([len(path) for path in nx.shortest_simple_paths(G, 1, 12)],
                 sorted([len(path) for path in nx.all_simple_paths(G, 1, 12)]))

def test_directed_weighted_shortest_simple_path_issue2427():
    G = nx.DiGraph()
    G.add_edge('IN', 'OUT', weight=2)
    G.add_edge('IN', 'A', weight=1)
    G.add_edge('IN', 'B', weight=2)
    G.add_edge('B', 'OUT', weight=2)
    assert_equal(list(nx.shortest_simple_paths(G, 'IN', 'OUT', weight="weight")),
                 [['IN', 'OUT'], ['IN', 'B', 'OUT']])
    G = nx.DiGraph()
    G.add_edge('IN', 'OUT', weight=10)
    G.add_edge('IN', 'A', weight=1)
    G.add_edge('IN', 'B', weight=1)
    G.add_edge('B', 'OUT', weight=1)
    assert_equal(list(nx.shortest_simple_paths(G, 'IN', 'OUT', weight="weight")),
                 [['IN', 'B', 'OUT'], ['IN', 'OUT']])

def number_of_hidden_nodes(G):
    path_list = []
    
    for j in range(6):
        if(G.has_node(j)):
            if (nx.has_path(G,j,6)):
                for path in nx.shortest_simple_paths(G, j, 6):
                    path_list = np.append(path_list, (len(path)-2))
            
    for j in range(6):
        if(G.has_node(j)):
            if (nx.has_path(G,j,7)):
                for path in nx.shortest_simple_paths(G, j, 7):
                    path_list = np.append(path_list, (len(path)-2))
    
    return np.max(int(np.max(path_list)),0)

 def get_shortest_path(self, target):
     shortest_paths = list( networkx.shortest_simple_paths(self._graph, self._initial_state, target) )
     shortest_path = shortest_paths[0]
     edges = []
     for i in range(len(shortest_path)-1):
         edges.append( self.get_edge_by_from_to( shortest_path[i].get_id(),
                                                 shortest_path[i+1].get_id() ) )
     return edges

def test_weight_name():
    G = nx.cycle_graph(7)
    nx.set_edge_attributes(G, 1, 'weight')
    nx.set_edge_attributes(G, 1, 'foo')
    G.adj[1][2]['foo'] = 7
    paths = list(nx.shortest_simple_paths(G, 0, 3, weight='foo'))
    solution = [[0, 6, 5, 4, 3], [0, 1, 2, 3]]
    assert_equal(paths, solution)

def test_weight_name():
    G = nx.cycle_graph(7)
    nx.set_edge_attributes(G, "weight", 1)
    nx.set_edge_attributes(G, "foo", 1)
    G.edge[1][2]["foo"] = 7
    paths = list(nx.shortest_simple_paths(G, 0, 3, weight="foo"))
    solution = [[0, 6, 5, 4, 3], [0, 1, 2, 3]]
    assert_equal(paths, solution)

def test_weighted_shortest_simple_path():
    def cost_func(path):
        return sum(G.adj[u][v]['weight'] for (u, v) in zip(path, path[1:]))
    G = nx.complete_graph(5)
    weight = {(u, v): random.randint(1, 100) for (u, v) in G.edges()}
    nx.set_edge_attributes(G, weight, 'weight')
    cost = 0
    for path in nx.shortest_simple_paths(G, 0, 3, weight='weight'):
        this_cost = cost_func(path)
        assert_true(cost <= this_cost)
        cost = this_cost

def simple(request, graph, startNode, endNode):
    start = url_unquote(startNode)
    end = url_unquote(endNode)
    if not (graph.has_node(start) and graph.has_node(end)):
        return request.respondJson({'message': 'node not in graph'},
                                   NOT_FOUND)

    ipaths = nx.shortest_simple_paths(graph, start, end)

    data = {'paths': tuple(ipaths)}
    request.respondJson(data)

def test_Greg_Bernstein():
    g1 = nx.Graph()
    g1.add_nodes_from(["N0", "N1", "N2", "N3", "N4"])
    g1.add_edge("N4", "N1", weight=10.0, capacity=50, name="L5")
    g1.add_edge("N4", "N0", weight=7.0, capacity=40, name="L4")
    g1.add_edge("N0", "N1", weight=10.0, capacity=45, name="L1")
    g1.add_edge("N3", "N0", weight=10.0, capacity=50, name="L0")
    g1.add_edge("N2", "N3", weight=12.0, capacity=30, name="L2")
    g1.add_edge("N1", "N2", weight=15.0, capacity=42, name="L3")
    solution = [['N1', 'N0', 'N3'], ['N1', 'N2', 'N3'], ['N1', 'N4', 'N0', 'N3']]
    result = list(nx.shortest_simple_paths(g1, 'N1', 'N3', weight='weight'))
    assert_equal(result, solution)

def testshortestpath():
    G = nx.Graph()
    G.add_edges_from([('a','e'),('a','d'),('d','e'),('b','d'),('b','c'),('c','e'),('c','d'),('b','e')])
    gen = nx.shortest_simple_paths(G,'a','b')
    for n in gen:
        print n
    print G.nodes()
    print '-----'
    G1 = nx.Graph()
    G1.add_edges_from([('a', 'e'), ('a', 'd'), ('d', 'e'), ('b', 'd'), ('b', 'c'), ('c', 'e'), ('c', 'd'), ('b', 'e'),('d', 'f'),('d', 'g'),('g','f')])
    gen1 = nx.shortest_simple_paths(G1, 'a', 'b')
    for n in gen1:
        print n
    print G1.nodes()


    print '-------'
    G3=nx.read_gpickle('try.gpickle')
    for (a,b) in G3.edges():
        G3[a][b]['Fw'] = int(G3[a][b]['Fw']*10000)

    gen3=nx.shortest_simple_paths(G3,230349,542752,weight='Fw')
    for path in gen3:
        l=0
        for n1,n2 in zip(path,path[1:]):
            l += G3[n1][n2]['Fw']
        print l,path

    print '-------'

    gen3 = nx.shortest_simple_paths(G3, 230349, 542752)
    allp=[]
    for path in gen3:
        l = 0
        for n1, n2 in zip(path, path[1:]):
            l += G3[n1][n2]['Fw']
        allp.append((l,path))
    allp=sorted(allp, key=lambda x:x[0])
    for p in allp:
        print p

def test_directed_weighted_shortest_simple_path():
    def cost_func(path):
        return sum(G.edge[u][v]["weight"] for (u, v) in zip(path, path[1:]))

    G = nx.complete_graph(5)
    G = G.to_directed()
    weight = {(u, v): random.randint(1, 100) for (u, v) in G.edges()}
    nx.set_edge_attributes(G, "weight", weight)
    cost = 0
    for path in nx.shortest_simple_paths(G, 0, 3, weight="weight"):
        this_cost = cost_func(path)
        assert_true(cost <= this_cost)
        cost = this_cost

 def k_shortest_paths(self, graph, src, dst, weight='weight', k=1):
     generator = nx.shortest_simple_paths(graph, source=src,
                                          target=dst, weight=weight)
     shortest_paths = []
     try:
         for path in generator:
             if k <= 0:
                 break
             shortest_paths.append(path)
             k -= 1
         return shortest_paths
     except:
         self.logger.debug("No path between %s and %s" % (src, dst))

    def get_shortest_paths(self, device, gateway):
        """Return list of shortest paths from device to gateway.

        Each path in the list is a list containing entity IDs. The first
        element of the list will be device.getPrimaryId(), and the last will
        be gateway.getPrimaryId().
        
        * Node IDs beginning with a / are a Device.getPrimaryId()
        * Node IDs beginning with a !/ are a DeviceComponent.getPrimaryId()
        * Remaining node IDs are MAC addresses.
        
        An empty list is returned if not paths from device to gateway exist.

        """
        device_entity = self.to_entity(device)
        gateway_entity = self.to_entity(gateway)
        cache_key = (device_entity, gateway_entity)

        cached_paths = self.paths_cache.get(cache_key)
        if cached_paths is not None:
            return cached_paths

        g = self.get_graph(gateway_entity)

        # No paths if the device or gateway isn't in the gateway's graph.
        if device_entity not in g or gateway_entity not in g:
            return []

        shortest_path = None
        shortest_paths = []

        for path in shortest_simple_paths(g, device_entity, gateway_entity):
            path_len = len(path)
            if not shortest_path or path_len <= shortest_path:
                # Interested in all paths the same length as the shortest.
                shortest_path = path_len
                shortest_paths.append(path)
            else:
                # Not interested in paths longer than the shortest.
                break

        self.paths_cache.set(cache_key, shortest_paths)

        return shortest_paths

def test_shortest_simple_paths_directed():
    G = nx.cycle_graph(7, create_using=nx.DiGraph())
    paths = nx.shortest_simple_paths(G, 0, 3)
    assert_equal([path for path in paths], [[0, 1, 2, 3]])

def test_ssp_multigraph():
    G = nx.MultiGraph()
    nx.add_path(G, [1, 2, 3])
    paths = list(nx.shortest_simple_paths(G, 1, 4))

 def find_shortest_path(node1, node2, number):
     p = list(nx.shortest_simple_paths(self.graph, node1, node2, weight = 'distance'))
     return p[number], len(p)

 def k_shortest_paths(G, source, target, k, weight=None):
     return list(islice(nx.shortest_simple_paths(G, source, target, weight=weight), k))

	def k_shortest_path(self, source, target, k = 6, weight = None):
		"""weight is the key and not the actual weight value"""
		#source = fromNode.get_id()
		#target = toNode.get_id()
		paths = nx.shortest_simple_paths(self.G, source, target, weight = weight)
		return list(islice(paths, k))

def test_ssp_target_missing():
    G = nx.Graph()
    nx.add_path(G, [1, 2, 3])
    paths = list(nx.shortest_simple_paths(G, 1, 4))

def longest_path(edge_list, nodes, verbose=False,
                 skeleton_arrays=None, save_png=False, save_name=None):
    '''
    Takes the output of pre_graph and runs the shortest path algorithm.

    Parameters
    ----------

    edge_list : list
        Contains the connectivity information for the graphs.

    nodes : list
        A complete list of all of the nodes. The other nodes lists have
        been separated as they are labeled differently.

    verbose : bool, optional
        If True, enables the plotting of the graph.

    skeleton_arrays : list, optional
        List of the skeleton arrays. Required when verbose=True.

    save_png : bool, optional
        Saves the plot made in verbose mode. Disabled by default.

    save_name : str, optional
        For use when ``save_png`` is enabled.
        **MUST be specified when ``save_png`` is enabled.**

    Returns
    -------

    max_path : list
        Contains the paths corresponding to the longest lengths for
        each skeleton.

    extremum : list
        Contains the starting and ending points of max_path

    '''
    num = len(nodes)

    # Initialize lists
    max_path = []
    extremum = []
    graphs = []

    for n in range(num):
        G = nx.Graph()
        G.add_nodes_from(nodes[n])
        for i in edge_list[n]:
            G.add_edge(i[0], i[1], weight=i[2][1])
        # networkx 2.0 returns a two-element tuple. Convert to a dict first
        paths = dict(nx.shortest_path_length(G, weight='weight'))
        values = []
        node_extrema = []

        for i in paths.keys():
            j = max(paths[i].items(), key=operator.itemgetter(1))
            node_extrema.append((j[0], i))
            values.append(j[1])
        max_path_length = max(values)
        start, finish = node_extrema[values.index(max_path_length)]
        extremum.append([start, finish])

        # def get_weight(pat):
        #     return sum([G.edge[x][y]['weight'] for x, y in
        #                 zip(pat[:-1], pat[1:])])

        # for pat in nx.shortest_simple_paths(G, start, finish):
        #     if np.isclose(get_weight(pat), max_path_length) or get_weight(pat) > max_path_length:
        #         long_path = pat
        #         break

        long_path = \
            list(nx.shortest_simple_paths(G, start, finish, 'weight'))[-1]

        max_path.append(long_path)
        graphs.append(G)

        if verbose or save_png:
            if not skeleton_arrays:
                Warning("Must input skeleton arrays if verbose or save_png is"
                        " enabled. No plots will be created.")
            elif save_png and save_name is None:
                Warning("Must give a save_name when save_png is enabled. No"
                        " plots will be created.")
            else:
                # Check if skeleton_arrays is a list
                assert isinstance(skeleton_arrays, list)
                import matplotlib.pyplot as p
                # if verbose:
                #     print("Filament: %s / %s" % (n + 1, num))
                p.subplot(1, 2, 1)
                p.imshow(skeleton_arrays[n], interpolation="nearest",
                         origin="lower")

                p.subplot(1, 2, 2)
                elist = [(u, v) for (u, v, d) in G.edges(data=True)]
                pos = nx.spring_layout(G)
                nx.draw_networkx_nodes(G, pos, node_size=200)
#.........这里部分代码省略.........