Module Expr Str Import alias ImportFrom alias Import alias identifier ImportFrom alias alias alias alias Assign NameStore Call AttributeLoad Str attr ListLoad Str Assign NameStore ListLoad Str Str Str Str FunctionDef arguments args NameParam NameParam NameParam NameParam defaults Str body Expr Str TryExcept body Assign TupleStore NameStore NameStore Call AttributeLoad NameLoad attr NameLoad NameLoad NameLoad keyword NameLoad Assign NameStore Call NameLoad Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr NameLoad NameLoad Assign NameStore BinOpSub Call NameLoad NameLoad NameLoad For TupleStore NameStore NameStore GeneratorExp TupleLoad NameLoad SubscriptLoad NameLoad Index NameLoad comprehension NameStore NameLoad body Expr Call AttributeLoad NameLoad attr GeneratorExp TupleLoad NameLoad NameLoad comprehension NameStore NameLoad CompareIn NameLoad NameLoad Return NameLoad handlers ExceptHandler type AttributeLoad NameLoad attr body Raise Call AttributeLoad NameLoad attr Str decorator_list FunctionDef arguments args NameParam NameParam NameParam NameParam NameParam defaults NameLoad NameLoad body Expr Str If BoolOpOr CompareIs NameLoad NameLoad CompareIs NameLoad NameLoad body Assign TupleStore NameStore NameStore Call NameLoad NameLoad orelse Assign NameStore NameLoad Assign NameStore Call NameLoad NameLoad BinOpMod Str SubscriptLoad NameLoad Index NameLoad BinOpMod Str SubscriptLoad NameLoad Index NameLoad Assign NameStore Call NameLoad GeneratorExp SubscriptLoad SubscriptLoad AttributeLoad NameLoad attr Index NameLoad Index Str comprehension NameStore NameLoad comprehension NameStore NameLoad Return BinOpSub NameLoad Call NameLoad ListLoad NameLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults NameLoad NameLoad body Expr Str If BoolOpAnd CompareIsNot NameLoad NameLoad CompareIsNot NameLoad NameLoad body If CompareNotIn NameLoad NameLoad body Raise Call AttributeLoad NameLoad attr BinOpMod Str NameLoad If CompareNotIn NameLoad NameLoad body Raise Call AttributeLoad NameLoad attr BinOpMod Str NameLoad Return Call NameLoad NameLoad NameLoad NameLoad If Call AttributeLoad NameLoad attr body If UnaryOpNot Call AttributeLoad NameLoad attr NameLoad body Raise Call AttributeLoad NameLoad attr Str Assign NameStore AttributeLoad NameLoad attr FunctionDef arguments args NameParam defaults body Return Call AttributeLoad AttributeLoad NameLoad attr attr ListLoad Call AttributeLoad NameLoad attr NameLoad Call AttributeLoad NameLoad attr NameLoad decorator_list orelse If UnaryOpNot Call AttributeLoad NameLoad attr NameLoad body Raise Call AttributeLoad NameLoad attr Str Assign NameStore AttributeLoad NameLoad attr Assign NameStore AttributeLoad NameLoad attr Assign NameStore Call AttributeLoad NameLoad attr Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr Assign NameStore Call NameLoad GeneratorExp NameLoad comprehension TupleStore NameStore NameStore Call AttributeLoad NameLoad attr CompareEq NameLoad NameLoad Assign NameStore Call NameLoad SubscriptLoad NameLoad Index NameLoad Assign TupleStore NameStore NameStore Call NameLoad NameLoad For NameStore BinOpSub BinOpSub Call NameLoad NameLoad Call NameLoad Call NameLoad NameLoad Call NameLoad ListLoad NameLoad body Assign NameStore Call NameLoad NameLoad NameLoad NameLoad keyword NameLoad keyword NameLoad If CompareGtE Call NameLoad NameLoad Call NameLoad NameLoad body Assign NameStore NameLoad For TupleStore NameStore NameStore Call NameLoad Call NameLoad NameLoad Num body If CompareIn NameLoad SubscriptLoad NameLoad Index NameLoad body Continue Assign NameStore Call NameLoad NameLoad NameLoad NameLoad keyword NameLoad keyword NameLoad If CompareGtE Call NameLoad NameLoad Call NameLoad NameLoad body Assign NameStore NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults NameLoad NameLoad body Expr Str Assign NameStore Call NameLoad NameLoad If BoolOpAnd CompareIsNot NameLoad NameLoad CompareIsNot NameLoad NameLoad body If CompareNotIn NameLoad NameLoad body Raise Call AttributeLoad NameLoad attr BinOpMod Str NameLoad If CompareNotIn NameLoad NameLoad body Raise Call AttributeLoad NameLoad attr BinOpMod Str NameLoad Return Call NameLoad NameLoad NameLoad NameLoad If Call AttributeLoad NameLoad attr body If UnaryOpNot Call AttributeLoad NameLoad attr NameLoad body Raise Call AttributeLoad NameLoad attr Str Assign NameStore Call AttributeLoad NameLoad attr Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr Assign NameStore Call NameLoad GeneratorExp NameLoad comprehension TupleStore NameStore NameStore Call AttributeLoad NameLoad attr CompareEq NameLoad NameLoad Assign NameStore Call AttributeLoad NameLoad attr NameLoad Assign NameStore Call AttributeLoad NameLoad attr Assign NameStore Call NameLoad NameLoad For NameStore Call NameLoad NameLoad body TryExcept body Assign NameStore Call NameLoad NameLoad SubscriptLoad NameLoad Index NameLoad SubscriptLoad NameLoad Index BinOpAdd NameLoad Num If CompareLtE Call NameLoad NameLoad Call NameLoad NameLoad body Assign NameStore NameLoad handlers ExceptHandler type NameLoad body Assign NameStore Call NameLoad NameLoad SubscriptLoad NameLoad Index NameLoad SubscriptLoad NameLoad Index Num If CompareLtE Call NameLoad NameLoad Call NameLoad NameLoad body Assign NameStore NameLoad Return NameLoad orelse If UnaryOpNot Call AttributeLoad NameLoad attr NameLoad body Raise Call AttributeLoad NameLoad attr Str Assign NameStore Call AttributeLoad NameLoad attr Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr Assign NameStore Call NameLoad GeneratorExp NameLoad comprehension TupleStore NameStore NameStore Call AttributeLoad NameLoad attr CompareEq NameLoad NameLoad Assign NameStore Call AttributeLoad NameLoad attr NameLoad For NameStore NameLoad body Assign NameStore Call NameLoad NameLoad keyword NameLoad Assign NameStore Call AttributeLoad NameLoad attr If NameLoad body Break orelse Return NameLoad For NameStore NameLoad body Assign NameStore Call NameLoad NameLoad NameLoad NameLoad If CompareLtE Call NameLoad NameLoad Call NameLoad NameLoad body Assign NameStore NameLoad Return NameLoad decorator_list
N/A N/A 
Flow based cut algorithms
 N/A itertools operator itemgetter N/A networkx nx networkx.algorithms.connectivity.connectivity _aux_digraph_node_connectivity _aux_digraph_edge_connectivity dominating_set node_connectivity N/A __author__ N/A N/A join N/A Jordi Torrents <jtorrents@milnou.net> N/A __all__ N/A minimum_st_node_cut minimum_node_cut minimum_st_edge_cut minimum_edge_cut minimum_st_edge_cut N/A N/A G s t capacity N/A capacity N/A N/A Returns the edges of the cut-set of a minimum (s, t)-cut.

    We use the max-flow min-cut theorem, i.e., the capacity of a minimum
    capacity cut is equal to the flow value of a maximum flow.

    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
    -------
    cutset : set
        Set of edges that, if removed from the graph, will disconnect it
    
    Raises
    ------
    NetworkXUnbounded
        If the graph has a path of infinite capacity, all cuts have
        infinite capacity and the function raises a NetworkXError.
    
    Examples
    --------
    >>> 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)
    >>> sorted(nx.minimum_edge_cut(G, 'x', 'y'))
    [('c', 'y'), ('x', 'b')]
    >>> nx.min_cut(G, 'x', 'y')
    3.0
     N/A N/A N/A N/A flow H N/A N/A nx ford_fulkerson_flow_and_auxiliary G s t capacity capacity N/A cutset N/A set N/A reachable N/A set N/A N/A nx single_source_shortest_path H s N/A others N/A N/A set H reachable N/A N/A u nbrs N/A N/A n N/A G N/A n N/A n reachable N/A N/A N/A N/A cutset update N/A N/A u v N/A v nbrs N/A v others N/A cutset N/A N/A N/A N/A nx NetworkXUnbounded N/A N/A N/A N/A nx NetworkXUnbounded Infinite capacity path, no minimum cut. N/A minimum_st_node_cut N/A N/A G s t aux_digraph mapping N/A None None N/A N/A Returns a set of nodes of minimum cardinality that disconnect source
    from target in G.

    This function returns the set of nodes of minimum cardinality that, 
    if removed, would destroy all paths among source and target in G. 
    
    Parameters
    ----------
    G : NetworkX graph

    s : node
        Source node.

    t : node
        Target node.

    Returns
    -------
    cutset : set
        Set of nodes that, if removed, would destroy all paths between 
        source and target in G.

    Examples
    --------
    >>> # Platonic icosahedral graph has node connectivity 5 
    >>> G = nx.icosahedral_graph()
    >>> len(nx.minimum_node_cut(G, 0, 6))
    5

    Notes
    -----
    This is a flow based implementation of minimum node cut. The algorithm 
    is based in solving a number of max-flow problems (ie local st-node
    connectivity, see local_node_connectivity) to determine the capacity 
    of the minimum cut on an auxiliary directed network that corresponds 
    to the minimum node cut of G. It handles both directed and undirected 
    graphs.

    This implementation is based on algorithm 11 in [1]_. We use the Ford 
    and Fulkerson algorithm to compute max flow (see ford_fulkerson).

    See also
    --------
    node_connectivity
    edge_connectivity
    minimum_edge_cut
    max_flow
    ford_fulkerson 

    References
    ----------
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. 
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

     N/A N/A N/A aux_digraph None N/A mapping None N/A N/A N/A H mapping N/A _aux_digraph_node_connectivity G N/A N/A H aux_digraph N/A edge_cut N/A minimum_st_edge_cut H N/A %sB N/A mapping N/A s N/A %sA N/A mapping N/A t N/A node_cut N/A set N/A N/A N/A N/A H node N/A node N/A id N/A edge edge_cut N/A node edge N/A N/A node_cut N/A set N/A s t N/A minimum_node_cut N/A N/A G s t N/A None None N/A N/A Returns a set of nodes of minimum cardinality that disconnects G.

    If source and target nodes are provided, this function returns the 
    set of nodes of minimum cardinality that, if removed, would destroy 
    all paths among source and target in G. If not, it returns a set 
    of nodes of minimum cardinality that disconnects G.
    
    Parameters
    ----------
    G : NetworkX graph

    s : node
        Source node. Optional (default=None)

    t : node
        Target node. Optional (default=None)

    Returns
    -------
    cutset : set
        Set of nodes that, if removed, would disconnect G. If source 
        and target nodes are provided, the set contians the nodes that
        if removed, would destroy all paths between source and target.

    Examples
    --------
    >>> # Platonic icosahedral graph has node connectivity 5 
    >>> G = nx.icosahedral_graph()
    >>> len(nx.minimum_node_cut(G))
    5
    >>> # this is the minimum over any pair of non adjacent nodes
    >>> from itertools import combinations
    >>> for u,v in combinations(G, 2):
    ...     if v not in G[u]:
    ...         assert(len(nx.minimum_node_cut(G,u,v)) == 5)
    ... 

    Notes
    -----
    This is a flow based implementation of minimum node cut. The algorithm 
    is based in solving a number of max-flow problems (ie local st-node
    connectivity, see local_node_connectivity) to determine the capacity 
    of the minimum cut on an auxiliary directed network that corresponds 
    to the minimum node cut of G. It handles both directed and undirected 
    graphs.

    This implementation is based on algorithm 11 in [1]_. We use the Ford 
    and Fulkerson algorithm to compute max flow (see ford_fulkerson).

    See also
    --------
    node_connectivity
    edge_connectivity
    minimum_edge_cut
    max_flow
    ford_fulkerson 

    References
    ----------
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. 
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

     N/A N/A N/A s None N/A t None N/A N/A N/A s G N/A N/A N/A N/A nx NetworkXError N/A node %s not in graph s N/A N/A t G N/A N/A N/A N/A nx NetworkXError N/A node %s not in graph t N/A N/A minimum_st_node_cut G s t N/A N/A N/A G is_directed N/A N/A N/A N/A N/A nx is_weakly_connected G N/A N/A N/A N/A nx NetworkXError Input graph is not connected N/A iter_func N/A itertools permutations neighbors N/A N/A v N/A N/A N/A N/A N/A N/A itertools chain from_iterable N/A N/A N/A G predecessors_iter v N/A N/A G successors_iter v N/A N/A N/A N/A N/A N/A nx is_connected G N/A N/A N/A N/A nx NetworkXError Input graph is not connected N/A iter_func N/A itertools combinations N/A neighbors N/A G neighbors_iter N/A deg N/A N/A G degree N/A min_deg N/A min N/A N/A deg values N/A v N/A next N/A n N/A N/A n d N/A N/A deg items N/A d min_deg N/A min_cut N/A set N/A G N/A v N/A N/A H mapping N/A _aux_digraph_node_connectivity G N/A w N/A N/A N/A set G N/A set N/A neighbors v N/A set N/A v N/A N/A this_cut N/A minimum_st_node_cut G v w aux_digraph H mapping mapping N/A N/A N/A len min_cut N/A len this_cut N/A N/A min_cut this_cut N/A N/A x y N/A iter_func N/A neighbors v 2 N/A N/A N/A y N/A G N/A x N/A N/A N/A this_cut N/A minimum_st_node_cut G x y aux_digraph H mapping mapping N/A N/A N/A len min_cut N/A len this_cut N/A N/A min_cut this_cut N/A min_cut N/A minimum_edge_cut N/A N/A G s t N/A None None N/A N/A Returns a set of edges of minimum cardinality that disconnects G.

    If source and target nodes are provided, this function returns the 
    set of edges of minimum cardinality that, if removed, would break 
    all paths among source and target in G. If not, it returns a set of 
    edges of minimum cardinality that disconnects G.
    
    Parameters
    ----------
    G : NetworkX graph

    s : node
        Source node. Optional (default=None)

    t : node
        Target node. Optional (default=None)

    Returns
    -------
    cutset : set
        Set of edges that, if removed, would disconnect G. If source 
        and target nodes are provided, the set contians the edges that
        if removed, would destroy all paths between source and target.

    Examples
    --------
    >>> # Platonic icosahedral graph has edge connectivity 5
    >>> G = nx.icosahedral_graph()
    >>> len(nx.minimum_edge_cut(G))
    5
    >>> # this is the minimum over any pair of nodes
    >>> from itertools import combinations
    >>> for u,v in combinations(G, 2):
    ...     assert(len(nx.minimum_edge_cut(G,u,v)) == 5)
    ... 

    Notes
    -----
    This is a flow based implementation of minimum edge cut. For
    undirected graphs the algorithm works by finding a 'small' dominating
    set of nodes of G (see algorithm 7 in [1]_) and computing the maximum
    flow between an arbitrary node in the dominating set and the rest of
    nodes in it. This is an implementation of algorithm 6 in [1]_.

    For directed graphs, the algorithm does n calls to the max flow function.
    This is an implementation of algorithm 8 in [1]_. We use the Ford and
    Fulkerson algorithm to compute max flow (see ford_fulkerson).

    See also
    --------
    node_connectivity
    edge_connectivity
    minimum_node_cut
    max_flow
    ford_fulkerson

    References
    ----------
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

     N/A H N/A _aux_digraph_edge_connectivity G N/A N/A N/A s None N/A t None N/A N/A N/A s G N/A N/A N/A N/A nx NetworkXError N/A node %s not in graph s N/A N/A t G N/A N/A N/A N/A nx NetworkXError N/A node %s not in graph t N/A N/A minimum_st_edge_cut H s t N/A N/A N/A G is_directed N/A N/A N/A N/A N/A nx is_weakly_connected G N/A N/A N/A N/A nx NetworkXError Input graph is not connected N/A deg N/A N/A G degree N/A min_deg N/A min N/A N/A deg values N/A node N/A next N/A n N/A N/A n d N/A N/A deg items N/A d min_deg N/A min_cut N/A N/A G edges node N/A nodes N/A N/A G nodes N/A n N/A len nodes N/A i N/A range n N/A N/A N/A N/A this_cut N/A minimum_st_edge_cut H N/A nodes N/A i N/A nodes N/A N/A i 1 N/A N/A N/A len this_cut N/A len min_cut N/A N/A min_cut this_cut N/A N/A N/A IndexError N/A N/A this_cut N/A minimum_st_edge_cut H N/A nodes N/A i N/A nodes N/A 0 N/A N/A N/A len this_cut N/A len min_cut N/A N/A min_cut this_cut N/A min_cut N/A N/A N/A N/A N/A nx is_connected G N/A N/A N/A N/A nx NetworkXError Input graph is not connected N/A deg N/A N/A G degree N/A min_deg N/A min N/A N/A deg values N/A node N/A next N/A n N/A N/A n d N/A N/A deg items N/A d min_deg N/A min_cut N/A N/A G edges node N/A node G N/A N/A D N/A dominating_set G start_with node N/A v N/A N/A D pop N/A D N/A N/A N/A N/A min_cut N/A w D N/A N/A this_cut N/A minimum_st_edge_cut H v w N/A N/A N/A len this_cut N/A len min_cut N/A N/A min_cut this_cut N/A min_cut N/A