def get_all_zero_edges(G, s, t, topological_dict):
    """
    Get all "zero-edges" from a graph: all the edges that if we remove them,
    the graph won't be connected anymore.
    """
    if nx.min_cut(G, s, t) != 1:
        return []
    auxiliary = nx.copy.deepcopy(G)
    zero_edges = nx.bidirectional_shortest_path(auxiliary, s, t)
    zero_edges = list(zip(zero_edges[:-1], zero_edges[1:]))

    kill_list = []
    for edge in zero_edges:

        auxiliary.remove_edge(edge[0], edge[1])

        try:
            nx.bidirectional_shortest_path(auxiliary, s, t)
            print edge
            kill_list.append(edge)
        except nx.NetworkXNoPath:
            pass
        auxiliary.add_edge(edge[0], edge[1])

    for edge in kill_list:
        zero_edges.remove(edge)
    zero_edges.sort(lambda x, y: cmp(topological_dict[x[0]], topological_dict[y[0]]))
    return zero_edges

 def test_bidirectional_shortest_path(self):
     assert_equal(nx.bidirectional_shortest_path(self.cycle,0,3),
                  [0, 1, 2, 3])
     assert_equal(nx.bidirectional_shortest_path(self.cycle,0,4),
                  [0, 6, 5, 4])
     validate_grid_path(4, 4, 1, 12, nx.bidirectional_shortest_path(self.grid,1,12))
     assert_equal(nx.bidirectional_shortest_path(self.directed_cycle,0,3),
                  [0, 1, 2, 3])

 def test_bidirectional_shortest_path(self):
     assert_equal(nx.bidirectional_shortest_path(self.cycle,0,3),
                  [0, 1, 2, 3])
     assert_equal(nx.bidirectional_shortest_path(self.cycle,0,4),
                  [0, 6, 5, 4])
     assert_equal(nx.bidirectional_shortest_path(self.grid,1,12),
                  [1, 2, 3, 4, 8, 12])
     assert_equal(nx.bidirectional_shortest_path(self.directed_cycle,0,3),
                  [0, 1, 2, 3])

def ford_fulkerson_impl(G, s, t, capacity):
    """Legacy implementation of the Edmonds-Karp algorithm"""
    if G.is_multigraph():
        raise nx.NetworkXError(
                'MultiGraph and MultiDiGraph not supported (yet).')

    if s not in G:
        raise nx.NetworkXError('node %s not in graph' % str(s))
    if t not in G:
        raise nx.NetworkXError('node %s not in graph' % str(t))
    if s == t:
        raise nx.NetworkXError('source and sink are the same node')

    auxiliary = _create_auxiliary_digraph(G, capacity=capacity)
    inf_capacity_flows = auxiliary.graph['inf_capacity_flows']

    flow_value = 0   # Initial feasible flow.

    # As long as there is an (s, t)-path in the auxiliary digraph, find
    # the shortest (with respect to the number of arcs) such path and
    # augment the flow on this path.
    while True:
        try:
            path_nodes = nx.bidirectional_shortest_path(auxiliary, s, t)
        except nx.NetworkXNoPath:
            break

        # Get the list of edges in the shortest path.
        path_edges = list(zip(path_nodes[:-1], path_nodes[1:]))

        # Find the minimum capacity of an edge in the path.
        try:
            path_capacity = min([auxiliary[u][v][capacity]
                                for u, v in path_edges
                                if capacity in auxiliary[u][v]])
        except ValueError:
            # path of infinite capacity implies no max flow
            raise nx.NetworkXUnbounded(
                    "Infinite capacity path, flow unbounded above.")

        flow_value += path_capacity

        # Augment the flow along the path.
        for u, v in path_edges:
            edge_attr = auxiliary[u][v]
            if capacity in edge_attr:
                edge_attr[capacity] -= path_capacity
                if edge_attr[capacity] == 0:
                    auxiliary.remove_edge(u, v)
            else:
                inf_capacity_flows[(u, v)] += path_capacity

            if auxiliary.has_edge(v, u):
                if capacity in auxiliary[v][u]:
                    auxiliary[v][u][capacity] += path_capacity
            else:
                auxiliary.add_edge(v, u, {capacity: path_capacity})

    auxiliary.graph['inf_capacity_flows'] = inf_capacity_flows
    return flow_value, auxiliary

def shortestPathOmd(pathToOmdFile, sourceObjectName, targetObjectName):
	'''Get the shortest path between two points on a feeder'''
	with open(pathToOmdFile) as inFile:
		tree = json.load(inFile)['tree']
	nxG = omf.feeder.treeToNxGraph(tree)
	nxG = graphValidator(pathToOmdFile, nxG)
	tracePath = nx.bidirectional_shortest_path(nxG, sourceObjectName, targetObjectName)
	return tracePath

def output_go_terms_and_levels(go_terms, go, output_file, root_id="GO:0008150"):
    """
	root_id = "GO:0008150" # BP
    """
    from networkx import bidirectional_shortest_path
    f_out = open(output_file, 'w')
    f_out.write("go level\n")
    for go_id in go_terms:
	level = len(bidirectional_shortest_path(go, go_id, root_id))
	f_out.write("%s %d\n" % (go_id, level)) 
    f_out.close()
    return

 def test_bidirectional_shortest_path_restricted(self):
     assert_equal(nx.bidirectional_shortest_path(self.cycle, 0, 3), [0, 1, 2, 3])
     assert_equal(nx.bidirectional_shortest_path(self.cycle, 0, 3, ignore_nodes=[1]), [0, 6, 5, 4, 3])
     assert_equal(nx.bidirectional_shortest_path(self.grid, 1, 12), [1, 2, 3, 4, 8, 12])
     assert_equal(nx.bidirectional_shortest_path(self.grid, 1, 12, ignore_nodes=[2]), [1, 5, 6, 10, 11, 12])
     assert_equal(nx.bidirectional_shortest_path(self.grid, 1, 12, ignore_nodes=[2, 6]), [1, 5, 9, 10, 11, 12])
     assert_equal(
         nx.bidirectional_shortest_path(self.grid, 1, 12, ignore_nodes=[2, 6], ignore_edges=[(10, 11)]),
         [1, 5, 9, 10, 14, 15, 16, 12],
     )
     assert_equal(nx.bidirectional_shortest_path(self.directed_cycle, 0, 3), [0, 1, 2, 3])
     assert_raises(nx.NetworkXNoPath, nx.bidirectional_shortest_path, self.directed_cycle, 0, 3, ignore_nodes=[1])
     assert_equal(nx.bidirectional_shortest_path(self.directed_cycle, 0, 3, ignore_edges=[(2, 1)]), [0, 1, 2, 3])
     assert_raises(
         nx.NetworkXNoPath, nx.bidirectional_shortest_path, self.directed_cycle, 0, 3, ignore_edges=[(1, 2)]
     )

def shortest_path(source, target, transfer, lines, option="dijkstra"):
    """Find shortest path, using given lines"""
    reduced_lines = dict()
    reduced_subway = nx.Graph()
    for line in transfer:
        reduced_lines[line] = lines[line]

    for l in reduced_lines.values():
        for pair in pairwise(l.route):
            dist = np.linalg.norm([pair[0].xy, pair[1].xy])
            reduced_subway.add_edge(*pair, distance=dist)

    if option == "dijkstra":
        # least distance
        return nx.bidirectional_dijkstra(reduced_subway, source, target, weight="distance")
    else:
        # least stops
        return nx.bidirectional_shortest_path(reduced_subway, source, target)

#.........这里部分代码省略.........
        If not specified, compute shortest paths using all nodes as source nodes.

    target : node, optional
        Ending node for path.
        If not specified, compute shortest paths using all nodes as target nodes.

    weight : None or string, optional (default = None)
        If None, every edge has weight/distance/cost 1.
        If a string, use this edge attribute as the edge weight.
        Any edge attribute not present defaults to 1.

    Returns
    -------
    path: list or dictionary
        All returned paths include both the source and target in the path.

        If the source and target are both specified, return a single list
        of nodes in a shortest path from the source to the target.

        If only the source is specified, return a dictionary keyed by
        targets with a list of nodes in a shortest path from the source
        to one of the targets.

        If only the target is specified, return a dictionary keyed by
        sources with a list of nodes in a shortest path from one of the
        sources to the target.

        If neither the source nor target are specified return a dictionary
        of dictionaries with path[source][target]=[list of nodes in path].

    Examples
    --------
    >>> G=nx.path_graph(5)
    >>> print(nx.shortest_path(G,source=0,target=4))
    [0, 1, 2, 3, 4]
    >>> p=nx.shortest_path(G,source=0) # target not specified
    >>> p[4]
    [0, 1, 2, 3, 4]
    >>> p=nx.shortest_path(G,target=4) # source not specified
    >>> p[0]
    [0, 1, 2, 3, 4]
    >>> p=nx.shortest_path(G) # source,target not specified
    >>> p[0][4]
    [0, 1, 2, 3, 4]

    Notes
    -----
    There may be more than one shortest path between a source and target.
    This returns only one of them.

    For digraphs this returns a shortest directed path. To find paths in the
    reverse direction first use G.reverse(copy=False) to flip the edge
    orientation.

    See Also
    --------
    all_pairs_shortest_path()
    all_pairs_dijkstra_path()
    single_source_shortest_path()
    single_source_dijkstra_path()
    """
    if source is None:
        if target is None:
            ## Find paths between all pairs.
            if weight is None:
                paths=nx.all_pairs_shortest_path(G)
            else:
                paths=nx.all_pairs_dijkstra_path(G,weight=weight)
        else:
            ## Find paths from all nodes co-accessible to the target.
            directed = G.is_directed()
            if directed:
               G.reverse(copy=False)

            if weight is None:
                paths=nx.single_source_shortest_path(G,target)
            else:
                paths=nx.single_source_dijkstra_path(G,target,weight=weight)

            # Now flip the paths so they go from a source to the target.
            for target in paths:
                paths[target] = list(reversed(paths[target]))

            if directed:
                G.reverse(copy=False)
    else:
        if target is None:
            ## Find paths to all nodes accessible from the source.
            if weight is None:
                paths=nx.single_source_shortest_path(G,source)
            else:
                paths=nx.single_source_dijkstra_path(G,source,weight=weight)
        else:
            ## Find shortest source-target path.
            if weight is None:
                paths=nx.bidirectional_shortest_path(G,source,target)
            else:
                paths=nx.dijkstra_path(G,source,target,weight)

    return paths

#.........这里部分代码省略.........
        Ending node for path.
        If not specified, compute shortest path lengths using all nodes as
        target nodes.

    weight : None or string, optional (default = None)
        If None, every edge has weight/distance/cost 1.
        If a string, use this edge attribute as the edge weight.
        Any edge attribute not present defaults to 1.

    Returns
    -------
    length: int or dictionary
        If the source and target are both specified, return the length of
        the shortest path from the source to the target.

        If only the source is specified, return a dictionary keyed by
        targets whose values are the lengths of the shortest path from the
        source to one of the targets.

        If only the target is specified, return a dictionary keyed by
        sources whose values are the lengths of the shortest path from one
        of the sources to the target.

        If neither the source nor target are specified return a dictionary
        of dictionaries with path[source][target]=L, where L is the length
        of the shortest path from source to target.

    Raises
    ------
    NetworkXNoPath
        If no path exists between source and target.

    Examples
    --------
    >>> G=nx.path_graph(5)
    >>> print(nx.shortest_path_length(G,source=0,target=4))
    4
    >>> p=nx.shortest_path_length(G,source=0) # target not specified
    >>> p[4]
    4
    >>> p=nx.shortest_path_length(G,target=4) # source not specified
    >>> p[0]
    4
    >>> p=nx.shortest_path_length(G) # source,target not specified
    >>> p[0][4]
    4

    Notes
    -----
    The length of the path is always 1 less than the number of nodes involved
    in the path since the length measures the number of edges followed.

    For digraphs this returns the shortest directed path length. To find path
    lengths in the reverse direction use G.reverse(copy=False) first to flip
    the edge orientation.

    See Also
    --------
    all_pairs_shortest_path_length()
    all_pairs_dijkstra_path_length()
    single_source_shortest_path_length()
    single_source_dijkstra_path_length()

    """
    if source is None:
        if target is None:
            ## Find paths between all pairs.
            if weight is None:
                paths=nx.all_pairs_shortest_path_length(G)
            else:
                paths=nx.all_pairs_dijkstra_path_length(G, weight=weight)
        else:
            ## Find paths from all nodes co-accessible to the target.
            directed = G.is_directed()
            if directed:
               G.reverse(copy=False)

            if weight is None:
                paths=nx.single_source_shortest_path_length(G,target)
            else:
                paths=nx.single_source_dijkstra_path_length(G,target,
                                                            weight=weight)

            if directed:
                G.reverse(copy=False)
    else:
        if target is None:
            ## Find paths to all nodes accessible from the source.
            if weight is None:
                paths=nx.single_source_shortest_path_length(G,source)
            else:
                paths=nx.single_source_dijkstra_path_length(G,source,weight=weight)
        else:
            ## Find shortest source-target path.
            if weight is None:
                p=nx.bidirectional_shortest_path(G,source,target)
                paths=len(p)-1
            else:
                paths=nx.dijkstra_path_length(G,source,target,weight)
    return paths

def ford_fulkerson(G, s, t, capacity="capacity"):
    """Find a maximum single-commodity flow using the Ford-Fulkerson
    algorithm.
    
    This algorithm uses Edmonds-Karp-Dinitz path selection rule which
    guarantees a running time of O(nm^2) for n nodes and m edges.


    Parameters
    ----------
    G : NetworkX nxgraph
        Edges of the nxgraph are expected to have an attribute called
        'capacity'. If this attribute is not present, the edge is
        considered to have infinite capacity.

    s : node
        Source node for the flow.

    t : node
        Sink node for the flow.

    capacity: string
        Edges of the nxgraph G are expected to have an attribute capacity
        that indicates how much flow the edge can support. If this
        attribute is not present, the edge is considered to have
        infinite capacity. Default value: 'capacity'.

    Returns
    -------
    flow_value : integer, float
        Value of the maximum flow, i.e., net outflow from the source.

    flow_dict : dictionary
        Dictionary of dictionaries keyed by nodes such that
        flow_dict[u][v] is the flow edge (u, v).

    Raises
    ------
    NetworkXError
        The algorithm does not support MultiGraph and MultiDiGraph. If
        the input nxgraph is an instance of one of these two classes, a
        NetworkXError is raised.

    NetworkXUnbounded
        If the nxgraph has a path of infinite capacity, the value of a
        feasible flow on the nxgraph is unbounded above and the function
        raises a NetworkXUnbounded.

    Examples
    --------
    >>> import networkx as nx
    >>> G = nx.DiGraph()
    >>> G.add_edge('x','a', capacity=3.0)
    >>> G.add_edge('x','b', capacity=1.0)
    >>> G.add_edge('a','c', capacity=3.0)
    >>> G.add_edge('b','c', capacity=5.0)
    >>> G.add_edge('b','d', capacity=4.0)
    >>> G.add_edge('d','e', capacity=2.0)
    >>> G.add_edge('c','y', capacity=2.0)
    >>> G.add_edge('e','y', capacity=3.0)
    >>> flow, F = nx.ford_fulkerson(G, 'x', 'y')
    >>> flow
    3.0
    """
    if G.is_multigraph():
        raise nx.NetworkXError("MultiGraph and MultiDiGraph not supported (yet).")

    if s not in G:
        raise nx.NetworkXError("node %s not in nxgraph" % str(s))
    if t not in G:
        raise nx.NetworkXError("node %s not in nxgraph" % str(t))

    auxiliary, inf_capacity_flows = _create_auxiliary_digraph(G, capacity=capacity)
    flow_value = 0  # Initial feasible flow.

    # As long as there is an (s, t)-path in the auxiliary digraph, find
    # the shortest (with respect to the number of arcs) such path and
    # augment the flow on this path.
    while True:
        try:
            path_nodes = nx.bidirectional_shortest_path(auxiliary, s, t)
        except nx.NetworkXNoPath:
            break

        # Get the list of edges in the shortest path.
        path_edges = list(zip(path_nodes[:-1], path_nodes[1:]))

        # Find the minimum capacity of an edge in the path.
        try:
            path_capacity = min([auxiliary[u][v][capacity] for u, v in path_edges if capacity in auxiliary[u][v]])
        except ValueError:
            # path of infinite capacity implies no max flow
            raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.")

        flow_value += path_capacity

        # Augment the flow along the path.
        for u, v in path_edges:
            edge_attr = auxiliary[u][v]
            if capacity in edge_attr:
#.........这里部分代码省略.........

def shortest_path(G,source=None,target=None,weighted=False):
    """Compute shortest paths in the graph.

    Parameters
    ----------
    G : NetworkX graph

    source : node, optional
       Starting node for path.  
       If not specified compute shortest paths for all connected node pairs.

    target : node, optional 
       Ending node for path.  
       If not specified compute shortest paths for every node reachable 
       from the source.

    weighted : bool, optional
       If True consider weighted edges when finding shortest path.

    Returns
    -------
    path: list or dictionary
        If the source and target are both specified return a single list
        of nodes in a shortest path.
        If only the source is specified return a dictionary keyed by
        targets with a list of nodes in a shortest path.
        If neither the source or target is specified return a dictionary 
        of dictionaries with path[source][target]=[list of nodes in path].

    Examples
    --------
    >>> G=nx.path_graph(5)
    >>> print nx.shortest_path(G,source=0,target=4)
    [0, 1, 2, 3, 4]
    >>> p=nx.shortest_path(G,source=0) # target not specified
    >>> p[4]
    [0, 1, 2, 3, 4]
    >>> p=nx.shortest_path(G) # source,target not specified
    >>> p[0][4]
    [0, 1, 2, 3, 4]

    Notes
    -----
    There may be more than one shortest path between a source and target.
    This returns only one of them.

    If weighted=True and the graph has no 'weight' edge attribute
    the value 1 will be used.

    For digraphs this returns a shortest directed path.  
    To find paths in the reverse direction use G.reverse(copy=False)
    first to flip the edge orientation.
    """
    if source is None:
        if target is None:
            if weighted:
                paths=nx.all_pairs_dijkstra_path(G)
            else:
                paths=nx.all_pairs_shortest_path(G)
        else:
            raise nx.NetworkXError(\
                "Target given but no source specified.")
    else: # source specified
        if target is None:
            if weighted:
                paths=nx.single_source_dijkstra_path(G,source)
            else:
                paths=nx.single_source_shortest_path(G,source)
        else:
            # shortest source-target path
            if weighted:
                paths=nx.dijkstra_path(G,source,target)
            else:
                paths=nx.bidirectional_shortest_path(G,source,target)

    return paths

def shortest_path_length(G,source=None,target=None,weighted=False):
    """Compute shortest path lengths in the graph.
    
    This function can compute the single source shortest path
    lengths by specifying only the source or all pairs shortest
    path lengths by specifying neither the source or target.

    Parameters
    ----------
    G : NetworkX graph

    source : node, optional
       Starting node for path.  
       If not specified compute shortest pats lenghts for all 
       connected node pairs.

    target : node, optional 
       Ending node for path.  
       If not specified compute shortest path lenghts for every 
       node reachable from the source.

    weighted : bool, optional
       If True consider weighted edges when finding shortest path length.

    Returns
    -------
    length : number, or container of numbers
        If the source and target are both specified return a
        single number for the shortest path.
        If only the source is specified return a dictionary keyed by
        targets with a the shortest path as keys.
        If neither the source or target is specified return a dictionary 
        of dictionaries with length[source][target]=value.

    Raises
    ------
    NetworkXError
        If no path exists between source and target.

    Examples
    --------
    >>> G=nx.path_graph(5)
    >>> print nx.shortest_path_length(G,source=0,target=4)
    4
    >>> p=nx.shortest_path_length(G,source=0) # target not specified
    >>> p[4]
    4
    >>> p=nx.shortest_path_length(G) # source,target not specified
    >>> p[0][4]
    4

    Notes
    -----
    If weighted=True and the graph has no 'weight' edge attribute
    the value 1 will be used.

    For digraphs this returns the shortest directed path.
    To find path lengths in the reverse direction use G.reverse(copy=False)
    first to flip the edge orientation.
    """
    if source is None:
        if target is None:
            if weighted:
                paths=nx.all_pairs_dijkstra_path_length(G)
            else:
                paths=nx.all_pairs_shortest_path_length(G)
        else:
            raise nx.NetworkXError(\
                "Target given but no source specified.")
    else: # source specified
        if target is None:
            if weighted:
                paths=nx.single_source_dijkstra_path_length(G,source)
            else:
                paths=nx.single_source_shortest_path_length(G,source)
        else:
            # shortest source-target path
            if weighted:
                paths=nx.dijkstra_path_length(G,source,target)
            else:
                p=nx.bidirectional_shortest_path(G,source,target)
                if p is False:
                    raise nx.NetworkXError(\
                        "No path from %s to %s."%(source,target))
                paths=len(p)-1
    return paths

def ford_fulkerson(G, s, t):
    """Find a maximum single-commodity flow using the Ford-Fulkerson
    algorithm.
    
    This algorithm uses Edmond-Karp-Dinitz path selection rule which
    guarantees a running time of O(|V||E|**2).

    Parameters
    ----------
    G : NetworkX graph
        Edges of the graph are expected to have an attribute called
        'capacity'. If this attribute is not present, the edge is
        considered to have infinite capacity.

    s : node
        Source node for the flow.

    t : node
        Sink node for the flow.

    Returns
    -------
    flowValue : integer, float
        Value of the maximum flow, i.e., net outflow from the source.

    flowGraph : NetworkX graph
        Graph with V(flowGraph) = V(G) and in which each edge has an
        attribute 'flow' which gives the flow on the edge.

    Raises
    ------
    NetworkXError
        If the graph has a path of infinite capacity, the value of a 
        feasible flow on the graph is unbounded above and the function
        raises a NetworkXError.

    Examples
    --------
    >>> import networkx as nx
    >>> G = nx.DiGraph()
    >>> G.add_edge('x','a', capacity = 3.0)
    >>> G.add_edge('x','b', capacity = 1.0)
    >>> G.add_edge('a','c', capacity = 3.0)
    >>> G.add_edge('b','c', capacity = 5.0)
    >>> G.add_edge('b','d', capacity = 4.0)
    >>> G.add_edge('d','e', capacity = 2.0)
    >>> G.add_edge('c','y', capacity = 2.0)
    >>> G.add_edge('e','y', capacity = 3.0)
    >>> flow,F=nx.ford_fulkerson(G, 'x', 'y')
    >>> flow
    3.0
    """
    
    auxiliary, infcapFlows = _create_auxiliary_digraph(G)
    flowValue = 0   # Initial feasible flow.

    # As long as there is an (s, t)-path in the auxiliary digraph, find
    # the shortest (with respect to the number of arcs) such path and
    # augment the flow on this path.
    while True:
        pathNodes = nx.bidirectional_shortest_path(auxiliary, s, t)
        if not pathNodes:
            break

        # Get the list of edges in the shortest path.
        pathEdges = []
        for i, u in enumerate(pathNodes[:-1]):
            v = pathNodes[i + 1]
            pathEdges.append((u, v, auxiliary[u][v]))

        # Find the minimum capacity of an edge in the path.
        try:
            pathCapacity = min([c['capacity']
                            for (u, v, c) in pathEdges
                            if c.has_key('capacity')])
        except ValueError: 
            # path of infinite capacity implies no max flow
            raise nx.NetworkXError(
                    "Infinite capacity path, flow unbounded above.")
        
        flowValue += pathCapacity

        # Augment the flow along the path.
        for (u, v, c) in pathEdges:
            auxEdgeAttr = auxiliary[u][v]
            if auxEdgeAttr.has_key('capacity'):
                auxEdgeAttr['capacity'] -= pathCapacity
                if auxEdgeAttr['capacity'] == 0:
                    auxiliary.remove_edge(u, v)
            else:
                infcapFlows[(u, v)] += pathCapacity

            if auxiliary.has_edge(v, u):
                if auxiliary[v][u].has_key('capacity'):
                    auxiliary[v][u]['capacity'] += pathCapacity
            else:
                auxiliary.add_edge(v, u, {'capacity': pathCapacity})
    
    flowGraph = _create_flow_graph(G, auxiliary, infcapFlows)
    return flowValue, flowGraph

#.........这里部分代码省略.........

    weight : None or string, optional (default = None)
        If None, every edge has weight/distance/cost 1.
        If a string, use this edge attribute as the edge weight.
        Any edge attribute not present defaults to 1.

    Returns
    -------
    length: int or iterator
        If the source and target are both specified, return the length of
        the shortest path from the source to the target.

        If only the source is specified, return a tuple
        (target, shortest path length) iterator, where shortest path lengths
        are the lengths of the shortest path from the source to one of the
        targets.

        If only the target is specified, return a tuple
        (source, shortest path length) iterator, where shortest path lengths
        are the lengths of the shortest path from one of the sources
        to the target.

        If neither the source nor target are specified, return a
        (source, dictionary) iterator with dictionary keyed by target and
        shortest path length as the key value.

    Raises
    ------
    NetworkXNoPath
        If no path exists between source and target.

    Examples
    --------
    >>> G = nx.path_graph(5)
    >>> nx.shortest_path_length(G, source=0, target=4)
    4
    >>> p = nx.shortest_path_length(G, source=0) # target not specified
    >>> dict(p)[4]
    4
    >>> p = nx.shortest_path_length(G, target=4) # source not specified
    >>> dict(p)[0]
    4
    >>> p = nx.shortest_path_length(G) # source,target not specified
    >>> dict(p)[0][4]
    4

    Notes
    -----
    The length of the path is always 1 less than the number of nodes involved
    in the path since the length measures the number of edges followed.

    For digraphs this returns the shortest directed path length. To find path
    lengths in the reverse direction use G.reverse(copy=False) first to flip
    the edge orientation.

    See Also
    --------
    all_pairs_shortest_path_length()
    all_pairs_dijkstra_path_length()
    single_source_shortest_path_length()
    single_source_dijkstra_path_length()

    """
    if source is None:
        if target is None:
            # Find paths between all pairs.
            if weight is None:
                paths = nx.all_pairs_shortest_path_length(G)
            else:
                paths = nx.all_pairs_dijkstra_path_length(G, weight=weight)
        else:
            # Find paths from all nodes co-accessible to the target.
            with nx.utils.reversed(G):
                if weight is None:
                    # We need to exhaust the iterator as Graph needs
                    # to be reversed.
                    path_length = nx.single_source_shortest_path_length
                    paths = list(path_length(G, target))
                else:
                    path_length = nx.single_source_dijkstra_path_length
                    paths = path_length(G, target, weight=weight)
    else:
        if source not in G:
            raise nx.NodeNotFound("Source {} not in G".format(source));

        if target is None:
            # Find paths to all nodes accessible from the source.
            if weight is None:
                paths = nx.single_source_shortest_path_length(G, source)
            else:
                paths = nx.single_source_dijkstra_path_length(G, source,
                                                              weight=weight)
        else:
            # Find shortest source-target path.
            if weight is None:
                p = nx.bidirectional_shortest_path(G, source, target)
                paths = len(p)-1
            else:
                paths = nx.dijkstra_path_length(G, source, target, weight)
    return paths

def shortest_path(G, source=None, target=None, weight=None):
    """Compute shortest paths in the graph.

    Parameters
    ----------
    G : NetworkX graph

    source : node, optional
       Starting node for path.
       If not specified compute shortest paths for all connected node pairs.

    target : node, optional
       Ending node for path.
       If not specified compute shortest paths for every node reachable
       from the source.

    weight : None or string, optional (default = None)
       If None, every edge has weight/distance/cost 1.
       If a string, use this edge attribute as the edge weight.
       Any edge attribute not present defaults to 1.

    Returns
    -------
    path: list or dictionary
        If the source and target are both specified return a single list
        of nodes in a shortest path.
        If only the source is specified return a dictionary keyed by
        targets with a list of nodes in a shortest path.
        If neither the source or target is specified return a dictionary
        of dictionaries with path[source][target]=[list of nodes in path].

    Examples
    --------
    >>> G=nx.path_graph(5)
    >>> print(nx.shortest_path(G,source=0,target=4))
    [0, 1, 2, 3, 4]
    >>> p=nx.shortest_path(G,source=0) # target not specified
    >>> p[4]
    [0, 1, 2, 3, 4]
    >>> p=nx.shortest_path(G) # source,target not specified
    >>> p[0][4]
    [0, 1, 2, 3, 4]

    Notes
    -----
    There may be more than one shortest path between a source and target.
    This returns only one of them.

    For digraphs this returns a shortest directed path.
    To find paths in the reverse direction first use G.reverse(copy=False)
    to flip the edge orientation.

    See Also
    --------
    all_pairs_shortest_path()
    all_pairs_dijkstra_path()
    single_source_shortest_path()
    single_source_dijkstra_path()
    """
    if source is None:
        if target is None:
            if weight is None:
                paths=nx.all_pairs_shortest_path(G)
            else:
                paths=nx.all_pairs_dijkstra_path(G,weight=weight)
        else:
            raise nx.NetworkXError(\
                "Target given but no source specified.")
    else: # source specified
        if target is None:
            if weight is None:
                paths=nx.single_source_shortest_path(G,source)
            else:
                paths=nx.single_source_dijkstra_path(G,source,weight=weight)
        else:
            # shortest source-target path
            if weight is None:
                paths=nx.bidirectional_shortest_path(G,source,target)
            else:
                paths=nx.dijkstra_path(G,source,target,weight)

    return paths

def shortest_path_length(G, source=None, target=None, weight=None):
    """Compute shortest path lengths in the graph.

    This function can compute the single source shortest path
    lengths by specifying only the source or all pairs shortest
    path lengths by specifying neither the source or target.

    Parameters
    ----------
    G : NetworkX graph

    source : node, optional
       Starting node for path.
       If not specified compute shortest path lengths for all
       connected node pairs.

    target : node, optional
       Ending node for path.
       If not specified compute shortest path lengths for every
       node reachable from the source.

    weight : None or string, optional (default = None)
       If None, every edge has weight/distance/cost 1.
       If a string, use this edge attribute as the edge weight.
       Any edge attribute not present defaults to 1.

    Returns
    -------
    length : number, or container of numbers
        If the source and target are both specified return a
        single number for the shortest path.
        If only the source is specified return a dictionary keyed by
        targets with a the shortest path as keys.
        If neither the source or target is specified return a dictionary
        of dictionaries with length[source][target]=value.

    Raises
    ------
    NetworkXNoPath
        If no path exists between source and target.

    Examples
    --------
    >>> G=nx.path_graph(5)
    >>> print(nx.shortest_path_length(G,source=0,target=4))
    4
    >>> p=nx.shortest_path_length(G,source=0) # target not specified
    >>> p[4]
    4
    >>> p=nx.shortest_path_length(G) # source,target not specified
    >>> p[0][4]
    4

    Notes
    -----
    For digraphs this returns the shortest directed path.
    To find path lengths in the reverse direction use G.reverse(copy=False)
    first to flip the edge orientation.

    See Also
    --------
    all_pairs_shortest_path_length()
    all_pairs_dijkstra_path_length()
    single_source_shortest_path_length()
    single_source_dijkstra_path_length()

    """
    if source is None:
        if target is None:
            if weight is None:
                paths=nx.all_pairs_shortest_path_length(G)
            else:
                paths=nx.all_pairs_dijkstra_path_length(G, weight=weight)
        else:
            raise nx.NetworkXError("Target given but no source specified.")
    else: # source specified
        if target is None:
            if weight is None:
                paths=nx.single_source_shortest_path_length(G,source)
            else:
                paths=nx.single_source_dijkstra_path_length(G,source,weight=weight)
        else:
            # shortest source-target path
            if weight is None:
                p=nx.bidirectional_shortest_path(G,source,target)
                paths=len(p)-1
            else:
                paths=nx.dijkstra_path_length(G,source,target,weight)
    return paths

def ford_fulkerson_flow_and_auxiliary(G, s, t, capacity='capacity'):
    """Find a maximum single-commodity flow using the Ford-Fulkerson
    algorithm.
    
    This function returns both the value of the maximum flow and the 
    auxiliary network resulting after finding the maximum flow, which
    is also named residual network in the literature. The 
    auxiliary network has edges with capacity equal to the capacity 
    of the edge in the original network minus the flow that went 
    throught that edge. Notice that it can happen that a flow 
    from v to u is allowed in the auxiliary network, though disallowed 
    in the original network. A dictionary with infinite capacity edges 
    can be found as an attribute of the auxiliary network.

    Parameters
    ----------
    G : NetworkX graph
        Edges of the graph are expected to have an attribute called
        'capacity'. If this attribute is not present, the edge is
        considered to have infinite capacity.

    s : node
        Source node for the flow.

    t : node
        Sink node for the flow.

    capacity: string
        Edges of the graph G are expected to have an attribute capacity
        that indicates how much flow the edge can support. If this
        attribute is not present, the edge is considered to have
        infinite capacity. Default value: 'capacity'.

    Returns
    -------
    flow_value : integer, float
        Value of the maximum flow, i.e., net outflow from the source.

    auxiliary : DiGraph
        Residual/auxiliary network after finding the maximum flow. 
        A dictionary with infinite capacity edges can be found as 
        an attribute of this network: auxiliary.graph['inf_capacity_flows']

    Raises
    ------
    NetworkXError
        The algorithm does not support MultiGraph and MultiDiGraph. If
        the input graph is an instance of one of these two classes, a
        NetworkXError is raised.

    NetworkXUnbounded
        If the graph has a path of infinite capacity, the value of a 
        feasible flow on the graph is unbounded above and the function
        raises a NetworkXUnbounded.

    Notes
    -----
    This algorithm uses Edmonds-Karp-Dinitz path selection rule which
    guarantees a running time of `O(nm^2)` for `n` nodes and `m` edges.

    Examples
    --------
    >>