Module Expr Str ImportFrom alias alias ImportFrom alias ImportFrom alias ImportFrom alias Import alias FunctionDef arguments args NameParam NameParam defaults NameLoad body Expr Str Assign NameStore ListLoad Assign NameStore Dict If CompareIsNot NameLoad NameLoad body Expr Call AttributeLoad NameLoad attr NameLoad Assign NameStore NameLoad Assign SubscriptStore NameLoad Index NameLoad NameLoad orelse Assign NameStore Num While CompareIsNot NameLoad NameLoad body Assign NameStore Call NameLoad NameLoad NameLoad If CompareEq NameLoad NameLoad body If CompareIsNot NameLoad NameLoad body Break Assign NameStore Call NameLoad NameLoad NameLoad If CompareIsNot NameLoad NameLoad body Assign SubscriptStore NameLoad Index NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad orelse Assign SubscriptStore NameLoad Index SubscriptLoad NameLoad Index Num SubscriptLoad NameLoad Index Num Expr Call AttributeLoad NameLoad attr SubscriptLoad NameLoad Index Num Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str For NameStore NameLoad body If CompareNotIn NameLoad NameLoad body Return NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str Assign NameStore NameLoad Assign NameStore NameLoad For NameStore NameLoad body For NameStore SubscriptLoad NameLoad Index NameLoad body If CompareNotIn NameLoad NameLoad body Assign NameStore Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad If BoolOpOr CompareIs NameLoad NameLoad CompareLt NameLoad NameLoad CompareLt NameLoad Num body Assign NameStore TupleLoad NameLoad NameLoad Assign NameStore NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str Assign NameStore Dict NameLoad Num Assign NameStore Dict NameLoad NameLoad Assign NameStore ListLoad TupleLoad Num NameLoad Assign NameStore Call NameLoad While CompareGt Call NameLoad NameLoad Num body Assign TupleStore NameStore NameStore Call AttributeLoad NameLoad attr Num If CompareNotIn NameLoad NameLoad body Expr Call AttributeLoad NameLoad attr NameLoad For NameStore SubscriptLoad NameLoad Index NameLoad body If CompareNotIn NameLoad NameLoad body Assign NameStore BinOpAdd NameLoad Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad If BoolOpOr CompareNotIn NameLoad NameLoad CompareLt NameLoad SubscriptLoad NameLoad Index NameLoad body Assign SubscriptStore NameLoad Index NameLoad NameLoad Assign SubscriptStore NameLoad Index NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad TupleLoad NameLoad NameLoad Return TupleLoad NameLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str Assign NameStore Dict NameLoad Num Assign NameStore Dict NameLoad NameLoad For NameStore Call NameLoad Num BinOpSub Call AttributeLoad NameLoad attr Num body For TupleStore NameStore NameStore Call AttributeLoad NameLoad attr body If BoolOpAnd CompareIn NameLoad NameLoad CompareNotIn NameLoad NameLoad body Assign SubscriptStore NameLoad Index NameLoad BinOpAdd SubscriptLoad NameLoad Index NameLoad Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad Assign SubscriptStore NameLoad Index NameLoad NameLoad orelse If BoolOpAnd CompareIn NameLoad NameLoad CompareIn NameLoad NameLoad CompareLt BinOpAdd SubscriptLoad NameLoad Index NameLoad Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad SubscriptLoad NameLoad Index NameLoad body Assign SubscriptStore NameLoad Index NameLoad BinOpAdd SubscriptLoad NameLoad Index NameLoad Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad Assign SubscriptStore NameLoad Index NameLoad NameLoad For TupleStore NameStore NameStore Call AttributeLoad NameLoad attr body If BoolOpAnd CompareIn NameLoad NameLoad CompareIn NameLoad NameLoad CompareLt BinOpAdd SubscriptLoad NameLoad Index NameLoad Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad SubscriptLoad NameLoad Index NameLoad body Raise Call NameLoad BinOpMod Str TupleLoad NameLoad NameLoad Return TupleLoad NameLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam NameParam defaults body Expr Str Assign NameStore ListLoad TupleLoad Num NameLoad Num NameLoad Assign NameStore Dict Assign NameStore Dict While NameLoad body Assign TupleStore NameStore NameStore NameStore NameStore Call NameLoad NameLoad If CompareEq NameLoad NameLoad body Assign NameStore BinOpAdd ListLoad NameLoad ListComp NameLoad comprehension NameStore Call NameLoad NameLoad NameLoad Expr Call AttributeLoad NameLoad attr Return NameLoad If CompareIn NameLoad NameLoad body Continue Assign SubscriptStore NameLoad Index NameLoad NameLoad For NameStore SubscriptLoad NameLoad Index NameLoad body If CompareIn NameLoad NameLoad body Continue Assign NameStore BinOpAdd NameLoad Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad If CompareIn NameLoad NameLoad body Assign TupleStore NameStore NameStore SubscriptLoad NameLoad Index NameLoad If CompareLtE NameLoad NameLoad body Continue orelse Assign NameStore Call NameLoad NameLoad NameLoad Assign SubscriptStore NameLoad Index NameLoad TupleLoad NameLoad NameLoad Expr Call NameLoad NameLoad TupleLoad BinOpAdd NameLoad NameLoad NameLoad NameLoad NameLoad Raise Call NameLoad NameLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body While CompareIsNot NameLoad NameLoad body Expr Yield NameLoad Assign NameStore SubscriptLoad NameLoad Index NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam NameParam defaults NameLoad body Expr Str If CompareEq NameLoad NameLoad body Assign NameStore Dict For NameStore Call AttributeLoad NameLoad attr body Assign SubscriptStore NameLoad Index NameLoad Call AttributeLoad NameLoad attr TupleLoad SubscriptLoad NameLoad Index Num SubscriptLoad NameLoad Index Num Assign NameStore Call AttributeLoad Dict attr Call AttributeLoad NameLoad attr Num Assign NameStore Call AttributeLoad Dict attr Call AttributeLoad NameLoad attr ListLoad Assign SubscriptStore NameLoad Index NameLoad ListLoad Str Call NameLoad Str Assign NameStore Call AttributeLoad Dict attr Call AttributeLoad NameLoad attr NameLoad Assign NameStore Call AttributeLoad Dict attr Call AttributeLoad NameLoad attr Call NameLoad Str Assign NameStore ListLoad NameLoad Assign NameStore NameLoad While UnaryOpNot NameLoad body For NameStore Call NameLoad Call NameLoad NameLoad body If UnaryOpNot SubscriptLoad NameLoad Index SubscriptLoad NameLoad Index NameLoad body Assign NameStore Call AttributeLoad NameLoad attr NameLoad Break For NameStore Call AttributeLoad NameLoad attr NameLoad body If BoolOpAnd CompareEq SubscriptLoad NameLoad Index NameLoad ListLoad CompareLt SubscriptLoad NameLoad Index TupleLoad NameLoad NameLoad SubscriptLoad NameLoad Index TupleLoad NameLoad NameLoad body Assign SubscriptStore NameLoad Index NameLoad Call NameLoad BinOpSub SubscriptLoad NameLoad Index TupleLoad NameLoad NameLoad SubscriptLoad NameLoad Index TupleLoad NameLoad NameLoad SubscriptLoad NameLoad Index NameLoad Assign SubscriptStore NameLoad Index NameLoad ListLoad NameLoad Str SubscriptLoad NameLoad Index NameLoad Expr Call AttributeLoad NameLoad attr NameLoad For NameStore Call AttributeLoad NameLoad attr NameLoad body If BoolOpAnd CompareEq SubscriptLoad NameLoad Index NameLoad ListLoad CompareGt SubscriptLoad NameLoad Index TupleLoad NameLoad NameLoad Num body Assign SubscriptStore NameLoad Index NameLoad Call NameLoad SubscriptLoad NameLoad Index TupleLoad NameLoad NameLoad SubscriptLoad NameLoad Index NameLoad Assign SubscriptStore NameLoad Index NameLoad ListLoad NameLoad Str SubscriptLoad NameLoad Index NameLoad Expr Call AttributeLoad NameLoad attr NameLoad Assign SubscriptStore NameLoad Index NameLoad NameLoad If CompareNotEq SubscriptLoad NameLoad Index NameLoad ListLoad body Assign NameStore SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index Num Assign NameStore NameLoad While CompareNotEq NameLoad NameLoad body Assign NameStore SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index Num If CompareEq SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index Num Str body Assign SubscriptStore NameLoad Index TupleLoad NameLoad NameLoad BinOpSub SubscriptLoad NameLoad Index TupleLoad NameLoad NameLoad NameLoad orelse Assign SubscriptStore NameLoad Index TupleLoad NameLoad NameLoad BinOpAdd SubscriptLoad NameLoad Index TupleLoad NameLoad NameLoad NameLoad Assign NameStore NameLoad Assign NameStore Call AttributeLoad Dict attr Call AttributeLoad NameLoad attr ListLoad Assign SubscriptStore NameLoad Index NameLoad ListLoad Str Call NameLoad Str Assign NameStore ListLoad NameLoad Assign NameStore Call AttributeLoad Dict attr Call AttributeLoad NameLoad attr NameLoad Assign NameStore Call AttributeLoad Dict attr Call AttributeLoad NameLoad attr Call NameLoad Str Assign NameStore NameLoad For NameStore Call AttributeLoad NameLoad attr body If BoolOpAnd CompareNotEq SubscriptLoad NameLoad Index NameLoad ListLoad CompareEq SubscriptLoad NameLoad Index NameLoad NameLoad body Assign NameStore NameLoad Assign NameStore Dict For NameStore Call AttributeLoad NameLoad attr body If CompareEq SubscriptLoad NameLoad Index NameLoad ListLoad body Assign SubscriptStore NameLoad Index NameLoad Num orelse Assign SubscriptStore NameLoad Index NameLoad Num Return TupleLoad NameLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults body Expr Str Assign NameStore ListLoad Assign NameStore ListLoad For NameStore Call AttributeLoad NameLoad attr body If CompareEq SubscriptLoad NameLoad Index NameLoad Num body Expr Call AttributeLoad NameLoad attr NameLoad orelse If CompareEq SubscriptLoad NameLoad Index NameLoad Num body Expr Call AttributeLoad NameLoad attr NameLoad Assign NameStore Num For NameStore NameLoad body For NameStore Call AttributeLoad NameLoad attr NameLoad body If CompareIn NameLoad NameLoad body Assign NameStore BinOpAdd NameLoad SubscriptLoad NameLoad Index TupleLoad NameLoad NameLoad For NameStore Call AttributeLoad NameLoad attr NameLoad body If CompareIn NameLoad NameLoad body Assign NameStore BinOpSub NameLoad SubscriptLoad NameLoad Index TupleLoad NameLoad NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults NameLoad body Expr Str Assign NameStore Call NameLoad Expr Call AttributeLoad NameLoad attr NameLoad If UnaryOpNot NameLoad body Assign NameStore Dict For NameStore Call AttributeLoad NameLoad attr body Assign SubscriptStore NameLoad Index NameLoad Call AttributeLoad NameLoad attr NameLoad Assign NameStore Dict Assign NameStore Dict Assign NameStore Num For NameStore Call AttributeLoad NameLoad attr body Assign SubscriptStore NameLoad Index NameLoad NameLoad Assign NameStore BinOpAdd NameLoad Num Assign NameStore Call AttributeLoad Dict attr Call NameLoad NameLoad Num Assign SubscriptStore NameLoad Index Num NameLoad For NameStore Call NameLoad Num NameLoad body Assign NameStore SubscriptLoad NameLoad Index NameLoad Assign NameStore ListLoad Assign TupleStore NameStore NameStore Call NameLoad NameLoad SubscriptLoad NameLoad Index NameLoad SubscriptLoad NameLoad Index NameLoad NameLoad For NameStore Call NameLoad NameLoad body If CompareEq SubscriptLoad NameLoad Index SubscriptLoad NameLoad Index NameLoad Num body Expr Call AttributeLoad NameLoad attr NameLoad Assign NameStore Call NameLoad NameLoad NameLoad NameLoad Assign SubscriptStore NameLoad Index NameLoad NameLoad For NameStore Call NameLoad NameLoad body If CompareEq NameLoad NameLoad body Continue If BoolOpAnd CompareIn NameLoad NameLoad CompareEq SubscriptLoad NameLoad Index NameLoad NameLoad body Assign SubscriptStore NameLoad Index NameLoad NameLoad If CompareIn SubscriptLoad NameLoad Index NameLoad NameLoad body Assign SubscriptStore NameLoad Index NameLoad SubscriptLoad NameLoad Index NameLoad Assign SubscriptStore NameLoad Index NameLoad NameLoad Assign SubscriptStore NameLoad Index NameLoad SubscriptLoad NameLoad Index NameLoad Assign SubscriptStore NameLoad Index NameLoad NameLoad Assign NameStore Dict For NameStore Call NameLoad Num NameLoad body Assign SubscriptStore NameLoad Index TupleLoad SubscriptLoad NameLoad Index NameLoad SubscriptLoad NameLoad Index SubscriptLoad NameLoad Index NameLoad SubscriptLoad NameLoad Index NameLoad Return NameLoad decorator_list
N/A N/A 
Minimization and maximization algorithms.

@sort: heuristic_search, minimal_spanning_tree, shortest_path,
shortest_path_bellman_ford
 pygraph.algorithms.utils heappush heappop pygraph.classes.exceptions NodeUnreachable pygraph.classes.exceptions NegativeWeightCycleError pygraph.classes.digraph digraph N/A bisect minimal_spanning_tree N/A N/A graph root N/A None N/A N/A 
    Minimal spanning tree.

    @attention: Minimal spanning tree is meaningful only for weighted graphs.

    @type  graph: graph
    @param graph: Graph.
    
    @type  root: node
    @param root: Optional root node (will explore only root's connected component)

    @rtype:  dictionary
    @return: Generated spanning tree.
     N/A visited N/A N/A spanning_tree N/A N/A N/A root None N/A N/A N/A N/A visited append root N/A nroot root N/A N/A spanning_tree N/A root None N/A N/A nroot 1 N/A N/A nroot None N/A N/A ledge N/A _lightest_edge graph visited N/A N/A ledge None N/A N/A N/A root None N/A N/A N/A nroot N/A _first_unvisited graph visited N/A N/A nroot None N/A N/A N/A spanning_tree N/A nroot None N/A N/A N/A visited append nroot N/A N/A N/A spanning_tree N/A N/A ledge N/A 1 N/A ledge N/A 0 N/A N/A N/A visited append N/A ledge N/A 1 N/A spanning_tree N/A _first_unvisited N/A N/A graph visited N/A N/A N/A 
    Return first unvisited node.
    
    @type  graph: graph
    @param graph: Graph.

    @type  visited: list
    @param visited: List of nodes.
    
    @rtype:  node
    @return: First unvisited node.
     N/A each graph N/A N/A N/A each visited N/A N/A each N/A None N/A _lightest_edge N/A N/A graph visited N/A N/A N/A 
    Return the lightest edge in graph going from a visited node to an unvisited one.
    
    @type  graph: graph
    @param graph: Graph.

    @type  visited: list
    @param visited: List of nodes.

    @rtype:  tuple
    @return: Lightest edge in graph going from a visited node to an unvisited one.
     N/A lightest_edge None N/A weight None N/A each visited N/A N/A other N/A graph N/A each N/A N/A N/A other visited N/A N/A w N/A N/A graph edge_weight N/A each other N/A N/A N/A weight None N/A w weight N/A weight 0 N/A N/A lightest_edge N/A each other N/A weight w N/A lightest_edge N/A shortest_path N/A N/A graph source N/A N/A N/A 
    Return the shortest path distance between source and all other nodes using Dijkstra's
    algorithm.
    
    @attention: All weights must be nonnegative.
    
    @see: shortest_path_bellman_ford

    @type  graph: graph, digraph
    @param graph: Graph.

    @type  source: node
    @param source: Node from which to start the search.

    @rtype:  tuple
    @return: A tuple containing two dictionaries, each keyed by target nodes.
        1. Shortest path spanning tree
        2. Shortest distance from given source to each target node
    Inaccessible target nodes do not appear in either dictionary.
     N/A dist N/A source 0 N/A previous N/A source None N/A q N/A N/A 0 source N/A finished N/A set N/A N/A N/A len q 0 N/A N/A N/A du u N/A N/A q pop 0 N/A N/A u finished N/A N/A N/A N/A finished add u N/A v N/A graph N/A u N/A N/A N/A v finished N/A N/A alt N/A du N/A N/A graph edge_weight N/A u v N/A N/A N/A v dist N/A alt N/A dist N/A v N/A N/A N/A dist N/A v alt N/A N/A previous N/A v u N/A N/A N/A bisect insort q N/A alt v N/A N/A previous dist N/A shortest_path_bellman_ford N/A N/A graph source N/A N/A N/A 
    Return the shortest path distance between the source node and all other 
    nodes in the graph using Bellman-Ford's algorithm.
    
    This algorithm is useful when you have a weighted (and obviously 
    a directed) graph with negative weights.
    
    @attention: The algorithm can detect negative weight cycles and will raise 
    an exception. It's meaningful only for directed weighted graphs.
    
    @see: shortest_path
    
    @type graph: digraph
    @param graph: Digraph
    
    @type source: node
    @param source: Source node of the graph
    
    @raise NegativeWeightCycleError: raises if it finds a negative weight cycle.
    If this condition is met d(v) > d(u) + W(u, v) then raise the error. 
    
    @rtype: tuple 
    @return: A tuple containing two dictionaries, each keyed by target nodes.
    (same as shortest_path function that implements Dijkstra's algorithm)
        1. Shortest path spanning tree
        2. Shortest distance from given source to each target node
     N/A distance N/A source 0 N/A predecessor N/A source None N/A i N/A range 1 N/A N/A N/A graph order 1 N/A N/A N/A src dst N/A N/A graph edges N/A N/A N/A N/A src distance N/A dst distance N/A N/A N/A distance N/A dst N/A N/A distance N/A src N/A N/A graph edge_weight N/A src dst N/A N/A predecessor N/A dst src N/A N/A N/A N/A src distance N/A dst distance N/A N/A N/A distance N/A src N/A N/A graph edge_weight N/A src dst N/A distance N/A dst N/A N/A N/A distance N/A dst N/A N/A distance N/A src N/A N/A graph edge_weight N/A src dst N/A N/A predecessor N/A dst src N/A N/A src dst N/A N/A graph edges N/A N/A N/A N/A src distance N/A dst distance N/A N/A N/A distance N/A src N/A N/A graph edge_weight N/A src dst N/A distance N/A dst N/A N/A N/A NegativeWeightCycleError N/A Detected a negative weight cycle on edge (%s, %s) N/A src dst N/A N/A predecessor distance N/A heuristic_search N/A N/A graph start goal heuristic N/A N/A N/A 
    A* search algorithm.
    
    A set of heuristics is available under C{graph.algorithms.heuristics}. User-created heuristics
    are allowed too.
    
    @type graph: graph, digraph
    @param graph: Graph
    
    @type start: node
    @param start: Start node
    
    @type goal: node
    @param goal: Goal node
    
    @type heuristic: function
    @param heuristic: Heuristic function
    
    @rtype: list
    @return: Optimized path from start to goal node 
     N/A queue N/A N/A 0 start 0 None N/A g N/A N/A explored N/A N/A queue N/A N/A N/A _ current dist parent N/A heappop queue N/A N/A current goal N/A N/A path N/A N/A current N/A n N/A n N/A _reconstruct_path parent explored N/A N/A N/A path reverse N/A path N/A N/A current explored N/A N/A N/A N/A explored N/A current parent N/A neighbor N/A graph N/A current N/A N/A N/A neighbor explored N/A N/A N/A ncost N/A dist N/A N/A graph edge_weight N/A current neighbor N/A N/A neighbor g N/A N/A N/A qcost h N/A g N/A neighbor N/A N/A qcost ncost N/A N/A N/A N/A h N/A heuristic neighbor goal N/A N/A g N/A neighbor N/A ncost h N/A N/A heappush queue N/A N/A ncost h neighbor ncost current N/A N/A NodeUnreachable start goal N/A _reconstruct_path N/A N/A node parents N/A N/A N/A N/A node None N/A N/A N/A node N/A node N/A parents N/A node N/A maximum_flow N/A N/A graph source sink caps N/A None N/A N/A 
    Find a maximum flow and minimum cut of a directed graph by the Edmonds-Karp algorithm.

    @type graph: digraph
    @param graph: Graph

    @type source: node
    @param source: Source of the flow

    @type sink: node
    @param sink: Sink of the flow

    @type caps: dictionary
    @param caps: Dictionary specifying a maximum capacity for each edge. If not given, the weight of the edge
    will be used as its capacity. Otherwise, for each edge (a,b), caps[(a,b)] should be given.
    
    @rtype: tuple
    @return: A tuple containing two dictionaries
        1. contains the flow through each edge for a maximal flow through the graph
        2. contains to which component of a minimum cut each node belongs
     N/A N/A caps None N/A N/A caps N/A N/A edge N/A N/A graph edges N/A N/A N/A caps N/A edge N/A N/A graph edge_weight N/A N/A edge N/A 0 N/A edge N/A 1 N/A f N/A N/A N/A fromkeys N/A N/A graph edges 0 N/A label N/A N/A N/A fromkeys N/A N/A graph nodes N/A N/A N/A label N/A source N/A - N/A float Inf N/A u N/A N/A N/A fromkeys N/A N/A graph nodes False N/A d N/A N/A N/A fromkeys N/A N/A graph nodes N/A float Inf N/A q N/A source N/A finished False N/A N/A finished N/A N/A i N/A range N/A len q N/A N/A N/A N/A u N/A N/A q N/A i N/A N/A v N/A N/A q pop i N/A N/A w N/A N/A graph neighbors v N/A N/A N/A N/A N/A label N/A w N/A N/A N/A f N/A N/A v w N/A caps N/A N/A v w N/A N/A N/A d N/A w N/A min N/A N/A caps N/A N/A v w N/A f N/A N/A v w N/A d N/A v N/A N/A label N/A w N/A v + N/A d N/A w N/A N/A N/A q append w N/A w N/A N/A graph incidents v N/A N/A N/A N/A N/A label N/A w N/A N/A N/A f N/A N/A w v 0 N/A N/A N/A d N/A w N/A min N/A f N/A N/A w v N/A d N/A v N/A N/A label N/A w N/A v - N/A d N/A w N/A N/A N/A q append w N/A N/A u N/A v True N/A N/A N/A label N/A sink N/A N/A N/A delta N/A N/A label N/A sink N/A -1 N/A w sink N/A N/A w source N/A N/A v N/A N/A label N/A w N/A 0 N/A N/A N/A N/A label N/A w N/A 1 - N/A N/A N/A f N/A N/A w v N/A N/A f N/A N/A w v delta N/A N/A N/A f N/A N/A v w N/A N/A f N/A N/A v w delta N/A w v N/A label N/A N/A N/A fromkeys N/A N/A graph nodes N/A N/A N/A label N/A source N/A - N/A float Inf N/A q N/A source N/A u N/A N/A N/A fromkeys N/A N/A graph nodes False N/A d N/A N/A N/A fromkeys N/A N/A graph nodes N/A float Inf N/A finished True N/A node N/A N/A graph nodes N/A N/A N/A N/A N/A label N/A node N/A N/A N/A u N/A node False N/A N/A finished False N/A cut N/A N/A node N/A N/A graph nodes N/A N/A N/A N/A label N/A node N/A N/A N/A N/A cut N/A node 1 N/A N/A N/A cut N/A node 0 N/A N/A f cut N/A cut_value N/A N/A graph flow cut N/A N/A N/A 
    Calculate the value of a cut.

    @type graph: digraph
    @param graph: Graph

    @type flow: dictionary
    @param flow: Dictionary containing a flow for each edge.

    @type cut: dictionary
    @param cut: Dictionary mapping each node to a subset index. The function only considers the flow between
    nodes with 0 and 1.
    
    @rtype: float
    @return: The value of the flow between the subsets 0 and 1
     N/A S N/A N/A T N/A N/A node N/A N/A cut keys N/A N/A N/A N/A cut N/A node 0 N/A N/A N/A N/A S append node N/A N/A N/A N/A cut N/A node 1 N/A N/A N/A N/A T append node N/A value 0 N/A node S N/A N/A neigh N/A N/A graph neighbors node N/A N/A N/A neigh T N/A N/A value N/A value N/A flow N/A N/A node neigh N/A inc N/A N/A graph incidents node N/A N/A N/A inc T N/A N/A value N/A value N/A flow N/A N/A inc node N/A value N/A cut_tree N/A N/A igraph caps N/A None N/A N/A 
    Construct a Gomory-Hu cut tree by applying the algorithm of Gusfield.

    @type igraph: graph
    @param igraph: Graph

    @type caps: dictionary
    @param caps: Dictionary specifying a maximum capacity for each edge. If not given, the weight of the edge
    will be used as its capacity. Otherwise, for each edge (a,b), caps[(a,b)] should be given.
    
    @rtype: dictionary
    @return: Gomory-Hu cut tree as a dictionary, where each edge is associated with its weight
     N/A graph N/A digraph N/A N/A N/A graph add_graph igraph N/A N/A caps N/A N/A caps N/A N/A edge N/A N/A graph edges N/A N/A N/A caps N/A edge N/A N/A igraph edge_weight edge N/A f N/A N/A n N/A N/A N 0 N/A node N/A N/A graph nodes N/A N/A N/A n N/A N node N/A N N/A N 1 N/A p N/A N/A N/A fromkeys N/A range N 0 N/A N/A p N/A 0 None N/A s N/A range 1 N N/A N/A t N/A p N/A s N/A S N/A N/A N/A flow cut N/A maximum_flow graph N/A n N/A s N/A n N/A t caps N/A i N/A range N N/A N/A N/A N/A cut N/A N/A n N/A i 0 N/A N/A N/A N/A S append i N/A value N/A cut_value graph flow cut N/A N/A f N/A s value N/A i N/A range N N/A N/A N/A i s N/A N/A N/A N/A N/A i S N/A N/A p N/A i t N/A N/A N/A p N/A i s N/A N/A N/A p N/A t S N/A N/A N/A p N/A s N/A p N/A t N/A N/A p N/A t s N/A N/A f N/A s N/A f N/A t N/A N/A f N/A t value N/A b N/A N/A i N/A range 1 N N/A N/A N/A b N/A N/A N/A n N/A i N/A n N/A N/A p N/A i N/A f N/A i N/A b N/A