ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
FixSystemGraph.h File Reference

Strongly connected components of the dependency graph of an equation system (a recursive query, see gate_fixsystem). More...

#include <algorithm>
#include <cstddef>
#include <utility>
#include <vector>
Include dependency graph for FixSystemGraph.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

std::vector< std::vector< std::size_t > > fixSystemComponents (const std::vector< std::vector< std::size_t > > &out)
 Strongly connected components of a directed graph, in the order in which equations along its edges can be solved.

Detailed Description

Strongly connected components of the dependency graph of an equation system (a recursive query, see gate_fixsystem).

Definition in file FixSystemGraph.h.

Function Documentation

◆ fixSystemComponents()

std::vector< std::vector< std::size_t > > fixSystemComponents ( const std::vector< std::vector< std::size_t > > & out)
inline

Strongly connected components of a directed graph, in the order in which equations along its edges can be solved.

Iterative Tarjan. With an edge j → i when the equation of i reads unknown j, every component comes after the components it reads, so solving them in the returned order only ever reads solved unknowns, or those of the component itself.

Parameters
outout[j] lists the vertices with an edge from j.
Returns
The components, each a list of vertices.

Definition at line 27 of file FixSystemGraph.h.

Here is the caller graph for this function: