This repository has been archived by the owner on Aug 5, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
fill.h
209 lines (175 loc) · 6.43 KB
/
fill.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
/**
* Implementation of the FILL algorithm described by Rose & Tarjan in
* "Algorithmic aspects of vertex elimination on graphs", plus other utility
* functions using the same algorithm.
*
* See: https://doi.org/10.1137/0205021
*/
#ifndef ALGO_FILL_H
#define ALGO_FILL_H
#include <utility>
#include <unordered_set>
#include <unordered_map>
#include "utils.h"
/**
* Compute the chordal completion of an ordered graph, directly adding new edges
* to the graph.
*
* @param g graph to compute the chordal completion of
* @param order ordered sequence of vertices of the graph
*
* @pre `g` is a simple, connected, undirected graph; `order` is an ordered
* sequence of the vertices of `g`
* @post `g` is the chordal completion of the original graph according to
* `order`
*/
template <class Graph>
void fill(Graph &g, const VertexOrder<Graph> &order) {
typedef typename VertexOrder<Graph>::value_type Vertex;
typedef typename VertexOrder<Graph>::size_type Index;
BOOST_CONCEPT_ASSERT((boost::MutableGraphConcept<Graph>));
BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<Graph>));
BOOST_CONCEPT_ASSERT((boost::AdjacencyGraphConcept<Graph>));
const auto n_vertices = boost::num_vertices(g);
std::unordered_map<Vertex, Index> index_of(n_vertices);
std::unordered_map<Vertex, std::unordered_set<Vertex>> succ(n_vertices);
for (Index i = 0; i < order.size(); i++)
index_of[order[i]] = i;
// Compute initial sets of successors: w is successor of v iff v--w and v
// comes before w in the given order
for (const auto v : iter_vertices(g)) {
for (const auto w : iter_neighbors(g, v)) {
if (index_of[v] < index_of[w])
succ[v].insert(w);
}
}
// For each vertex v in the order
for (auto it = order.begin(); it != order.end() - 1; it++) {
const Vertex v = *it;
Index min_index = n_vertices;
Vertex closest;
// Find the closest successor of v in the order
for (const auto w : succ[v]) {
if (index_of[w] < min_index)
min_index = index_of[w];
}
closest = order[min_index];
// Mark any other successor of v as a successor of closest and add edges
// to the graph as necessary (i.e. edges of the deficiency of v)
for (const auto w : succ[v]) {
if (w != closest && succ[closest].find(w) == succ[closest].end()) {
succ[closest].insert(w);
boost::add_edge(closest, w, g);
}
}
}
}
/**
* Compute the chordal completion of an ordered graph, and only return edges of
* the fill-in, without adding them to the graph. This is the same function as
* fill(), except it does not modify the graph and returns the edges instead.
*
* @param g graph to compute the chordal completion of
* @param order ordered sequence of vertices of the graph
* @return edges of the fill-in of the graph as pairs of vertices
*
* @pre `g` is a simple, connected, undirected graph; `order` is an ordered
* sequence of the vertices of `g`
*/
template <class Graph>
EdgeSet<Graph> fill_in(const Graph &g, const VertexOrder<Graph> &order) {
typedef typename VertexOrder<Graph>::value_type Vertex;
typedef typename VertexOrder<Graph>::size_type Index;
BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<Graph>));
BOOST_CONCEPT_ASSERT((boost::AdjacencyGraphConcept<Graph>));
const auto n_vertices = boost::num_vertices(g);
std::unordered_map<Vertex, Index> index_of(n_vertices);
std::unordered_map<Vertex, std::unordered_set<Vertex>> succ(n_vertices);
EdgeSet<Graph> fill_in_edges;
for (Index i = 0; i < order.size(); i++)
index_of[order[i]] = i;
// Compute initial sets of successors: w is successor of v iff v--w and v
// comes before w in the given order
for (const auto v : iter_vertices(g)) {
for (const auto w : iter_neighbors(g, v)) {
if (index_of[v] < index_of[w])
succ[v].insert(w);
}
}
// For each vertex v in the order
for (auto it = order.begin(); it != order.end() - 1; it++) {
const Vertex v = *it;
Index min_index = n_vertices;
Vertex closest;
// Find the closest successor of v in the order
for (const auto w : succ[v]) {
if (index_of[w] < min_index)
min_index = index_of[w];
}
closest = order[min_index];
// Mark any other successor of v as a successor of closest and add new
// edges to the fill-in as necessary
for (const auto w : succ[v]) {
if (w != closest && succ[closest].find(w) == succ[closest].end()) {
succ[closest].insert(w);
if (closest < w)
fill_in_edges.emplace(closest, w);
else
fill_in_edges.emplace(w, closest);
}
}
}
return fill_in_edges;
}
/**
* Determine whether the provided order is a perfect elimination order for the
* given graph. This is the same function as fill(), only that it stops as soon
* as possible without modifying the graph.
*
* @param g graph
* @param order ordered sequence of vertices of the graph
* @return true/false whether `order` is a perfect elimination order for `g`
*
* @pre `g` is a simple, connected, undirected graph
*/
template <class Graph>
bool is_perfect_elimination_order(const Graph &g, const VertexOrder<Graph> &order) {
typedef typename VertexOrder<Graph>::value_type Vertex;
typedef typename VertexOrder<Graph>::size_type Index;
BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<Graph>));
BOOST_CONCEPT_ASSERT((boost::AdjacencyGraphConcept<Graph>));
const auto n_vertices = boost::num_vertices(g);
std::unordered_map<Vertex, Index> index_of(n_vertices);
std::unordered_map<Vertex, std::unordered_set<Vertex>> succ(n_vertices);
for (Index i = 0; i < order.size(); i++)
index_of[order[i]] = i;
// Compute initial sets of successors: w is successor of v iff v--w and v
// comes before w in the given order
for (const auto v : iter_vertices(g)) {
for (const auto w : iter_neighbors(g, v)) {
if (index_of[v] < index_of[w])
succ[v].insert(w);
}
}
// For each vertex v in the order
for (auto it = order.begin(); it != order.end() - 1; it++) {
const Vertex v = *it;
Index min_index = n_vertices;
Vertex closest;
// Find the closest successor of v in the order
for (const auto w : succ[v]) {
if (index_of[w] < min_index)
min_index = index_of[w];
}
closest = order[min_index];
// If there is any other successor w of v that is not also a successor
// of closest then the given order was not a perfect elimination order,
// as the edge closest--w would be part of the deficiency of v.
for (const auto w : succ[v]) {
if (w != closest && succ[closest].find(w) == succ[closest].end())
return false;
}
}
return true;
}
#endif // ALGO_FILL_H