ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
FixSystemGraph.h
Go to the documentation of this file.
1/**
2 * @file FixSystemGraph.h
3 * @brief Strongly connected components of the dependency graph of an
4 * equation system (a recursive query, see @c gate_fixsystem).
5 */
6#ifndef FIX_SYSTEM_GRAPH_H
7#define FIX_SYSTEM_GRAPH_H
8
9#include <algorithm>
10#include <cstddef>
11#include <utility>
12#include <vector>
13
14/**
15 * @brief Strongly connected components of a directed graph, in the order
16 * in which equations along its edges can be solved.
17 *
18 * Iterative Tarjan. With an edge @c j → @c i when the equation of @c i
19 * reads unknown @c j, every component comes after the components it
20 * reads, so solving them in the returned order only ever reads solved
21 * unknowns, or those of the component itself.
22 *
23 * @param out @c out[j] lists the vertices with an edge from @c j.
24 * @return The components, each a list of vertices.
25 */
26inline std::vector<std::vector<std::size_t> >
27fixSystemComponents(const std::vector<std::vector<std::size_t> > &out)
28{
29 const std::size_t n = out.size();
30 const std::size_t UNSEEN = static_cast<std::size_t>(-1);
31 std::vector<std::size_t> index(n, UNSEEN), low(n, 0);
32 std::vector<char> on_stack(n, 0);
33 std::vector<std::size_t> tstack;
34 std::vector<std::vector<std::size_t> > comps;
35 std::size_t counter = 0;
36
37 for(std::size_t root = 0; root < n; ++root) {
38 if(index[root] != UNSEEN)
39 continue;
40 std::vector<std::pair<std::size_t, std::size_t> > call{{root, 0}};
41 index[root] = low[root] = counter++;
42 tstack.push_back(root);
43 on_stack[root] = 1;
44 while(!call.empty()) {
45 const std::size_t v = call.back().first;
46 std::size_t &k = call.back().second;
47 if(k < out[v].size()) {
48 const std::size_t u = out[v][k++];
49 if(index[u] == UNSEEN) {
50 index[u] = low[u] = counter++;
51 tstack.push_back(u);
52 on_stack[u] = 1;
53 call.emplace_back(u, 0);
54 } else if(on_stack[u])
55 low[v] = std::min(low[v], index[u]);
56 continue;
57 }
58 if(low[v] == index[v]) {
59 std::vector<std::size_t> comp;
60 std::size_t u;
61 do {
62 u = tstack.back();
63 tstack.pop_back();
64 on_stack[u] = 0;
65 comp.push_back(u);
66 } while(u != v);
67 comps.push_back(std::move(comp));
68 }
69 call.pop_back();
70 if(!call.empty())
71 low[call.back().first] = std::min(low[call.back().first], low[v]);
72 }
73 }
74 /* Tarjan emits a component after every component reachable from it,
75 * i.e. after those that read it: reverse into solving order. */
76 std::reverse(comps.begin(), comps.end());
77 return comps;
78}
79
80#endif /* FIX_SYSTEM_GRAPH_H */
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 ca...