mapgraph::algo

Module scc

Source
Available on crate features algorithms and alloc only.
Expand description

Contains an implementation of the Tarjan’s SCC algorithm.

This algorithm expects the graph to be connected. In case the graph is disjoint, only nodes belonging to the same component as the start node will be marked.

§Marking SCCs

Strongly-Connected Components are represented by user-provided types. The implementation interacts with the types using the Scc and WithScc traits.

The Scc trait should be implemented by the type representing an SCC. The type is expected to be easily clonable and the only required method is with_entry that constructs the type from an index of an arbitrary node belonging to the SCC. See docs for the Scc trait for more information.

The WithScc trait is used to actually mark graph nodes with an SCC. It should be implemented on the graph’s node weight type.

This design allows to only reserve place for information about SCCs in graphs that actually use this algorithm.

§Secondary maps

The algorithm expects a secondary map that maps node indices to tuples containing two u32 values to be provided as its last argument. This is only useful when you have strict performance requirements. When in doubt you should use a HashMap or a BTreeMap. In some cases, however, it might affect performance of the algorithm, especially for large graphs. If this is your case, continue reading.

Choosing a map is a concern mostly for graphs based on SlotMap-like node maps which provide secondary maps that can be accessed faster than HashMaps. These maps are backed by vectors so the usage of memory will be inefficient when you only visit a small number of node slots:

  1. When the node slots are densely located but the component the start node belongs to happens to be a small part of the graph;
  2. When the node slots are located sparsely.

Otherwise using these secondary maps is OK and will give you a performance boost when compared to other kinds of maps.

Traits§

Scc
A trait for a type that represents a strongly-connected component of a graph.
WithScc
A trait for a node weight that stores information about the SCC it belongs to.

Functions§

mark_sccs
Runs Tarjan’s SCC detection algorithm on a graph and marks weights with SCCs they belong to.
mark_sccs_with_filter
Runs Tarjan’s SCC detection algorithm on a graph while ignoring certain edges and marks weights with SCCs they belong to.