easygraph.functions.components.strongly_connected module#

easygraph.functions.components.strongly_connected.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. :param G: A directed graph. :type G: easygraph.DiGraph :param scc: Strongly connected components. If provided, the elements in

scc must partition the nodes in G. If not provided, it will be calculated as scc=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:: easygraph.DiGraph

Examples

# >>> condensation(G)

Notes

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

easygraph.functions.components.strongly_connected.is_strongly_connected(G)[source]#

Test directed graph for strong connectivity.

A directed graph is strongly connected if and only if every vertex in the graph is reachable from every other vertex.

Parameters:: G (EasyGraph Graph) – A directed graph.
Returns:: connected – True if the graph is strongly connected, False otherwise.
Return type:: bool

Examples

>>> G = eg.DiGraph([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4), (4, 2)])
>>> eg.is_strongly_connected(G)
True
>>> G.remove_edge(2, 3)
>>> eg.is_strongly_connected(G)
False

Raises:: EasyGraphNotImplemented – If G is undirected.

See also

strongly_connected_components, number_connected_components

Notes

For directed graphs only.

easygraph.functions.components.strongly_connected.strongly_connected_components(G)[source]#

Generate nodes in strongly connected components of graph.

Parameters:: G (EasyGraph Graph) – A directed graph.
Returns:: comp – A generator of sets of nodes, one for each strongly connected component of G.
Return type:: generator of sets
Raises:: EasyGraphNotImplemented – If G is undirected.

Examples

Generate a sorted list of strongly connected components, largest first.

If you only want the largest component, it’s more efficient to use max instead of sort.

>>> largest = max(eg.strongly_connected_components(G), key=len)