Opm::StronglyConnectedComponents Struct Reference

The strongly connected components of a directed graph, as computed by tarjan(). More...

#include <Tarjan.hpp>

Public Member Functions
int	numComponents () const
	The number of components. More...
std::span< const int >	operator[] (int k) const
	The vertices of a component. More...
auto	components () const
	All components in order, for use in a range-based for loop. More...

Public Attributes
std::vector< int >	vertices
std::vector< int >	offsets {0}
std::vector< int >	componentOf
	The component each vertex belongs to. More...

Detailed Description

The strongly connected components of a directed graph, as computed by tarjan().

The components are numbered in reverse topological order of the condensation of the graph: if there is an edge from a vertex in component a to a vertex in a different component b, then b < a. For an upwind graph (edges point from a cell to the cells it receives flow from) this means that component 0 is the most upstream one and that every component only depends on components with a lower number.

Member Function Documentation

components()

auto Opm::StronglyConnectedComponents::components ( ) const

inline

All components in order, for use in a range-based for loop.

Returns

A view with one std::span<const int> per component, see operator[]().

References numComponents().

numComponents()

int Opm::StronglyConnectedComponents::numComponents ( ) const

inline

The number of components.

Returns

The number of components, i.e. offsets.size() - 1.

References offsets.

Referenced by components(), and Opm::tarjan().

operator[]()

std::span< const int > Opm::StronglyConnectedComponents::operator[] ( int  k ) const

inline

The vertices of a component.

Parameters

k	Component index, 0 <= k < numComponents().

Returns

A view of the vertices of component k.

References offsets, and vertices.

Member Data Documentation

componentOf

std::vector<int> Opm::StronglyConnectedComponents::componentOf

The component each vertex belongs to.

Referenced by Opm::tarjan().

offsets

std::vector<int> Opm::StronglyConnectedComponents::offsets {0}

Start of each component in vertices, with the total vertex count as the final entry. Always has numComponents() + 1 entries.

Referenced by numComponents(), operator[](), and Opm::tarjan().

vertices

std::vector<int> Opm::StronglyConnectedComponents::vertices

All vertices, grouped by component. Component k occupies vertices[offsets[k]], ..., vertices[offsets[k + 1] - 1].

Referenced by operator[](), and Opm::tarjan().

---

The documentation for this struct was generated from the following file:

• Tarjan.hpp