easygraph.functions.components.weakly_connected module#

Weakly connected components.

easygraph.functions.components.weakly_connected.is_weakly_connected(G)[source]#

Test directed graph for weak connectivity.

A directed graph is weakly connected if and only if the graph is connected when the direction of the edge between nodes is ignored.

Note that if a graph is strongly connected (i.e. the graph is connected even when we account for directionality), it is by definition weakly connected as well.

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

Examples

>>> G = eg.DiGraph([(0, 1), (2, 1)])
>>> G.add_node(3)
>>> eg.is_weakly_connected(G)  # node 3 is not connected to the graph
False
>>> G.add_edge(2, 3)
>>> eg.is_weakly_connected(G)
True

See also

is_strongly_connected, is_semiconnected, is_connected, is_biconnected, weakly_connected_components

Notes

For directed graphs only.

easygraph.functions.components.weakly_connected.number_weakly_connected_components(G)[source]#

Returns the number of weakly connected components in G.

Parameters:: G (EasyGraph graph) – A directed graph.
Returns:: n – Number of weakly connected components
Return type:: integer
Raises:: EasyGraphNotImplemented – If G is undirected.

Examples

>>> G = eg.DiGraph([(0, 1), (2, 1), (3, 4)])
>>> eg.number_weakly_connected_components(G)
2

See also

weakly_connected_components, number_connected_components, number_strongly_connected_components

Notes

For directed graphs only.

easygraph.functions.components.weakly_connected.weakly_connected_components(G)[source]#

Generate weakly connected components of G.

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

Examples

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

>>> G = eg.path_graph(4, create_using=eg.DiGraph())
>>> eg.add_path(G, [10, 11, 12])
>>> [
...     len(c)
...     for c in sorted(eg.weakly_connected_components(G), key=len, reverse=True)
... ]
[4, 3]

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

>>> largest_cc = max(eg.weakly_connected_components(G), key=len)