Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.components.condensation

condensation(G, scc=None)[source]

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 – 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.

Return type

NetworkX DiGraph

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.