class_docstr: A simple algorithm to find all k-edge-connected components in a graph.
  
  Constructing the auxiliary graph (which may take some time) allows for the
  k-edge-ccs to be found in linear time for arbitrary k.
  
  Notes
  -----
  This implementation is based on [1]_. The idea is to construct an auxiliary
  graph from which the k-edge-ccs can be extracted in linear time. The
  auxiliary graph is constructed in $O(|V|\cdot F)$ operations, where F is the
  complexity of max flow. Querying the components takes an additional $O(|V|)$
  operations. This algorithm can be slow for large graphs, but it handles an
  arbitrary k and works for both directed and undirected inputs.
  
  The undirected case for k=1 is exactly connected components.
  The undirected case for k=2 is exactly bridge connected components.
  The directed case for k=1 is exactly strongly connected components.
  
  References
  ----------
  .. [1] Wang, Tianhao, et al. (2015) A simple algorithm for finding all
      k-edge-connected components.
      http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264
  
  Examples
  --------
  >>> import itertools as it
  >>> from networkx.utils import pairwise
  >>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph
  >>> # Build an interesting graph with multiple levels of k-edge-ccs
  >>> paths = [
  ...     (1, 2, 3, 4, 1, 3, 4, 2),  # a 3-edge-cc (a 4 clique)
  ...     (5, 6, 7, 5),  # a 2-edge-cc (a 3 clique)
  ...     (1, 5),  # combine first two ccs into a 1-edge-cc
  ...     (0,),  # add an additional disconnected 1-edge-cc
  ... ]
  >>> G = nx.Graph()
  >>> G.add_nodes_from(it.chain(*paths))
  >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
  >>> # Constructing the AuxGraph takes about O(n ** 4)
  >>> aux_graph = EdgeComponentAuxGraph.construct(G)
  >>> # Once constructed, querying takes O(n)
  >>> sorted(map(sorted, aux_graph.k_edge_components(k=1)))
  [[0], [1, 2, 3, 4, 5, 6, 7]]
  >>> sorted(map(sorted, aux_graph.k_edge_components(k=2)))
  [[0], [1, 2, 3, 4], [5, 6, 7]]
  >>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))
  [[0], [1, 2, 3, 4], [5], [6], [7]]
  >>> sorted(map(sorted, aux_graph.k_edge_components(k=4)))
  [[0], [1], [2], [3], [4], [5], [6], [7]]
  
  The auxiliary graph is primarily used for k-edge-ccs but it
  can also speed up the queries of k-edge-subgraphs by refining the
  search space.
  
  >>> import itertools as it
  >>> from networkx.utils import pairwise
  >>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph
  >>> paths = [
  ...     (1, 2, 4, 3, 1, 4),
  ... ]
  >>> G = nx.Graph()
  >>> G.add_nodes_from(it.chain(*paths))
  >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
  >>> aux_graph = EdgeComponentAuxGraph.construct(G)
  >>> sorted(map(sorted, aux_graph.k_edge_subgraphs(k=3)))
  [[1], [2], [3], [4]]
  >>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))
  [[1, 4], [2], [3]]
class_docstr_tok: ["A","simple","algorithm","to","find","all","k-edge-connected","components","in","a","graph",".","Constructing","the","auxiliary","graph","(","which","may","take","some","time",")","allows","for","the","k-edge-ccs","to","be","found","in","linear","time","for","arbitrary","k.","Notes","--","--","-","This","implementation","is","based","on","[","1","]","_",".","The","idea","is","to","construct","an","auxiliary","graph","from","which","the","k-edge-ccs","can","be","extracted","in","linear","time",".","The","auxiliary","graph","is","constructed","in","$","O","(","|V|\\cdot","F",")","$","operations",",","where","F","is","the","complexity","of","max","flow",".","Querying","the","components","takes","an","additional","$","O","(","|V|",")","$","operations",".","This","algorithm","can","be","slow","for","large","graphs",",","but","it","handles","an","arbitrary","k","and","works","for","both","directed","and","undirected","inputs",".","The","undirected","case","for","k=1","is","exactly","connected","components",".","The","undirected","case","for","k=2","is","exactly","bridge","connected","components",".","The","directed","case","for","k=1","is","exactly","strongly","connected","components",".","References","--","--","--","--","--","..","[","1","]","Wang",",","Tianhao",",","et","al",".","(","2015",")","A","simple","algorithm","for","finding","all","k-edge-connected","components",".","http",":","\/\/journals.plos.org\/plosone\/article","?","id=10.1371\/journal.pone.0136264","Examples","--","--","--","--",">",">",">","import","itertools","as","it",">",">",">","from","networkx.utils","import","pairwise",">",">",">","from","networkx.algorithms.connectivity","import","EdgeComponentAuxGraph",">",">",">","#","Build","an","interesting","graph","with","multiple","levels","of","k-edge-ccs",">",">",">","paths","=","[","...","(","1",",","2",",","3",",","4",",","1",",","3",",","4",",","2",")",",","#","a","3-edge-cc","(","a","4","clique",")","...","(","5",",","6",",","7",",","5",")",",","#","a","2-edge-cc","(","a","3","clique",")","...","(","1",",","5",")",",","#","combine","first","two","ccs","into","a","1-edge-cc","...","(","0",",",")",",","#","add","an","additional","disconnected","1-edge-cc","...","]",">",">",">","G","=","nx.Graph","(",")",">",">",">","G.add_nodes_from","(","it.chain","(","*","paths",")",")",">",">",">","G.add_edges_from","(","it.chain","(","*","[","pairwise","(","path",")","for","path","in","paths","]",")",")",">",">",">","#","Constructing","the","AuxGraph","takes","about","O","(","n","*","*","4",")",">",">",">","aux_graph","=","EdgeComponentAuxGraph.construct","(","G",")",">",">",">","#","Once","constructed",",","querying","takes","O","(","n",")",">",">",">","sorted","(","map","(","sorted",",","aux_graph.k_edge_components","(","k=1",")",")",")","[","[","0","]",",","[","1",",","2",",","3",",","4",",","5",",","6",",","7","]","]",">",">",">","sorted","(","map","(","sorted",",","aux_graph.k_edge_components","(","k=2",")",")",")","[","[","0","]",",","[","1",",","2",",","3",",","4","]",",","[","5",",","6",",","7","]","]",">",">",">","sorted","(","map","(","sorted",",","aux_graph.k_edge_components","(","k=3",")",")",")","[","[","0","]",",","[","1",",","2",",","3",",","4","]",",","[","5","]",",","[","6","]",",","[","7","]","]",">",">",">","sorted","(","map","(","sorted",",","aux_graph.k_edge_components","(","k=4",")",")",")","[","[","0","]",",","[","1","]",",","[","2","]",",","[","3","]",",","[","4","]",",","[","5","]",",","[","6","]",",","[","7","]","]","The","auxiliary","graph","is","primarily","used","for","k-edge-ccs","but","it","can","also","speed","up","the","queries","of","k-edge-subgraphs","by","refining","the","search","space",".",">",">",">","import","itertools","as","it",">",">",">","from","networkx.utils","import","pairwise",">",">",">","from","networkx.algorithms.connectivity","import","EdgeComponentAuxGraph",">",">",">","paths","=","[","...","(","1",",","2",",","4",",","3",",","1",",","4",")",",","...","]",">",">",">","G","=","nx.Graph","(",")",">",">",">","G.add_nodes_from","(","it.chain","(","*","paths",")",")",">",">",">","G.add_edges_from","(","it.chain","(","*","[","pairwise","(","path",")","for","path","in","paths","]",")",")",">",">",">","aux_graph","=","EdgeComponentAuxGraph.construct","(","G",")",">",">",">","sorted","(","map","(","sorted",",","aux_graph.k_edge_subgraphs","(","k=3",")",")",")","[","[","1","]",",","[","2","]",",","[","3","]",",","[","4","]","]",">",">",">","sorted","(","map","(","sorted",",","aux_graph.k_edge_components","(","k=3",")",")",")","[","[","1",",","4","]",",","[","2","]",",","[","3","]","]"]
docstr: Builds an auxiliary graph encoding edge-connectivity between nodes.
  
  Notes
  -----
  Given G=(V, E), initialize an empty auxiliary graph A.
  Choose an arbitrary source node s.  Initialize a set N of available
  nodes (that can be used as the sink). The algorithm picks an
  arbitrary node t from N - {s}, and then computes the minimum st-cut
  (S, T) with value w. If G is directed the minimum of the st-cut or
  the ts-cut is used instead. Then, the edge (s, t) is added to the
  auxiliary graph with weight w. The algorithm is called recursively
  first using S as the available nodes and s as the source, and then
  using T and t. Recursion stops when the source is the only available
  node.
  
  Parameters
  ----------
  G : NetworkX graph
docstr_tok: ["Builds","an","auxiliary","graph","encoding","edge-connectivity","between","nodes",".","Notes","--","--","-","Given","G=","(","V",",","E",")",",","initialize","an","empty","auxiliary","graph","A",".","Choose","an","arbitrary","source","node","s.","Initialize","a","set","N","of","available","nodes","(","that","can","be","used","as","the","sink",")",".","The","algorithm","picks","an","arbitrary","node","t","from","N","-","{","s","}",",","and","then","computes","the","minimum","st-cut","(","S",",","T",")","with","value","w.","If","G","is","directed","the","minimum","of","the","st-cut","or","the","ts-cut","is","used","instead",".","Then",",","the","edge","(","s",",","t",")","is","added","to","the","auxiliary","graph","with","weight","w.","The","algorithm","is","called","recursively","first","using","S","as","the","available","nodes","and","s","as","the","source",",","and","then","using","T","and","t.","Recursion","stops","when","the","source","is","the","only","available","node",".","Parameters","--","--","--","--","--","G",":","NetworkX","graph"]
code: def construct(EdgeComponentAuxGraph, G):
      """Builds an auxiliary graph encoding edge-connectivity between nodes.
  
      Notes
      -----
      Given G=(V, E), initialize an empty auxiliary graph A.
      Choose an arbitrary source node s.  Initialize a set N of available
      nodes (that can be used as the sink). The algorithm picks an
      arbitrary node t from N - {s}, and then computes the minimum st-cut
      (S, T) with value w. If G is directed the minimum of the st-cut or
      the ts-cut is used instead. Then, the edge (s, t) is added to the
      auxiliary graph with weight w. The algorithm is called recursively
      first using S as the available nodes and s as the source, and then
      using T and t. Recursion stops when the source is the only available
      node.
  
      Parameters
      ----------
      G : NetworkX graph
      """
      # workaround for classmethod decorator
      not_implemented_for("multigraph")(lambda G: G)(G)
  
      def _recursive_build(H, A, source, avail):
          # Terminate once the flow has been compute to every node.
          if {source} == avail:
              return
          # pick an arbitrary node as the sink
          sink = arbitrary_element(avail - {source})
          # find the minimum cut and its weight
          value, (S, T) = nx.minimum_cut(H, source, sink)
          if H.is_directed():
              # check if the reverse direction has a smaller cut
              value_, (T_, S_) = nx.minimum_cut(H, sink, source)
              if value_ < value:
                  value, S, T = value_, S_, T_
          # add edge with weight of cut to the aux graph
          A.add_edge(source, sink, weight=value)
          # recursively call until all but one node is used
          _recursive_build(H, A, source, avail.intersection(S))
          _recursive_build(H, A, sink, avail.intersection(T))
  
      # Copy input to ensure all edges have unit capacity
      H = G.__class__()
      H.add_nodes_from(G.nodes())
      H.add_edges_from(G.edges(), capacity=1)
  
      # A is the auxiliary graph to be constructed
      # It is a weighted undirected tree
      A = nx.Graph()
  
      # Pick an arbitrary node as the source
      if H.number_of_nodes() > 0:
          source = arbitrary_element(H.nodes())
          # Initialize a set of elements that can be chosen as the sink
          avail = set(H.nodes())
  
          # This constructs A
          _recursive_build(H, A, source, avail)
  
      # This class is a container the holds the auxiliary graph A and
      # provides access the k_edge_components function.
      self = EdgeComponentAuxGraph()
      self.A = A
      self.H = H
      return self
  
file_path: networkx/networkx/algorithms/connectivity/edge_kcomponents.py
imports: import itertools
  from functools import partial
  import networkx
  from networkx.utils import arbitrary_element, not_implemented_for
label_desc: Use image node_id 1 for calling the EdgeComponentAuxGraph obj's underlying member method code with example usage: obj.construct(EdgeComponentAuxGraph, G) and returns: self