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: Queries the auxiliary graph for k-edge-connected subgraphs.
  
  Parameters
  ----------
  k : Integer
      Desired edge connectivity
  
  Returns
  -------
  k_edge_subgraphs : a generator of k-edge-subgraphs
  
  Notes
  -----
  Refines the k-edge-ccs into k-edge-subgraphs. The running time is more
  than $O(|V|)$.
  
  For single values of k it is faster to use `nx.k_edge_subgraphs`.
  But for multiple values of k, it can be faster to build AuxGraph and
  then use this method.
docstr_tok: ["Queries","the","auxiliary","graph","for","k-edge-connected","subgraphs",".","Parameters","--","--","--","--","--","k",":","Integer","Desired","edge","connectivity","Returns","--","--","--","-","k_edge_subgraphs",":","a","generator","of","k-edge-subgraphs","Notes","--","--","-","Refines","the","k-edge-ccs","into","k-edge-subgraphs",".","The","running","time","is","more","than","$","O","(","|V|",")","$",".","For","single","values","of","k","it","is","faster","to","use","`","nx.k_edge_subgraphs","`",".","But","for","multiple","values","of","k",",","it","can","be","faster","to","build","AuxGraph","and","then","use","this","method","."]
code: def k_edge_subgraphs(self, k):
      """Queries the auxiliary graph for k-edge-connected subgraphs.
  
      Parameters
      ----------
      k : Integer
          Desired edge connectivity
  
      Returns
      -------
      k_edge_subgraphs : a generator of k-edge-subgraphs
  
      Notes
      -----
      Refines the k-edge-ccs into k-edge-subgraphs. The running time is more
      than $O(|V|)$.
  
      For single values of k it is faster to use `nx.k_edge_subgraphs`.
      But for multiple values of k, it can be faster to build AuxGraph and
      then use this method.
      """
      if k < 1:
          raise ValueError("k cannot be less than 1")
      H = self.H
      A = self.A
      # "traverse the auxiliary graph A and delete all edges with weights less
      # than k"
      aux_weights = nx.get_edge_attributes(A, "weight")
      # Create a relevant graph with the auxiliary edges with weights >= k
      R = nx.Graph()
      R.add_nodes_from(A.nodes())
      R.add_edges_from(e for e, w in aux_weights.items() if w >= k)
  
      # Return the components whose subgraphs are k-edge-connected
      for cc in nx.connected_components(R):
          if len(cc) < k:
              # Early return optimization
              for node in cc:
                  yield {node}
          else:
              # Call subgraph solution to refine the results
              C = H.subgraph(cc)
              yield from k_edge_subgraphs(C, k)
  
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 3 for calling the EdgeComponentAuxGraph obj's underlying member method code with example usage: obj.k_edge_subgraphs(k) without return types