Module traitgraph_algo::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_weakly_connected_components
  Returns the weakly connected components of a 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.