easygraph.functions.components package

Submodules

easygraph.functions.components.biconnected module

easygraph.functions.components.biconnected.biconnected_components(G)[source]

Returns a list of biconnected components, each of which denotes the edges set of a biconnected component.

Parameters:

G (easygraph.Graph or easygraph.DiGraph) –

Returns:

biconnected_components – Each element list is the edges set of a biconnected component.

Return type:

list of list

Examples

>>> connected_components(G)
easygraph.functions.components.biconnected.generator_articulation_points(G)[source]

Returns a generator of articulation points.

Parameters:

G (easygraph.Graph or easygraph.DiGraph) –

Return type:

Yields the articulation point in G.

Examples

>>> generator_articulation_points(G)
easygraph.functions.components.biconnected.generator_biconnected_components_edges(G)[source]

Returns a generator of nodes in each biconnected component.

Parameters:

G (easygraph.Graph or easygraph.DiGraph) –

Return type:

Yields edges set of each biconnected component.

See also

generator_biconnected_components_nodes

Examples

>>> generator_biconnected_components_edges(G)
easygraph.functions.components.biconnected.generator_biconnected_components_nodes(G)[source]

Returns a generator of nodes in each biconnected component.

Parameters:

G (easygraph.Graph or easygraph.DiGraph) –

Return type:

Yields nodes set of each biconnected component.

See also

generator_biconnected_components_edges

Examples

>>> generator_biconnected_components_nodes(G)
easygraph.functions.components.biconnected.is_biconnected(G)[source]

Returns whether the graph is biconnected or not.

Parameters:

G (easygraph.Graph or easygraph.DiGraph) –

Returns:

is_biconnected – True if the graph is biconnected.

Return type:

boolean

Examples

>>> is_biconnected(G)

easygraph.functions.components.connected module

easygraph.functions.components.connected.connected_component_of_node(G, node)[source]

Returns the connected component that node belongs to.

Parameters:

  • G (easygraph.Graph) –

  • node (object) – The target node

Returns:

connected_component_of_node – The connected component that node belongs to.

Return type:

set

Examples

Returns the connected component of one node Jack.

>>> connected_component_of_node(G, node='Jack')
easygraph.functions.components.connected.connected_components(*args, **kwargs)
easygraph.functions.components.connected.connected_components_directed(*args, **kwargs)
easygraph.functions.components.connected.is_connected(G)[source]

Returns whether the graph is connected or not.

Parameters:

G (easygraph.Graph or easygraph.DiGraph) –

Returns:

is_biconnected – True if the graph is connected.

Return type:

boolean

Examples

>>> is_connected(G)
easygraph.functions.components.connected.number_connected_components(G)[source]

Returns the number of connected components.

Parameters:

G (easygraph.Graph) –

Returns:

number_connected_components – The number of connected components.

Return type:

int

Examples

>>> number_connected_components(G)

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

is_connected, is_biconnected, strongly_connected_components

Notes

For directed graphs only.

easygraph.functions.components.strongly_connected.number_strongly_connected_components(G)[source]

Returns number of strongly connected components in graph.

Parameters:

G (Easygraph graph) – A directed graph.

Returns:

n – Number of strongly connected components

Return type:

integer

Raises:

EasygraphNotImplemented – If G is undirected.

Examples

>>> G = eg.DiGraph([(0, 1), (1, 2), (2, 0), (2, 3), (4, 5), (3, 4), (5, 6), (6, 3), (6, 7)])
>>> eg.number_strongly_connected_components(G)
3

See also

strongly_connected_components, number_connected_components

Notes

For directed graphs only.

easygraph.functions.components.strongly_connected.strongly_connected_components(*args, **kwargs)

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)

See also

connected_components, strongly_connected_components

Notes

For directed graphs only.

Module contents