Skip to main content
`Ctrl`+`K`

# condensation

condensation(G, scc=None)

  Returns the condensation of G.

  The condensation of G is the graph with each of the strongly connected components contracted into a single node.

  Parameters:
    G NetworkX DiGraph

      A directed graph.

    scc: list or generator (optional, default=None)

      Strongly connected components. If provided, the elements in `scc` must partition the nodes in `G`. If not provided, it will be calculated as scc=nx.strongly_connected_components(G).

  Returns:
    C NetworkX DiGraph

      The condensation graph C of G. The node labels are integers corresponding to the index of the component in the list of strongly connected components of G. C has a graph attribute named ‘mapping’ with a dictionary mapping the original nodes to the nodes in C to which they belong. Each node in C also has a node attribute ‘members’ with the set of original nodes in G that form the SCC that the node in C represents.

  Raises:
    NetworkXNotImplemented

      If G is undirected.

  Notes

  After contracting all strongly connected components to a single node, the resulting graph is a directed acyclic graph.

  Examples

  Contracting two sets of strongly connected nodes into two distinct SCC using the barbell graph.

      >>> G = nx.barbell_graph(4, 0)
      >>> G.remove_edge(3, 4)
      >>> G = nx.DiGraph(G)
      >>> H = nx.condensation(G)
      >>> H.nodes.data()
      NodeDataView({0: {'members': {0, 1, 2, 3}}, 1: {'members': {4, 5, 6, 7}}})
      >>> H.graph["mapping"]
      {0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 1}

  Contracting a complete graph into one single SCC.

      >>> G = nx.complete_graph(7, create_using=nx.DiGraph)
      >>> H = nx.condensation(G)
      >>> H.nodes
      NodeView((0,))
      >>> H.nodes.data()
      NodeDataView({0: {'members': {0, 1, 2, 3, 4, 5, 6}}})