Module components

Algorithms related to graph components, i.e. finding the strongly or weakly connected components of a graph or checking if a graph is strongly connected.

Functions

decompose_strongly_connected_components

Returns the strongly connected components of a graph.

decompose_strongly_connected_components_non_consecutive

Returns the strongly connected components of a graph whose indices are non-consecutive.

decompose_weakly_connected_components

Returns the weakly connected components of a graph.

decompose_weakly_connected_components_with_mappings

Returns the weakly connected components of a graph, as well as a mapping from node indices in the WCCs to node indices in the source graph, and a mapping from edge indices in the WCCs to edge indices in the source graph.

extract_subgraphs_from_node_mapping

Extract the subgraphs of the given graph according to the given node_mapping.

is_cycle

Returns true if the given graph is a cycle.

is_strong_bridge

Returns true if the given edge is a strong bridge. Note that this function assumes that the graph is strongly connected, and always returns true otherwise.

is_strongly_connected

Returns true if the graph is strongly connected.

naively_compute_strong_bridges

Compute the strong bridges of the graph with a naive O(m^2) algorithm. Note that this function assumes that the graph is strongly connected, and returns all edges otherwise.