Module Expr Str Assign NameStore Str ImportFrom alias Import alias identifier ImportFrom alias ImportFrom alias Assign NameStore ListLoad Str FunctionDef arguments args NameParam NameParam NameParam NameParam NameParam NameParam NameParam defaults body Expr Str If CompareNotIn NameLoad NameLoad body Raise Call AttributeLoad NameLoad attr BinOpMod Str Call NameLoad NameLoad If CompareNotIn NameLoad NameLoad body Raise Call AttributeLoad NameLoad attr BinOpMod Str Call NameLoad NameLoad If CompareEq NameLoad NameLoad body Raise Call AttributeLoad NameLoad attr Str If CompareIs NameLoad NameLoad body Assign NameStore Call NameLoad NameLoad NameLoad orelse Assign NameStore NameLoad Assign NameStore AttributeLoad NameLoad attr Assign NameStore AttributeLoad NameLoad attr Assign NameStore AttributeLoad NameLoad attr For NameStore NameLoad body For NameStore Call AttributeLoad SubscriptLoad NameLoad Index NameLoad attr body Assign SubscriptStore NameLoad Index Str Num Assign NameStore Dict NameLoad Num Assign NameStore Call NameLoad ListLoad TupleLoad NameLoad Num While NameLoad body Assign TupleStore NameStore NameStore Call AttributeLoad NameLoad attr AugAssignAdd NameStore Num For TupleStore NameStore NameStore Call AttributeLoad SubscriptLoad NameLoad Index NameLoad attr body If BoolOpAnd CompareNotIn NameLoad NameLoad CompareLt SubscriptLoad NameLoad Index Str SubscriptLoad NameLoad Index Str body Assign SubscriptStore NameLoad Index NameLoad NameLoad Expr Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad If CompareNotIn NameLoad NameLoad body Assign SubscriptStore AttributeLoad NameLoad attr Index Str Num Return NameLoad Assign NameStore Call NameLoad NameLoad Assign NameStore BinOpDiv Call AttributeLoad NameLoad attr Num For NameStore NameLoad body Assign SubscriptStore SubscriptLoad NameLoad Index NameLoad Index Str IfExp CompareIn NameLoad NameLoad SubscriptLoad NameLoad Index NameLoad NameLoad Assign SubscriptStore SubscriptLoad NameLoad Index NameLoad Index Str Call NameLoad SubscriptLoad NameLoad Index NameLoad Assign NameStore BinOpMult ListLoad Num BinOpSub BinOpMult Num NameLoad Num For NameStore NameLoad body AugAssignAdd SubscriptStore NameLoad Index SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index Str Num Assign NameStore SubscriptLoad AttributeLoad NameLoad attr Index Str FunctionDef arguments args NameParam defaults body Expr Str Assign NameStore NameLoad Assign NameStore Call NameLoad NameLoad Assign NameStore Call NameLoad NameLoad For NameStore NameLoad body Assign NameStore SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index NameLoad Assign NameStore Call NameLoad NameLoad BinOpSub SubscriptLoad NameLoad Index Str SubscriptLoad NameLoad Index Str Assign NameStore NameLoad If CompareGt BinOpMult NameLoad Num NameLoad body Raise Call AttributeLoad NameLoad attr Str Assign NameStore Call NameLoad NameLoad Assign NameStore Call NameLoad NameLoad For NameStore NameLoad body AugAssignAdd SubscriptStore SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index NameLoad Index Str NameLoad AugAssignSub SubscriptStore SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index NameLoad Index Str NameLoad Assign NameStore NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam defaults body Expr Str Assign NameStore BinOpSub NameLoad Num For TupleStore NameStore NameStore Call AttributeLoad SubscriptLoad NameLoad Index NameLoad attr body If CompareLt SubscriptLoad NameLoad Index Str SubscriptLoad NameLoad Index Str body Assign NameStore Call NameLoad NameLoad SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index Str Return BinOpAdd NameLoad Num decorator_list If CompareIs NameLoad NameLoad body Assign NameStore Call NameLoad Str Assign NameStore Num Assign NameStore ListLoad NameLoad Assign NameStore NameLoad Assign NameStore IfExp UnaryOpNot NameLoad NameLoad Call NameLoad Call NameLoad BinOpPow NameLoad Num BinOpMult Num BinOpPow NameLoad BinOpDiv Num Num Assign NameStore CompareGtE SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index Str NameLoad While UnaryOpNot NameLoad body Assign NameStore SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index Str Assign NameStore SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index Str While NameLoad body Assign TupleStore NameStore NameStore Call AttributeLoad NameLoad attr If BoolOpAnd CompareEq NameLoad BinOpAdd SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index Str Num CompareLt SubscriptLoad NameLoad Index Str SubscriptLoad NameLoad Index Str body Expr Call AttributeLoad NameLoad attr NameLoad Assign NameStore NameLoad Break TryExcept body Expr Call AttributeLoad NameLoad attr handlers ExceptHandler type NameLoad body AugAssignSub SubscriptStore NameLoad Index NameLoad Num If CompareEq SubscriptLoad NameLoad Index NameLoad Num body Assign SubscriptStore AttributeLoad NameLoad attr Index Str NameLoad Return NameLoad Assign NameStore Call NameLoad NameLoad If BoolOpAnd CompareEq NameLoad NameLoad CompareGtE NameLoad NameLoad body If UnaryOpNot NameLoad body Assign SubscriptStore AttributeLoad NameLoad attr Index Str NameLoad Return NameLoad orelse Assign NameStore NameLoad Break AugAssignAdd SubscriptStore NameLoad Index NameLoad Num Assign SubscriptStore SubscriptLoad NameLoad Index NameLoad Index Str NameLoad If CompareNotEq NameLoad NameLoad body Expr Call AttributeLoad NameLoad attr Assign NameStore SubscriptLoad NameLoad Index Num Break If CompareEq NameLoad NameLoad body AugAssignAdd NameStore Call NameLoad NameLoad If CompareGtE NameLoad NameLoad body Assign SubscriptStore AttributeLoad NameLoad attr Index Str NameLoad Return NameLoad Assign NameStore ListLoad NameLoad Assign NameStore NameLoad AugAssignAdd NameStore Call NameLoad NameLoad NameLoad NameLoad BinOpSub NameLoad NameLoad Assign SubscriptStore AttributeLoad NameLoad attr Index Str NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam NameParam NameParam NameParam NameParam NameParam defaults Str NameLoad NameLoad NameLoad NameLoad body Expr Str Assign NameStore Call NameLoad NameLoad NameLoad NameLoad NameLoad NameLoad NameLoad NameLoad Assign SubscriptStore AttributeLoad NameLoad attr Index Str Str Return NameLoad decorator_list
N/A N/A 
Shortest augmenting path algorithm for maximum flow problems.
 N/A __author__ ysitu <ysitu@users.noreply.github.com> collections deque N/A networkx nx utils * edmondskarp edmonds_karp_core N/A __all__ N/A shortest_augmenting_path shortest_augmenting_path_impl N/A N/A G s t capacity residual two_phase cutoff N/A N/A N/A Implementation of the shortest augmenting path algorithm.
     N/A N/A s G N/A N/A N/A N/A nx NetworkXError N/A node %s not in graph N/A str s N/A N/A t G N/A N/A N/A N/A nx NetworkXError N/A node %s not in graph N/A str t N/A N/A s t N/A N/A N/A N/A nx NetworkXError source and sink are the same node N/A N/A residual None N/A N/A R N/A build_residual_network G capacity N/A N/A R residual N/A R_node N/A R node N/A R_pred N/A R pred N/A R_succ N/A R succ N/A u R N/A N/A e N/A N/A N/A R_succ N/A u values N/A N/A N/A e N/A flow 0 N/A heights N/A t 0 N/A q N/A deque N/A N/A t 0 N/A q N/A N/A N/A u height N/A N/A q popleft N/A height 1 N/A N/A v attr N/A N/A N/A R_pred N/A u items N/A N/A N/A N/A v heights N/A N/A attr N/A flow N/A attr N/A capacity N/A N/A N/A heights N/A v height N/A N/A N/A q append N/A v height N/A N/A s heights N/A N/A N/A N/A R graph N/A flow_value 0 N/A R N/A n N/A len G N/A m N/A N/A N/A R size 2 N/A u R N/A N/A N/A N/A R_node N/A u N/A height N/A N/A u heights N/A heights N/A u n N/A N/A N/A R_node N/A u N/A curr_edge N/A CurrentEdge N/A R_succ N/A u N/A counts N/A N/A 0 N/A N/A 2 n 1 N/A u R N/A N/A N/A counts N/A N/A N/A R_node N/A u N/A height 1 N/A inf N/A N/A R graph N/A inf augment N/A N/A path N/A N/A N/A Augment flow along a path from s to t.
         N/A flow inf N/A it N/A iter path N/A u N/A next it N/A v it N/A N/A attr N/A N/A R_succ N/A u N/A v N/A flow N/A min flow N/A N/A attr N/A capacity N/A attr N/A flow N/A u v N/A N/A N/A flow 2 inf N/A N/A N/A N/A nx NetworkXUnbounded Infinite capacity path, flow unbounded above. N/A it N/A iter path N/A u N/A next it N/A v it N/A N/A N/A N/A N/A R_succ N/A u N/A v N/A flow flow N/A N/A N/A N/A R_succ N/A v N/A u N/A flow flow N/A u v N/A flow N/A relabel N/A N/A u N/A N/A N/A Relabel a node to create an admissible edge.
         N/A height N/A n 1 N/A N/A v attr N/A N/A N/A R_succ N/A u items N/A N/A N/A N/A attr N/A flow N/A attr N/A capacity N/A N/A height N/A min height N/A N/A R_node N/A v N/A height N/A N/A height 1 N/A N/A N/A cutoff None N/A N/A cutoff N/A float inf N/A flow_value 0 N/A path N/A s N/A u s N/A d N/A N/A two_phase n N/A int N/A min N/A m 0.5 N/A 2 N/A n N/A 2.0 3 N/A done N/A N/A N/A R_node N/A s N/A height d N/A N/A done N/A N/A height N/A N/A R_node N/A u N/A height N/A curr_edge N/A N/A R_node N/A u N/A curr_edge N/A True N/A N/A N/A v attr N/A N/A curr_edge get N/A N/A N/A height N/A N/A N/A R_node N/A v N/A height 1 N/A N/A attr N/A flow N/A attr N/A capacity N/A N/A N/A N/A path append v N/A u v N/A N/A N/A N/A N/A N/A curr_edge move_to_next N/A N/A N/A StopIteration N/A N/A N/A counts N/A height 1 N/A N/A N/A counts N/A height 0 N/A N/A N/A N/A R graph N/A flow_value flow_value N/A R N/A height N/A relabel u N/A N/A N/A u s N/A height d N/A N/A N/A two_phase N/A N/A N/A N/A R graph N/A flow_value flow_value N/A R N/A N/A done True N/A N/A N/A counts N/A height 1 N/A N/A N/A R_node N/A u N/A height height N/A N/A u s N/A N/A N/A N/A path pop N/A u N/A path N/A -1 N/A N/A N/A u t N/A N/A flow_value N/A augment path N/A N/A flow_value cutoff N/A N/A N/A N/A R graph N/A flow_value flow_value N/A R N/A path N/A s N/A u s N/A flow_value N/A edmonds_karp_core R s t N/A cutoff flow_value N/A N/A N/A R graph N/A flow_value flow_value N/A R N/A shortest_augmenting_path N/A N/A G s t capacity residual value_only two_phase cutoff N/A capacity None False False None N/A N/A Find a maximum single-commodity flow using the shortest augmenting path
    algorithm.

    This function returns the residual network resulting after computing
    the maximum flow. See below for details about the conventions
    NetworkX uses for defining residual networks.

    This algorithm has a running time of `O(n^2 m)` for `n` nodes and `m`
    edges.


    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'.

    residual : NetworkX graph
        Residual network on which the algorithm is to be executed. If None, a
        new residual network is created. Default value: None.

    value_only : bool
        If True compute only the value of the maximum flow. This parameter
        will be ignored by this algorithm because it is not applicable.

    two_phase : bool
        If True, a two-phase variant is used. The two-phase variant improves
        the running time on unit-capacity networks from `O(nm)` to
        `O(\min(n^{2/3}, m^{1/2}) m)`. Default value: False.

    cutoff : integer, float
        If specified, the algorithm will terminate when the flow value reaches
        or exceeds the cutoff. In this case, it may be unable to immediately
        determine a minimum cut. Default value: None.

    Returns
    -------
    R : NetworkX DiGraph
        Residual network after computing the maximum flow.

    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.

    See also
    --------
    :meth:`maximum_flow`
    :meth:`minimum_cut`
    :meth:`edmonds_karp`
    :meth:`preflow_push`

    Notes
    -----
    The residual network :samp:`R` from an input graph :samp:`G` has the
    same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
    of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
    self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
    in :samp:`G`.

    For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
    is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
    in :samp:`G` or zero otherwise. If the capacity is infinite,
    :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
    that does not affect the solution of the problem. This value is stored in
    :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
    :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
    satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.

    The flow value, defined as the total flow into :samp:`t`, the sink, is
    stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
    specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
    that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
    :samp:`s`-:samp:`t` cut.

    Examples
    --------
    >>> import networkx as nx
    >>> from networkx.algorithms.flow import shortest_augmenting_path

    The functions that implement flow algorithms and output a residual
    network, such as this one, are not imported to the base NetworkX
    namespace, so you have to explicitly import them from the flow package.

    >>> 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)
    >>> R = shortest_augmenting_path(G, 'x', 'y')
    >>> flow_value = nx.maximum_flow_value(G, 'x', 'y')
    >>> flow_value
    3.0
    >>> flow_value == R.graph['flow_value']
    True

     N/A R N/A shortest_augmenting_path_impl G s t capacity residual two_phase cutoff N/A N/A N/A R graph N/A algorithm shortest_augmenting_path N/A R N/A