#include <algorithm>#include <cstddef>#include <ranges>#include <span>#include <stdexcept>#include <string>#include <type_traits>#include <utility>#include <vector>
Go to the source code of this file.
Classes | |
| struct | Opm::StronglyConnectedComponents |
| The strongly connected components of a directed graph, as computed by tarjan(). More... | |
Namespaces | |
| namespace | Opm |
Functions | |
| template<class Graph > | |
| StronglyConnectedComponents | Opm::tarjan (const Graph &graph) |
| Compute the strongly connected components of a directed graph with Tarjan's algorithm. More... | |
Detailed Description
Tarjan's algorithm for the strongly connected components (SCCs) of a directed graph, see R. E. Tarjan, "Depth-first search and linear graph algorithms", SIAM J. Comput. 1(2), 1972, or https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
This is a new, independent C++ implementation of the same algorithm that existed in the legacy C-code, reorder transport solver in opm-simulators-legacy (authored by Jostein Natvig).
The intended use is to order the cells of a reservoir model for transport solves that follow the flow. Build the graph so that every cell has an edge to each of its upwind neighbours. The components are then returned with all upwind components first, so that solving them in the returned order only ever needs values that are already final:
- A component with one cell and no flow loop is solved with a single local solve.
- A component with several cells is a flow loop: its cells depend on each other and have to be solved together, either directly or iteratively.