deba@2480
|
1 |
/* -*- C++ -*-
|
deba@2480
|
2 |
*
|
deba@2480
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
deba@2480
|
4 |
*
|
deba@2480
|
5 |
* Copyright (C) 2003-2007
|
deba@2480
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@2480
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@2480
|
8 |
*
|
deba@2480
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@2480
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@2480
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@2480
|
12 |
*
|
deba@2480
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@2480
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@2480
|
15 |
* purpose.
|
deba@2480
|
16 |
*
|
deba@2480
|
17 |
*/
|
deba@2480
|
18 |
#ifndef LEMON_PLANARITY_H
|
deba@2480
|
19 |
#define LEMON_PLANARITY_H
|
deba@2480
|
20 |
|
deba@2480
|
21 |
/// \ingroup graph_prop
|
deba@2480
|
22 |
/// \file
|
deba@2480
|
23 |
/// \brief Planarity checking, embedding
|
deba@2480
|
24 |
|
deba@2480
|
25 |
#include <vector>
|
deba@2480
|
26 |
#include <list>
|
deba@2480
|
27 |
|
deba@2480
|
28 |
#include <lemon/dfs.h>
|
deba@2480
|
29 |
#include <lemon/radix_sort.h>
|
deba@2480
|
30 |
#include <lemon/maps.h>
|
deba@2480
|
31 |
#include <lemon/path.h>
|
deba@2480
|
32 |
|
deba@2480
|
33 |
|
deba@2480
|
34 |
namespace lemon {
|
deba@2480
|
35 |
|
deba@2480
|
36 |
namespace _planarity_bits {
|
deba@2480
|
37 |
|
deba@2480
|
38 |
template <typename UGraph>
|
deba@2480
|
39 |
struct PlanarityVisitor : DfsVisitor<UGraph> {
|
deba@2480
|
40 |
|
deba@2480
|
41 |
typedef typename UGraph::Node Node;
|
deba@2480
|
42 |
typedef typename UGraph::Edge Edge;
|
deba@2480
|
43 |
|
deba@2480
|
44 |
typedef typename UGraph::template NodeMap<Edge> PredMap;
|
deba@2480
|
45 |
|
deba@2480
|
46 |
typedef typename UGraph::template UEdgeMap<bool> TreeMap;
|
deba@2480
|
47 |
|
deba@2480
|
48 |
typedef typename UGraph::template NodeMap<int> OrderMap;
|
deba@2480
|
49 |
typedef std::vector<Node> OrderList;
|
deba@2480
|
50 |
|
deba@2480
|
51 |
typedef typename UGraph::template NodeMap<int> LowMap;
|
deba@2480
|
52 |
typedef typename UGraph::template NodeMap<int> AncestorMap;
|
deba@2480
|
53 |
|
deba@2480
|
54 |
PlanarityVisitor(const UGraph& ugraph,
|
deba@2480
|
55 |
PredMap& pred_map, TreeMap& tree_map,
|
deba@2480
|
56 |
OrderMap& order_map, OrderList& order_list,
|
deba@2480
|
57 |
AncestorMap& ancestor_map, LowMap& low_map)
|
deba@2480
|
58 |
: _ugraph(ugraph), _pred_map(pred_map), _tree_map(tree_map),
|
deba@2480
|
59 |
_order_map(order_map), _order_list(order_list),
|
deba@2480
|
60 |
_ancestor_map(ancestor_map), _low_map(low_map) {}
|
deba@2480
|
61 |
|
deba@2480
|
62 |
void reach(const Node& node) {
|
deba@2480
|
63 |
_order_map[node] = _order_list.size();
|
deba@2480
|
64 |
_low_map[node] = _order_list.size();
|
deba@2480
|
65 |
_ancestor_map[node] = _order_list.size();
|
deba@2480
|
66 |
_order_list.push_back(node);
|
deba@2480
|
67 |
}
|
deba@2480
|
68 |
|
deba@2480
|
69 |
void discover(const Edge& edge) {
|
deba@2480
|
70 |
Node source = _ugraph.source(edge);
|
deba@2480
|
71 |
Node target = _ugraph.target(edge);
|
deba@2480
|
72 |
|
deba@2480
|
73 |
_tree_map[edge] = true;
|
deba@2480
|
74 |
_pred_map[target] = edge;
|
deba@2480
|
75 |
}
|
deba@2480
|
76 |
|
deba@2480
|
77 |
void examine(const Edge& edge) {
|
deba@2480
|
78 |
Node source = _ugraph.source(edge);
|
deba@2480
|
79 |
Node target = _ugraph.target(edge);
|
deba@2480
|
80 |
|
deba@2480
|
81 |
if (_order_map[target] < _order_map[source] && !_tree_map[edge]) {
|
deba@2480
|
82 |
if (_low_map[source] > _order_map[target]) {
|
deba@2480
|
83 |
_low_map[source] = _order_map[target];
|
deba@2480
|
84 |
}
|
deba@2480
|
85 |
if (_ancestor_map[source] > _order_map[target]) {
|
deba@2480
|
86 |
_ancestor_map[source] = _order_map[target];
|
deba@2480
|
87 |
}
|
deba@2480
|
88 |
}
|
deba@2480
|
89 |
}
|
deba@2480
|
90 |
|
deba@2480
|
91 |
void backtrack(const Edge& edge) {
|
deba@2480
|
92 |
Node source = _ugraph.source(edge);
|
deba@2480
|
93 |
Node target = _ugraph.target(edge);
|
deba@2480
|
94 |
|
deba@2480
|
95 |
if (_low_map[source] > _low_map[target]) {
|
deba@2480
|
96 |
_low_map[source] = _low_map[target];
|
deba@2480
|
97 |
}
|
deba@2480
|
98 |
}
|
deba@2480
|
99 |
|
deba@2480
|
100 |
const UGraph& _ugraph;
|
deba@2480
|
101 |
PredMap& _pred_map;
|
deba@2480
|
102 |
TreeMap& _tree_map;
|
deba@2480
|
103 |
OrderMap& _order_map;
|
deba@2480
|
104 |
OrderList& _order_list;
|
deba@2480
|
105 |
AncestorMap& _ancestor_map;
|
deba@2480
|
106 |
LowMap& _low_map;
|
deba@2480
|
107 |
};
|
deba@2480
|
108 |
|
deba@2480
|
109 |
template <typename UGraph, bool embedding = true>
|
deba@2480
|
110 |
struct NodeDataNode {
|
deba@2480
|
111 |
int prev, next;
|
deba@2480
|
112 |
int visited;
|
deba@2480
|
113 |
typename UGraph::Edge first;
|
deba@2480
|
114 |
bool inverted;
|
deba@2480
|
115 |
};
|
deba@2480
|
116 |
|
deba@2480
|
117 |
template <typename UGraph>
|
deba@2480
|
118 |
struct NodeDataNode<UGraph, false> {
|
deba@2480
|
119 |
int prev, next;
|
deba@2480
|
120 |
int visited;
|
deba@2480
|
121 |
};
|
deba@2480
|
122 |
|
deba@2480
|
123 |
template <typename UGraph>
|
deba@2480
|
124 |
struct ChildListNode {
|
deba@2480
|
125 |
typedef typename UGraph::Node Node;
|
deba@2480
|
126 |
Node first;
|
deba@2480
|
127 |
Node prev, next;
|
deba@2480
|
128 |
};
|
deba@2480
|
129 |
|
deba@2480
|
130 |
template <typename UGraph>
|
deba@2480
|
131 |
struct EdgeListNode {
|
deba@2480
|
132 |
typename UGraph::Edge prev, next;
|
deba@2480
|
133 |
};
|
deba@2480
|
134 |
|
deba@2480
|
135 |
}
|
deba@2480
|
136 |
|
deba@2480
|
137 |
/// \ingroup graph_prop
|
deba@2480
|
138 |
///
|
deba@2480
|
139 |
/// \brief Planarity checking of an undirected simple graph
|
deba@2480
|
140 |
///
|
deba@2480
|
141 |
/// This class implements the Boyer-Myrvold algorithm for planar
|
deba@2480
|
142 |
/// checking of an undirected graph. This class is a simplified
|
deba@2480
|
143 |
/// version of the PlanarEmbedding algorithm class, and it does
|
deba@2480
|
144 |
/// provide neither embedding nor kuratowski subdivisons.
|
deba@2480
|
145 |
template <typename UGraph>
|
deba@2480
|
146 |
class PlanarityChecking {
|
deba@2480
|
147 |
private:
|
deba@2480
|
148 |
|
deba@2480
|
149 |
UGRAPH_TYPEDEFS(typename UGraph)
|
deba@2480
|
150 |
|
deba@2480
|
151 |
const UGraph& _ugraph;
|
deba@2480
|
152 |
|
deba@2480
|
153 |
private:
|
deba@2480
|
154 |
|
deba@2480
|
155 |
typedef typename UGraph::template NodeMap<Edge> PredMap;
|
deba@2480
|
156 |
|
deba@2480
|
157 |
typedef typename UGraph::template UEdgeMap<bool> TreeMap;
|
deba@2480
|
158 |
|
deba@2480
|
159 |
typedef typename UGraph::template NodeMap<int> OrderMap;
|
deba@2480
|
160 |
typedef std::vector<Node> OrderList;
|
deba@2480
|
161 |
|
deba@2480
|
162 |
typedef typename UGraph::template NodeMap<int> LowMap;
|
deba@2480
|
163 |
typedef typename UGraph::template NodeMap<int> AncestorMap;
|
deba@2480
|
164 |
|
deba@2480
|
165 |
typedef _planarity_bits::NodeDataNode<UGraph> NodeDataNode;
|
deba@2480
|
166 |
typedef std::vector<NodeDataNode> NodeData;
|
deba@2480
|
167 |
|
deba@2480
|
168 |
typedef _planarity_bits::ChildListNode<UGraph> ChildListNode;
|
deba@2480
|
169 |
typedef typename UGraph::template NodeMap<ChildListNode> ChildLists;
|
deba@2480
|
170 |
|
deba@2480
|
171 |
typedef typename UGraph::template NodeMap<std::list<int> > MergeRoots;
|
deba@2480
|
172 |
|
deba@2480
|
173 |
typedef typename UGraph::template NodeMap<bool> EmbedEdge;
|
deba@2480
|
174 |
|
deba@2480
|
175 |
public:
|
deba@2480
|
176 |
|
deba@2480
|
177 |
/// \brief Constructor
|
deba@2480
|
178 |
///
|
deba@2480
|
179 |
/// \warining The graph should be simple, i.e. parallel and loop edge
|
deba@2480
|
180 |
/// free.
|
deba@2480
|
181 |
PlanarityChecking(const UGraph& ugraph) : _ugraph(ugraph) {}
|
deba@2480
|
182 |
|
deba@2480
|
183 |
/// \brief Runs the algorithm.
|
deba@2480
|
184 |
///
|
deba@2480
|
185 |
/// Runs the algorithm.
|
deba@2480
|
186 |
/// \return %True when the graph is planar.
|
deba@2481
|
187 |
bool run() {
|
deba@2480
|
188 |
typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor;
|
deba@2480
|
189 |
|
deba@2480
|
190 |
PredMap pred_map(_ugraph, INVALID);
|
deba@2480
|
191 |
TreeMap tree_map(_ugraph, false);
|
deba@2480
|
192 |
|
deba@2480
|
193 |
OrderMap order_map(_ugraph, -1);
|
deba@2480
|
194 |
OrderList order_list;
|
deba@2480
|
195 |
|
deba@2480
|
196 |
AncestorMap ancestor_map(_ugraph, -1);
|
deba@2480
|
197 |
LowMap low_map(_ugraph, -1);
|
deba@2480
|
198 |
|
deba@2480
|
199 |
Visitor visitor(_ugraph, pred_map, tree_map,
|
deba@2480
|
200 |
order_map, order_list, ancestor_map, low_map);
|
deba@2480
|
201 |
DfsVisit<UGraph, Visitor> visit(_ugraph, visitor);
|
deba@2480
|
202 |
visit.run();
|
deba@2480
|
203 |
|
deba@2480
|
204 |
ChildLists child_lists(_ugraph);
|
deba@2480
|
205 |
createChildLists(tree_map, order_map, low_map, child_lists);
|
deba@2480
|
206 |
|
deba@2480
|
207 |
NodeData node_data(2 * order_list.size());
|
deba@2480
|
208 |
|
deba@2480
|
209 |
EmbedEdge embed_edge(_ugraph, false);
|
deba@2480
|
210 |
|
deba@2480
|
211 |
MergeRoots merge_roots(_ugraph);
|
deba@2480
|
212 |
|
deba@2480
|
213 |
for (int i = order_list.size() - 1; i >= 0; --i) {
|
deba@2480
|
214 |
|
deba@2480
|
215 |
Node node = order_list[i];
|
deba@2480
|
216 |
|
deba@2480
|
217 |
Node source = node;
|
deba@2480
|
218 |
for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
|
deba@2480
|
219 |
Node target = _ugraph.target(e);
|
deba@2480
|
220 |
|
deba@2480
|
221 |
if (order_map[source] < order_map[target] && tree_map[e]) {
|
deba@2481
|
222 |
initFace(target, node_data, order_map, order_list);
|
deba@2480
|
223 |
}
|
deba@2480
|
224 |
}
|
deba@2480
|
225 |
|
deba@2480
|
226 |
for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
|
deba@2480
|
227 |
Node target = _ugraph.target(e);
|
deba@2480
|
228 |
|
deba@2480
|
229 |
if (order_map[source] < order_map[target] && !tree_map[e]) {
|
deba@2480
|
230 |
embed_edge[target] = true;
|
deba@2480
|
231 |
walkUp(target, source, i, pred_map, low_map,
|
deba@2480
|
232 |
order_map, order_list, node_data, merge_roots);
|
deba@2480
|
233 |
}
|
deba@2480
|
234 |
}
|
deba@2480
|
235 |
|
deba@2480
|
236 |
for (typename MergeRoots::Value::iterator it =
|
deba@2480
|
237 |
merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
|
deba@2480
|
238 |
int rn = *it;
|
deba@2480
|
239 |
walkDown(rn, i, node_data, order_list, child_lists,
|
deba@2480
|
240 |
ancestor_map, low_map, embed_edge, merge_roots);
|
deba@2480
|
241 |
}
|
deba@2480
|
242 |
merge_roots[node].clear();
|
deba@2480
|
243 |
|
deba@2480
|
244 |
for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
|
deba@2480
|
245 |
Node target = _ugraph.target(e);
|
deba@2480
|
246 |
|
deba@2480
|
247 |
if (order_map[source] < order_map[target] && !tree_map[e]) {
|
deba@2480
|
248 |
if (embed_edge[target]) {
|
deba@2480
|
249 |
return false;
|
deba@2480
|
250 |
}
|
deba@2480
|
251 |
}
|
deba@2480
|
252 |
}
|
deba@2480
|
253 |
}
|
deba@2480
|
254 |
|
deba@2480
|
255 |
return true;
|
deba@2480
|
256 |
}
|
deba@2480
|
257 |
|
deba@2480
|
258 |
private:
|
deba@2480
|
259 |
|
deba@2480
|
260 |
void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
|
deba@2480
|
261 |
const LowMap& low_map, ChildLists& child_lists) {
|
deba@2480
|
262 |
|
deba@2480
|
263 |
for (NodeIt n(_ugraph); n != INVALID; ++n) {
|
deba@2480
|
264 |
Node source = n;
|
deba@2480
|
265 |
|
deba@2480
|
266 |
std::vector<Node> targets;
|
deba@2480
|
267 |
for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
|
deba@2480
|
268 |
Node target = _ugraph.target(e);
|
deba@2480
|
269 |
|
deba@2480
|
270 |
if (order_map[source] < order_map[target] && tree_map[e]) {
|
deba@2480
|
271 |
targets.push_back(target);
|
deba@2480
|
272 |
}
|
deba@2480
|
273 |
}
|
deba@2480
|
274 |
|
deba@2480
|
275 |
if (targets.size() == 0) {
|
deba@2480
|
276 |
child_lists[source].first = INVALID;
|
deba@2480
|
277 |
} else if (targets.size() == 1) {
|
deba@2480
|
278 |
child_lists[source].first = targets[0];
|
deba@2480
|
279 |
child_lists[targets[0]].prev = INVALID;
|
deba@2480
|
280 |
child_lists[targets[0]].next = INVALID;
|
deba@2480
|
281 |
} else {
|
deba@2480
|
282 |
radixSort(targets.begin(), targets.end(), mapFunctor(low_map));
|
deba@2480
|
283 |
for (int i = 1; i < int(targets.size()); ++i) {
|
deba@2480
|
284 |
child_lists[targets[i]].prev = targets[i - 1];
|
deba@2480
|
285 |
child_lists[targets[i - 1]].next = targets[i];
|
deba@2480
|
286 |
}
|
deba@2480
|
287 |
child_lists[targets.back()].next = INVALID;
|
deba@2480
|
288 |
child_lists[targets.front()].prev = INVALID;
|
deba@2480
|
289 |
child_lists[source].first = targets.front();
|
deba@2480
|
290 |
}
|
deba@2480
|
291 |
}
|
deba@2480
|
292 |
}
|
deba@2480
|
293 |
|
deba@2480
|
294 |
void walkUp(const Node& node, Node root, int rorder,
|
deba@2480
|
295 |
const PredMap& pred_map, const LowMap& low_map,
|
deba@2480
|
296 |
const OrderMap& order_map, const OrderList& order_list,
|
deba@2480
|
297 |
NodeData& node_data, MergeRoots& merge_roots) {
|
deba@2480
|
298 |
|
deba@2480
|
299 |
int na, nb;
|
deba@2480
|
300 |
bool da, db;
|
deba@2480
|
301 |
|
deba@2480
|
302 |
na = nb = order_map[node];
|
deba@2480
|
303 |
da = true; db = false;
|
deba@2480
|
304 |
|
deba@2480
|
305 |
while (true) {
|
deba@2480
|
306 |
|
deba@2480
|
307 |
if (node_data[na].visited == rorder) break;
|
deba@2480
|
308 |
if (node_data[nb].visited == rorder) break;
|
deba@2480
|
309 |
|
deba@2480
|
310 |
node_data[na].visited = rorder;
|
deba@2480
|
311 |
node_data[nb].visited = rorder;
|
deba@2480
|
312 |
|
deba@2480
|
313 |
int rn = -1;
|
deba@2480
|
314 |
|
deba@2480
|
315 |
if (na >= int(order_list.size())) {
|
deba@2480
|
316 |
rn = na;
|
deba@2480
|
317 |
} else if (nb >= int(order_list.size())) {
|
deba@2480
|
318 |
rn = nb;
|
deba@2480
|
319 |
}
|
deba@2480
|
320 |
|
deba@2480
|
321 |
if (rn == -1) {
|
deba@2480
|
322 |
int nn;
|
deba@2480
|
323 |
|
deba@2480
|
324 |
nn = da ? node_data[na].prev : node_data[na].next;
|
deba@2480
|
325 |
da = node_data[nn].prev != na;
|
deba@2480
|
326 |
na = nn;
|
deba@2480
|
327 |
|
deba@2480
|
328 |
nn = db ? node_data[nb].prev : node_data[nb].next;
|
deba@2480
|
329 |
db = node_data[nn].prev != nb;
|
deba@2480
|
330 |
nb = nn;
|
deba@2480
|
331 |
|
deba@2480
|
332 |
} else {
|
deba@2480
|
333 |
|
deba@2480
|
334 |
Node rep = order_list[rn - order_list.size()];
|
deba@2480
|
335 |
Node parent = _ugraph.source(pred_map[rep]);
|
deba@2480
|
336 |
|
deba@2480
|
337 |
if (low_map[rep] < rorder) {
|
deba@2480
|
338 |
merge_roots[parent].push_back(rn);
|
deba@2480
|
339 |
} else {
|
deba@2480
|
340 |
merge_roots[parent].push_front(rn);
|
deba@2480
|
341 |
}
|
deba@2480
|
342 |
|
deba@2480
|
343 |
if (parent != root) {
|
deba@2480
|
344 |
na = nb = order_map[parent];
|
deba@2480
|
345 |
da = true; db = false;
|
deba@2480
|
346 |
} else {
|
deba@2480
|
347 |
break;
|
deba@2480
|
348 |
}
|
deba@2480
|
349 |
}
|
deba@2480
|
350 |
}
|
deba@2480
|
351 |
}
|
deba@2480
|
352 |
|
deba@2480
|
353 |
void walkDown(int rn, int rorder, NodeData& node_data,
|
deba@2480
|
354 |
OrderList& order_list, ChildLists& child_lists,
|
deba@2480
|
355 |
AncestorMap& ancestor_map, LowMap& low_map,
|
deba@2480
|
356 |
EmbedEdge& embed_edge, MergeRoots& merge_roots) {
|
deba@2480
|
357 |
|
deba@2480
|
358 |
std::vector<std::pair<int, bool> > merge_stack;
|
deba@2480
|
359 |
|
deba@2480
|
360 |
for (int di = 0; di < 2; ++di) {
|
deba@2480
|
361 |
bool rd = di == 0;
|
deba@2480
|
362 |
int pn = rn;
|
deba@2480
|
363 |
int n = rd ? node_data[rn].next : node_data[rn].prev;
|
deba@2480
|
364 |
|
deba@2480
|
365 |
while (n != rn) {
|
deba@2480
|
366 |
|
deba@2480
|
367 |
Node node = order_list[n];
|
deba@2480
|
368 |
|
deba@2480
|
369 |
if (embed_edge[node]) {
|
deba@2480
|
370 |
|
deba@2480
|
371 |
// Merging components on the critical path
|
deba@2480
|
372 |
while (!merge_stack.empty()) {
|
deba@2480
|
373 |
|
deba@2480
|
374 |
// Component root
|
deba@2480
|
375 |
int cn = merge_stack.back().first;
|
deba@2480
|
376 |
bool cd = merge_stack.back().second;
|
deba@2480
|
377 |
merge_stack.pop_back();
|
deba@2480
|
378 |
|
deba@2480
|
379 |
// Parent of component
|
deba@2480
|
380 |
int dn = merge_stack.back().first;
|
deba@2480
|
381 |
bool dd = merge_stack.back().second;
|
deba@2480
|
382 |
merge_stack.pop_back();
|
deba@2480
|
383 |
|
deba@2480
|
384 |
Node parent = order_list[dn];
|
deba@2480
|
385 |
|
deba@2480
|
386 |
// Erasing from merge_roots
|
deba@2480
|
387 |
merge_roots[parent].pop_front();
|
deba@2480
|
388 |
|
deba@2480
|
389 |
Node child = order_list[cn - order_list.size()];
|
deba@2480
|
390 |
|
deba@2480
|
391 |
// Erasing from child_lists
|
deba@2480
|
392 |
if (child_lists[child].prev != INVALID) {
|
deba@2480
|
393 |
child_lists[child_lists[child].prev].next =
|
deba@2480
|
394 |
child_lists[child].next;
|
deba@2480
|
395 |
} else {
|
deba@2480
|
396 |
child_lists[parent].first = child_lists[child].next;
|
deba@2480
|
397 |
}
|
deba@2480
|
398 |
|
deba@2480
|
399 |
if (child_lists[child].next != INVALID) {
|
deba@2480
|
400 |
child_lists[child_lists[child].next].prev =
|
deba@2480
|
401 |
child_lists[child].prev;
|
deba@2480
|
402 |
}
|
deba@2480
|
403 |
|
deba@2480
|
404 |
// Merging external faces
|
deba@2480
|
405 |
{
|
deba@2480
|
406 |
int en = cn;
|
deba@2480
|
407 |
cn = cd ? node_data[cn].prev : node_data[cn].next;
|
deba@2480
|
408 |
cd = node_data[cn].next == en;
|
deba@2480
|
409 |
|
deba@2480
|
410 |
}
|
deba@2480
|
411 |
|
deba@2480
|
412 |
if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
|
deba@2480
|
413 |
if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
|
deba@2480
|
414 |
|
deba@2480
|
415 |
}
|
deba@2480
|
416 |
|
deba@2480
|
417 |
bool d = pn == node_data[n].prev;
|
deba@2480
|
418 |
|
deba@2480
|
419 |
if (node_data[n].prev == node_data[n].next &&
|
deba@2480
|
420 |
node_data[n].inverted) {
|
deba@2480
|
421 |
d = !d;
|
deba@2480
|
422 |
}
|
deba@2480
|
423 |
|
deba@2480
|
424 |
// Embedding edge into external face
|
deba@2480
|
425 |
if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
|
deba@2480
|
426 |
if (d) node_data[n].prev = rn; else node_data[n].next = rn;
|
deba@2480
|
427 |
pn = rn;
|
deba@2480
|
428 |
|
deba@2480
|
429 |
embed_edge[order_list[n]] = false;
|
deba@2480
|
430 |
}
|
deba@2480
|
431 |
|
deba@2480
|
432 |
if (!merge_roots[node].empty()) {
|
deba@2480
|
433 |
|
deba@2480
|
434 |
bool d = pn == node_data[n].prev;
|
deba@2480
|
435 |
|
deba@2480
|
436 |
merge_stack.push_back(std::make_pair(n, d));
|
deba@2480
|
437 |
|
deba@2480
|
438 |
int rn = merge_roots[node].front();
|
deba@2480
|
439 |
|
deba@2480
|
440 |
int xn = node_data[rn].next;
|
deba@2480
|
441 |
Node xnode = order_list[xn];
|
deba@2480
|
442 |
|
deba@2480
|
443 |
int yn = node_data[rn].prev;
|
deba@2480
|
444 |
Node ynode = order_list[yn];
|
deba@2480
|
445 |
|
deba@2480
|
446 |
bool rd;
|
deba@2480
|
447 |
if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
|
deba@2480
|
448 |
rd = true;
|
deba@2480
|
449 |
} else if (!external(ynode, rorder, child_lists,
|
deba@2480
|
450 |
ancestor_map, low_map)) {
|
deba@2480
|
451 |
rd = false;
|
deba@2480
|
452 |
} else if (pertinent(xnode, embed_edge, merge_roots)) {
|
deba@2480
|
453 |
rd = true;
|
deba@2480
|
454 |
} else {
|
deba@2480
|
455 |
rd = false;
|
deba@2480
|
456 |
}
|
deba@2480
|
457 |
|
deba@2480
|
458 |
merge_stack.push_back(std::make_pair(rn, rd));
|
deba@2480
|
459 |
|
deba@2480
|
460 |
pn = rn;
|
deba@2480
|
461 |
n = rd ? xn : yn;
|
deba@2480
|
462 |
|
deba@2480
|
463 |
} else if (!external(node, rorder, child_lists,
|
deba@2480
|
464 |
ancestor_map, low_map)) {
|
deba@2480
|
465 |
int nn = (node_data[n].next != pn ?
|
deba@2480
|
466 |
node_data[n].next : node_data[n].prev);
|
deba@2480
|
467 |
|
deba@2480
|
468 |
bool nd = n == node_data[nn].prev;
|
deba@2480
|
469 |
|
deba@2480
|
470 |
if (nd) node_data[nn].prev = pn;
|
deba@2480
|
471 |
else node_data[nn].next = pn;
|
deba@2480
|
472 |
|
deba@2480
|
473 |
if (n == node_data[pn].prev) node_data[pn].prev = nn;
|
deba@2480
|
474 |
else node_data[pn].next = nn;
|
deba@2480
|
475 |
|
deba@2480
|
476 |
node_data[nn].inverted =
|
deba@2480
|
477 |
(node_data[nn].prev == node_data[nn].next && nd != rd);
|
deba@2480
|
478 |
|
deba@2480
|
479 |
n = nn;
|
deba@2480
|
480 |
}
|
deba@2480
|
481 |
else break;
|
deba@2480
|
482 |
|
deba@2480
|
483 |
}
|
deba@2480
|
484 |
|
deba@2480
|
485 |
if (!merge_stack.empty() || n == rn) {
|
deba@2480
|
486 |
break;
|
deba@2480
|
487 |
}
|
deba@2480
|
488 |
}
|
deba@2480
|
489 |
}
|
deba@2480
|
490 |
|
deba@2480
|
491 |
void initFace(const Node& node, NodeData& node_data,
|
deba@2481
|
492 |
const OrderMap& order_map, const OrderList& order_list) {
|
deba@2480
|
493 |
int n = order_map[node];
|
deba@2480
|
494 |
int rn = n + order_list.size();
|
deba@2480
|
495 |
|
deba@2480
|
496 |
node_data[n].next = node_data[n].prev = rn;
|
deba@2480
|
497 |
node_data[rn].next = node_data[rn].prev = n;
|
deba@2480
|
498 |
|
deba@2480
|
499 |
node_data[n].visited = order_list.size();
|
deba@2480
|
500 |
node_data[rn].visited = order_list.size();
|
deba@2480
|
501 |
|
deba@2480
|
502 |
}
|
deba@2480
|
503 |
|
deba@2480
|
504 |
bool external(const Node& node, int rorder,
|
deba@2480
|
505 |
ChildLists& child_lists, AncestorMap& ancestor_map,
|
deba@2480
|
506 |
LowMap& low_map) {
|
deba@2480
|
507 |
Node child = child_lists[node].first;
|
deba@2480
|
508 |
|
deba@2480
|
509 |
if (child != INVALID) {
|
deba@2480
|
510 |
if (low_map[child] < rorder) return true;
|
deba@2480
|
511 |
}
|
deba@2480
|
512 |
|
deba@2480
|
513 |
if (ancestor_map[node] < rorder) return true;
|
deba@2480
|
514 |
|
deba@2480
|
515 |
return false;
|
deba@2480
|
516 |
}
|
deba@2480
|
517 |
|
deba@2480
|
518 |
bool pertinent(const Node& node, const EmbedEdge& embed_edge,
|
deba@2480
|
519 |
const MergeRoots& merge_roots) {
|
deba@2480
|
520 |
return !merge_roots[node].empty() || embed_edge[node];
|
deba@2480
|
521 |
}
|
deba@2480
|
522 |
|
deba@2480
|
523 |
};
|
deba@2480
|
524 |
|
deba@2480
|
525 |
/// \ingroup graph_prop
|
deba@2480
|
526 |
///
|
deba@2480
|
527 |
/// \brief Planar embedding of an undirected simple graph
|
deba@2480
|
528 |
///
|
deba@2480
|
529 |
/// This class implements the Boyer-Myrvold algorithm for planar
|
deba@2480
|
530 |
/// embedding of an undirected graph. The planar embeding is an
|
deba@2480
|
531 |
/// ordering of the outgoing edges in each node, which is a possible
|
deba@2480
|
532 |
/// configuration to draw the graph in the plane. If there is not
|
deba@2480
|
533 |
/// such ordering then the graph contains a \f$ K_5 \f$ (full graph
|
deba@2480
|
534 |
/// with 5 nodes) or an \f$ K_{3,3} \f$ (complete bipartite graph on
|
deba@2480
|
535 |
/// 3 ANode and 3 BNode) subdivision.
|
deba@2480
|
536 |
///
|
deba@2480
|
537 |
/// The current implementation calculates an embedding or an
|
deba@2480
|
538 |
/// Kuratowski subdivision if the graph is not planar. The running
|
deba@2480
|
539 |
/// time of the algorithm is \f$ O(n) \f$.
|
deba@2480
|
540 |
template <typename UGraph>
|
deba@2480
|
541 |
class PlanarEmbedding {
|
deba@2480
|
542 |
private:
|
deba@2480
|
543 |
|
deba@2480
|
544 |
UGRAPH_TYPEDEFS(typename UGraph)
|
deba@2480
|
545 |
|
deba@2480
|
546 |
const UGraph& _ugraph;
|
deba@2480
|
547 |
typename UGraph::template EdgeMap<Edge> _embedding;
|
deba@2480
|
548 |
|
deba@2480
|
549 |
typename UGraph::template UEdgeMap<bool> _kuratowski;
|
deba@2480
|
550 |
|
deba@2480
|
551 |
private:
|
deba@2480
|
552 |
|
deba@2480
|
553 |
typedef typename UGraph::template NodeMap<Edge> PredMap;
|
deba@2480
|
554 |
|
deba@2480
|
555 |
typedef typename UGraph::template UEdgeMap<bool> TreeMap;
|
deba@2480
|
556 |
|
deba@2480
|
557 |
typedef typename UGraph::template NodeMap<int> OrderMap;
|
deba@2480
|
558 |
typedef std::vector<Node> OrderList;
|
deba@2480
|
559 |
|
deba@2480
|
560 |
typedef typename UGraph::template NodeMap<int> LowMap;
|
deba@2480
|
561 |
typedef typename UGraph::template NodeMap<int> AncestorMap;
|
deba@2480
|
562 |
|
deba@2480
|
563 |
typedef _planarity_bits::NodeDataNode<UGraph> NodeDataNode;
|
deba@2480
|
564 |
typedef std::vector<NodeDataNode> NodeData;
|
deba@2480
|
565 |
|
deba@2480
|
566 |
typedef _planarity_bits::ChildListNode<UGraph> ChildListNode;
|
deba@2480
|
567 |
typedef typename UGraph::template NodeMap<ChildListNode> ChildLists;
|
deba@2480
|
568 |
|
deba@2480
|
569 |
typedef typename UGraph::template NodeMap<std::list<int> > MergeRoots;
|
deba@2480
|
570 |
|
deba@2480
|
571 |
typedef typename UGraph::template NodeMap<Edge> EmbedEdge;
|
deba@2480
|
572 |
|
deba@2480
|
573 |
typedef _planarity_bits::EdgeListNode<UGraph> EdgeListNode;
|
deba@2480
|
574 |
typedef typename UGraph::template EdgeMap<EdgeListNode> EdgeLists;
|
deba@2480
|
575 |
|
deba@2480
|
576 |
typedef typename UGraph::template NodeMap<bool> FlipMap;
|
deba@2480
|
577 |
|
deba@2480
|
578 |
typedef typename UGraph::template NodeMap<int> TypeMap;
|
deba@2480
|
579 |
|
deba@2480
|
580 |
enum IsolatorNodeType {
|
deba@2480
|
581 |
HIGHX = 6, LOWX = 7,
|
deba@2480
|
582 |
HIGHY = 8, LOWY = 9,
|
deba@2480
|
583 |
ROOT = 10, PERTINENT = 11,
|
deba@2480
|
584 |
INTERNAL = 12
|
deba@2480
|
585 |
};
|
deba@2480
|
586 |
|
deba@2480
|
587 |
public:
|
deba@2480
|
588 |
|
deba@2480
|
589 |
/// \brief Constructor
|
deba@2480
|
590 |
///
|
deba@2480
|
591 |
/// \warining The graph should be simple, i.e. parallel and loop edge
|
deba@2480
|
592 |
/// free.
|
deba@2480
|
593 |
PlanarEmbedding(const UGraph& ugraph)
|
deba@2480
|
594 |
: _ugraph(ugraph), _embedding(_ugraph), _kuratowski(ugraph, false) {}
|
deba@2480
|
595 |
|
deba@2480
|
596 |
/// \brief Runs the algorithm.
|
deba@2480
|
597 |
///
|
deba@2480
|
598 |
/// Runs the algorithm.
|
deba@2480
|
599 |
/// \param kuratowski If the parameter is false, then the
|
deba@2480
|
600 |
/// algorithm does not calculate the isolate Kuratowski
|
deba@2480
|
601 |
/// subdivisions.
|
deba@2480
|
602 |
///\return %True when the graph is planar.
|
deba@2480
|
603 |
bool run(bool kuratowski = true) {
|
deba@2480
|
604 |
typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor;
|
deba@2480
|
605 |
|
deba@2480
|
606 |
PredMap pred_map(_ugraph, INVALID);
|
deba@2480
|
607 |
TreeMap tree_map(_ugraph, false);
|
deba@2480
|
608 |
|
deba@2480
|
609 |
OrderMap order_map(_ugraph, -1);
|
deba@2480
|
610 |
OrderList order_list;
|
deba@2480
|
611 |
|
deba@2480
|
612 |
AncestorMap ancestor_map(_ugraph, -1);
|
deba@2480
|
613 |
LowMap low_map(_ugraph, -1);
|
deba@2480
|
614 |
|
deba@2480
|
615 |
Visitor visitor(_ugraph, pred_map, tree_map,
|
deba@2480
|
616 |
order_map, order_list, ancestor_map, low_map);
|
deba@2480
|
617 |
DfsVisit<UGraph, Visitor> visit(_ugraph, visitor);
|
deba@2480
|
618 |
visit.run();
|
deba@2480
|
619 |
|
deba@2480
|
620 |
ChildLists child_lists(_ugraph);
|
deba@2480
|
621 |
createChildLists(tree_map, order_map, low_map, child_lists);
|
deba@2480
|
622 |
|
deba@2480
|
623 |
NodeData node_data(2 * order_list.size());
|
deba@2480
|
624 |
|
deba@2480
|
625 |
EmbedEdge embed_edge(_ugraph, INVALID);
|
deba@2480
|
626 |
|
deba@2480
|
627 |
MergeRoots merge_roots(_ugraph);
|
deba@2480
|
628 |
|
deba@2480
|
629 |
EdgeLists edge_lists(_ugraph);
|
deba@2480
|
630 |
|
deba@2480
|
631 |
FlipMap flip_map(_ugraph, false);
|
deba@2480
|
632 |
|
deba@2480
|
633 |
for (int i = order_list.size() - 1; i >= 0; --i) {
|
deba@2480
|
634 |
|
deba@2480
|
635 |
Node node = order_list[i];
|
deba@2480
|
636 |
|
deba@2480
|
637 |
node_data[i].first = INVALID;
|
deba@2480
|
638 |
|
deba@2480
|
639 |
Node source = node;
|
deba@2480
|
640 |
for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
|
deba@2480
|
641 |
Node target = _ugraph.target(e);
|
deba@2480
|
642 |
|
deba@2480
|
643 |
if (order_map[source] < order_map[target] && tree_map[e]) {
|
deba@2480
|
644 |
initFace(target, edge_lists, node_data,
|
deba@2480
|
645 |
pred_map, order_map, order_list);
|
deba@2480
|
646 |
}
|
deba@2480
|
647 |
}
|
deba@2480
|
648 |
|
deba@2480
|
649 |
for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
|
deba@2480
|
650 |
Node target = _ugraph.target(e);
|
deba@2480
|
651 |
|
deba@2480
|
652 |
if (order_map[source] < order_map[target] && !tree_map[e]) {
|
deba@2480
|
653 |
embed_edge[target] = e;
|
deba@2480
|
654 |
walkUp(target, source, i, pred_map, low_map,
|
deba@2480
|
655 |
order_map, order_list, node_data, merge_roots);
|
deba@2480
|
656 |
}
|
deba@2480
|
657 |
}
|
deba@2480
|
658 |
|
deba@2480
|
659 |
for (typename MergeRoots::Value::iterator it =
|
deba@2480
|
660 |
merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
|
deba@2480
|
661 |
int rn = *it;
|
deba@2480
|
662 |
walkDown(rn, i, node_data, edge_lists, flip_map, order_list,
|
deba@2480
|
663 |
child_lists, ancestor_map, low_map, embed_edge, merge_roots);
|
deba@2480
|
664 |
}
|
deba@2480
|
665 |
merge_roots[node].clear();
|
deba@2480
|
666 |
|
deba@2480
|
667 |
for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
|
deba@2480
|
668 |
Node target = _ugraph.target(e);
|
deba@2480
|
669 |
|
deba@2480
|
670 |
if (order_map[source] < order_map[target] && !tree_map[e]) {
|
deba@2480
|
671 |
if (embed_edge[target] != INVALID) {
|
deba@2480
|
672 |
if (kuratowski) {
|
deba@2480
|
673 |
isolateKuratowski(e, node_data, edge_lists, flip_map,
|
deba@2480
|
674 |
order_map, order_list, pred_map, child_lists,
|
deba@2480
|
675 |
ancestor_map, low_map,
|
deba@2480
|
676 |
embed_edge, merge_roots);
|
deba@2480
|
677 |
}
|
deba@2480
|
678 |
return false;
|
deba@2480
|
679 |
}
|
deba@2480
|
680 |
}
|
deba@2480
|
681 |
}
|
deba@2480
|
682 |
}
|
deba@2480
|
683 |
|
deba@2480
|
684 |
for (int i = 0; i < int(order_list.size()); ++i) {
|
deba@2480
|
685 |
|
deba@2480
|
686 |
mergeRemainingFaces(order_list[i], node_data, order_list, order_map,
|
deba@2480
|
687 |
child_lists, edge_lists);
|
deba@2480
|
688 |
storeEmbedding(order_list[i], node_data, order_map, pred_map,
|
deba@2480
|
689 |
edge_lists, flip_map);
|
deba@2480
|
690 |
}
|
deba@2480
|
691 |
|
deba@2480
|
692 |
return true;
|
deba@2480
|
693 |
}
|
deba@2480
|
694 |
|
deba@2480
|
695 |
/// \brief Gives back the successor of an edge
|
deba@2480
|
696 |
///
|
deba@2480
|
697 |
/// Gives back the successor of an edge. This function makes
|
deba@2480
|
698 |
/// possible to query the cyclic order of the outgoing edges from
|
deba@2480
|
699 |
/// a node.
|
deba@2480
|
700 |
Edge next(const Edge& edge) const {
|
deba@2480
|
701 |
return _embedding[edge];
|
deba@2480
|
702 |
}
|
deba@2480
|
703 |
|
deba@2480
|
704 |
/// \brief Gives back true when the undirected edge is in the
|
deba@2480
|
705 |
/// kuratowski subdivision
|
deba@2480
|
706 |
///
|
deba@2480
|
707 |
/// Gives back true when the undirected edge is in the kuratowski
|
deba@2480
|
708 |
/// subdivision
|
deba@2480
|
709 |
bool kuratowski(const UEdge& uedge) {
|
deba@2480
|
710 |
return _kuratowski[uedge];
|
deba@2480
|
711 |
}
|
deba@2480
|
712 |
|
deba@2480
|
713 |
private:
|
deba@2480
|
714 |
|
deba@2480
|
715 |
void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
|
deba@2480
|
716 |
const LowMap& low_map, ChildLists& child_lists) {
|
deba@2480
|
717 |
|
deba@2480
|
718 |
for (NodeIt n(_ugraph); n != INVALID; ++n) {
|
deba@2480
|
719 |
Node source = n;
|
deba@2480
|
720 |
|
deba@2480
|
721 |
std::vector<Node> targets;
|
deba@2480
|
722 |
for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
|
deba@2480
|
723 |
Node target = _ugraph.target(e);
|
deba@2480
|
724 |
|
deba@2480
|
725 |
if (order_map[source] < order_map[target] && tree_map[e]) {
|
deba@2480
|
726 |
targets.push_back(target);
|
deba@2480
|
727 |
}
|
deba@2480
|
728 |
}
|
deba@2480
|
729 |
|
deba@2480
|
730 |
if (targets.size() == 0) {
|
deba@2480
|
731 |
child_lists[source].first = INVALID;
|
deba@2480
|
732 |
} else if (targets.size() == 1) {
|
deba@2480
|
733 |
child_lists[source].first = targets[0];
|
deba@2480
|
734 |
child_lists[targets[0]].prev = INVALID;
|
deba@2480
|
735 |
child_lists[targets[0]].next = INVALID;
|
deba@2480
|
736 |
} else {
|
deba@2480
|
737 |
radixSort(targets.begin(), targets.end(), mapFunctor(low_map));
|
deba@2480
|
738 |
for (int i = 1; i < int(targets.size()); ++i) {
|
deba@2480
|
739 |
child_lists[targets[i]].prev = targets[i - 1];
|
deba@2480
|
740 |
child_lists[targets[i - 1]].next = targets[i];
|
deba@2480
|
741 |
}
|
deba@2480
|
742 |
child_lists[targets.back()].next = INVALID;
|
deba@2480
|
743 |
child_lists[targets.front()].prev = INVALID;
|
deba@2480
|
744 |
child_lists[source].first = targets.front();
|
deba@2480
|
745 |
}
|
deba@2480
|
746 |
}
|
deba@2480
|
747 |
}
|
deba@2480
|
748 |
|
deba@2480
|
749 |
void walkUp(const Node& node, Node root, int rorder,
|
deba@2480
|
750 |
const PredMap& pred_map, const LowMap& low_map,
|
deba@2480
|
751 |
const OrderMap& order_map, const OrderList& order_list,
|
deba@2480
|
752 |
NodeData& node_data, MergeRoots& merge_roots) {
|
deba@2480
|
753 |
|
deba@2480
|
754 |
int na, nb;
|
deba@2480
|
755 |
bool da, db;
|
deba@2480
|
756 |
|
deba@2480
|
757 |
na = nb = order_map[node];
|
deba@2480
|
758 |
da = true; db = false;
|
deba@2480
|
759 |
|
deba@2480
|
760 |
while (true) {
|
deba@2480
|
761 |
|
deba@2480
|
762 |
if (node_data[na].visited == rorder) break;
|
deba@2480
|
763 |
if (node_data[nb].visited == rorder) break;
|
deba@2480
|
764 |
|
deba@2480
|
765 |
node_data[na].visited = rorder;
|
deba@2480
|
766 |
node_data[nb].visited = rorder;
|
deba@2480
|
767 |
|
deba@2480
|
768 |
int rn = -1;
|
deba@2480
|
769 |
|
deba@2480
|
770 |
if (na >= int(order_list.size())) {
|
deba@2480
|
771 |
rn = na;
|
deba@2480
|
772 |
} else if (nb >= int(order_list.size())) {
|
deba@2480
|
773 |
rn = nb;
|
deba@2480
|
774 |
}
|
deba@2480
|
775 |
|
deba@2480
|
776 |
if (rn == -1) {
|
deba@2480
|
777 |
int nn;
|
deba@2480
|
778 |
|
deba@2480
|
779 |
nn = da ? node_data[na].prev : node_data[na].next;
|
deba@2480
|
780 |
da = node_data[nn].prev != na;
|
deba@2480
|
781 |
na = nn;
|
deba@2480
|
782 |
|
deba@2480
|
783 |
nn = db ? node_data[nb].prev : node_data[nb].next;
|
deba@2480
|
784 |
db = node_data[nn].prev != nb;
|
deba@2480
|
785 |
nb = nn;
|
deba@2480
|
786 |
|
deba@2480
|
787 |
} else {
|
deba@2480
|
788 |
|
deba@2480
|
789 |
Node rep = order_list[rn - order_list.size()];
|
deba@2480
|
790 |
Node parent = _ugraph.source(pred_map[rep]);
|
deba@2480
|
791 |
|
deba@2480
|
792 |
if (low_map[rep] < rorder) {
|
deba@2480
|
793 |
merge_roots[parent].push_back(rn);
|
deba@2480
|
794 |
} else {
|
deba@2480
|
795 |
merge_roots[parent].push_front(rn);
|
deba@2480
|
796 |
}
|
deba@2480
|
797 |
|
deba@2480
|
798 |
if (parent != root) {
|
deba@2480
|
799 |
na = nb = order_map[parent];
|
deba@2480
|
800 |
da = true; db = false;
|
deba@2480
|
801 |
} else {
|
deba@2480
|
802 |
break;
|
deba@2480
|
803 |
}
|
deba@2480
|
804 |
}
|
deba@2480
|
805 |
}
|
deba@2480
|
806 |
}
|
deba@2480
|
807 |
|
deba@2480
|
808 |
void walkDown(int rn, int rorder, NodeData& node_data,
|
deba@2480
|
809 |
EdgeLists& edge_lists, FlipMap& flip_map,
|
deba@2480
|
810 |
OrderList& order_list, ChildLists& child_lists,
|
deba@2480
|
811 |
AncestorMap& ancestor_map, LowMap& low_map,
|
deba@2480
|
812 |
EmbedEdge& embed_edge, MergeRoots& merge_roots) {
|
deba@2480
|
813 |
|
deba@2480
|
814 |
std::vector<std::pair<int, bool> > merge_stack;
|
deba@2480
|
815 |
|
deba@2480
|
816 |
for (int di = 0; di < 2; ++di) {
|
deba@2480
|
817 |
bool rd = di == 0;
|
deba@2480
|
818 |
int pn = rn;
|
deba@2480
|
819 |
int n = rd ? node_data[rn].next : node_data[rn].prev;
|
deba@2480
|
820 |
|
deba@2480
|
821 |
while (n != rn) {
|
deba@2480
|
822 |
|
deba@2480
|
823 |
Node node = order_list[n];
|
deba@2480
|
824 |
|
deba@2480
|
825 |
if (embed_edge[node] != INVALID) {
|
deba@2480
|
826 |
|
deba@2480
|
827 |
// Merging components on the critical path
|
deba@2480
|
828 |
while (!merge_stack.empty()) {
|
deba@2480
|
829 |
|
deba@2480
|
830 |
// Component root
|
deba@2480
|
831 |
int cn = merge_stack.back().first;
|
deba@2480
|
832 |
bool cd = merge_stack.back().second;
|
deba@2480
|
833 |
merge_stack.pop_back();
|
deba@2480
|
834 |
|
deba@2480
|
835 |
// Parent of component
|
deba@2480
|
836 |
int dn = merge_stack.back().first;
|
deba@2480
|
837 |
bool dd = merge_stack.back().second;
|
deba@2480
|
838 |
merge_stack.pop_back();
|
deba@2480
|
839 |
|
deba@2480
|
840 |
Node parent = order_list[dn];
|
deba@2480
|
841 |
|
deba@2480
|
842 |
// Erasing from merge_roots
|
deba@2480
|
843 |
merge_roots[parent].pop_front();
|
deba@2480
|
844 |
|
deba@2480
|
845 |
Node child = order_list[cn - order_list.size()];
|
deba@2480
|
846 |
|
deba@2480
|
847 |
// Erasing from child_lists
|
deba@2480
|
848 |
if (child_lists[child].prev != INVALID) {
|
deba@2480
|
849 |
child_lists[child_lists[child].prev].next =
|
deba@2480
|
850 |
child_lists[child].next;
|
deba@2480
|
851 |
} else {
|
deba@2480
|
852 |
child_lists[parent].first = child_lists[child].next;
|
deba@2480
|
853 |
}
|
deba@2480
|
854 |
|
deba@2480
|
855 |
if (child_lists[child].next != INVALID) {
|
deba@2480
|
856 |
child_lists[child_lists[child].next].prev =
|
deba@2480
|
857 |
child_lists[child].prev;
|
deba@2480
|
858 |
}
|
deba@2480
|
859 |
|
deba@2480
|
860 |
// Merging edges + flipping
|
deba@2480
|
861 |
Edge de = node_data[dn].first;
|
deba@2480
|
862 |
Edge ce = node_data[cn].first;
|
deba@2480
|
863 |
|
deba@2480
|
864 |
flip_map[order_list[cn - order_list.size()]] = cd != dd;
|
deba@2480
|
865 |
if (cd != dd) {
|
deba@2480
|
866 |
std::swap(edge_lists[ce].prev, edge_lists[ce].next);
|
deba@2480
|
867 |
ce = edge_lists[ce].prev;
|
deba@2480
|
868 |
std::swap(edge_lists[ce].prev, edge_lists[ce].next);
|
deba@2480
|
869 |
}
|
deba@2480
|
870 |
|
deba@2480
|
871 |
{
|
deba@2480
|
872 |
Edge dne = edge_lists[de].next;
|
deba@2480
|
873 |
Edge cne = edge_lists[ce].next;
|
deba@2480
|
874 |
|
deba@2480
|
875 |
edge_lists[de].next = cne;
|
deba@2480
|
876 |
edge_lists[ce].next = dne;
|
deba@2480
|
877 |
|
deba@2480
|
878 |
edge_lists[dne].prev = ce;
|
deba@2480
|
879 |
edge_lists[cne].prev = de;
|
deba@2480
|
880 |
}
|
deba@2480
|
881 |
|
deba@2480
|
882 |
if (dd) {
|
deba@2480
|
883 |
node_data[dn].first = ce;
|
deba@2480
|
884 |
}
|
deba@2480
|
885 |
|
deba@2480
|
886 |
// Merging external faces
|
deba@2480
|
887 |
{
|
deba@2480
|
888 |
int en = cn;
|
deba@2480
|
889 |
cn = cd ? node_data[cn].prev : node_data[cn].next;
|
deba@2480
|
890 |
cd = node_data[cn].next == en;
|
deba@2480
|
891 |
|
deba@2480
|
892 |
if (node_data[cn].prev == node_data[cn].next &&
|
deba@2480
|
893 |
node_data[cn].inverted) {
|
deba@2480
|
894 |
cd = !cd;
|
deba@2480
|
895 |
}
|
deba@2480
|
896 |
}
|
deba@2480
|
897 |
|
deba@2480
|
898 |
if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
|
deba@2480
|
899 |
if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
|
deba@2480
|
900 |
|
deba@2480
|
901 |
}
|
deba@2480
|
902 |
|
deba@2480
|
903 |
bool d = pn == node_data[n].prev;
|
deba@2480
|
904 |
|
deba@2480
|
905 |
if (node_data[n].prev == node_data[n].next &&
|
deba@2480
|
906 |
node_data[n].inverted) {
|
deba@2480
|
907 |
d = !d;
|
deba@2480
|
908 |
}
|
deba@2480
|
909 |
|
deba@2480
|
910 |
// Add new edge
|
deba@2480
|
911 |
{
|
deba@2480
|
912 |
Edge edge = embed_edge[node];
|
deba@2480
|
913 |
Edge re = node_data[rn].first;
|
deba@2480
|
914 |
|
deba@2480
|
915 |
edge_lists[edge_lists[re].next].prev = edge;
|
deba@2480
|
916 |
edge_lists[edge].next = edge_lists[re].next;
|
deba@2480
|
917 |
edge_lists[edge].prev = re;
|
deba@2480
|
918 |
edge_lists[re].next = edge;
|
deba@2480
|
919 |
|
deba@2480
|
920 |
if (!rd) {
|
deba@2480
|
921 |
node_data[rn].first = edge;
|
deba@2480
|
922 |
}
|
deba@2480
|
923 |
|
deba@2480
|
924 |
Edge rev = _ugraph.oppositeEdge(edge);
|
deba@2480
|
925 |
Edge e = node_data[n].first;
|
deba@2480
|
926 |
|
deba@2480
|
927 |
edge_lists[edge_lists[e].next].prev = rev;
|
deba@2480
|
928 |
edge_lists[rev].next = edge_lists[e].next;
|
deba@2480
|
929 |
edge_lists[rev].prev = e;
|
deba@2480
|
930 |
edge_lists[e].next = rev;
|
deba@2480
|
931 |
|
deba@2480
|
932 |
if (d) {
|
deba@2480
|
933 |
node_data[n].first = rev;
|
deba@2480
|
934 |
}
|
deba@2480
|
935 |
|
deba@2480
|
936 |
}
|
deba@2480
|
937 |
|
deba@2480
|
938 |
// Embedding edge into external face
|
deba@2480
|
939 |
if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
|
deba@2480
|
940 |
if (d) node_data[n].prev = rn; else node_data[n].next = rn;
|
deba@2480
|
941 |
pn = rn;
|
deba@2480
|
942 |
|
deba@2480
|
943 |
embed_edge[order_list[n]] = INVALID;
|
deba@2480
|
944 |
}
|
deba@2480
|
945 |
|
deba@2480
|
946 |
if (!merge_roots[node].empty()) {
|
deba@2480
|
947 |
|
deba@2480
|
948 |
bool d = pn == node_data[n].prev;
|
deba@2480
|
949 |
if (node_data[n].prev == node_data[n].next &&
|
deba@2480
|
950 |
node_data[n].inverted) {
|
deba@2480
|
951 |
d = !d;
|
deba@2480
|
952 |
}
|
deba@2480
|
953 |
|
deba@2480
|
954 |
merge_stack.push_back(std::make_pair(n, d));
|
deba@2480
|
955 |
|
deba@2480
|
956 |
int rn = merge_roots[node].front();
|
deba@2480
|
957 |
|
deba@2480
|
958 |
int xn = node_data[rn].next;
|
deba@2480
|
959 |
Node xnode = order_list[xn];
|
deba@2480
|
960 |
|
deba@2480
|
961 |
int yn = node_data[rn].prev;
|
deba@2480
|
962 |
Node ynode = order_list[yn];
|
deba@2480
|
963 |
|
deba@2480
|
964 |
bool rd;
|
deba@2480
|
965 |
if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
|
deba@2480
|
966 |
rd = true;
|
deba@2480
|
967 |
} else if (!external(ynode, rorder, child_lists,
|
deba@2480
|
968 |
ancestor_map, low_map)) {
|
deba@2480
|
969 |
rd = false;
|
deba@2480
|
970 |
} else if (pertinent(xnode, embed_edge, merge_roots)) {
|
deba@2480
|
971 |
rd = true;
|
deba@2480
|
972 |
} else {
|
deba@2480
|
973 |
rd = false;
|
deba@2480
|
974 |
}
|
deba@2480
|
975 |
|
deba@2480
|
976 |
merge_stack.push_back(std::make_pair(rn, rd));
|
deba@2480
|
977 |
|
deba@2480
|
978 |
pn = rn;
|
deba@2480
|
979 |
n = rd ? xn : yn;
|
deba@2480
|
980 |
|
deba@2480
|
981 |
} else if (!external(node, rorder, child_lists,
|
deba@2480
|
982 |
ancestor_map, low_map)) {
|
deba@2480
|
983 |
int nn = (node_data[n].next != pn ?
|
deba@2480
|
984 |
node_data[n].next : node_data[n].prev);
|
deba@2480
|
985 |
|
deba@2480
|
986 |
bool nd = n == node_data[nn].prev;
|
deba@2480
|
987 |
|
deba@2480
|
988 |
if (nd) node_data[nn].prev = pn;
|
deba@2480
|
989 |
else node_data[nn].next = pn;
|
deba@2480
|
990 |
|
deba@2480
|
991 |
if (n == node_data[pn].prev) node_data[pn].prev = nn;
|
deba@2480
|
992 |
else node_data[pn].next = nn;
|
deba@2480
|
993 |
|
deba@2480
|
994 |
node_data[nn].inverted =
|
deba@2480
|
995 |
(node_data[nn].prev == node_data[nn].next && nd != rd);
|
deba@2480
|
996 |
|
deba@2480
|
997 |
n = nn;
|
deba@2480
|
998 |
}
|
deba@2480
|
999 |
else break;
|
deba@2480
|
1000 |
|
deba@2480
|
1001 |
}
|
deba@2480
|
1002 |
|
deba@2480
|
1003 |
if (!merge_stack.empty() || n == rn) {
|
deba@2480
|
1004 |
break;
|
deba@2480
|
1005 |
}
|
deba@2480
|
1006 |
}
|
deba@2480
|
1007 |
}
|
deba@2480
|
1008 |
|
deba@2480
|
1009 |
void initFace(const Node& node, EdgeLists& edge_lists,
|
deba@2480
|
1010 |
NodeData& node_data, const PredMap& pred_map,
|
deba@2480
|
1011 |
const OrderMap& order_map, const OrderList& order_list) {
|
deba@2480
|
1012 |
int n = order_map[node];
|
deba@2480
|
1013 |
int rn = n + order_list.size();
|
deba@2480
|
1014 |
|
deba@2480
|
1015 |
node_data[n].next = node_data[n].prev = rn;
|
deba@2480
|
1016 |
node_data[rn].next = node_data[rn].prev = n;
|
deba@2480
|
1017 |
|
deba@2480
|
1018 |
node_data[n].visited = order_list.size();
|
deba@2480
|
1019 |
node_data[rn].visited = order_list.size();
|
deba@2480
|
1020 |
|
deba@2480
|
1021 |
node_data[n].inverted = false;
|
deba@2480
|
1022 |
node_data[rn].inverted = false;
|
deba@2480
|
1023 |
|
deba@2480
|
1024 |
Edge edge = pred_map[node];
|
deba@2480
|
1025 |
Edge rev = _ugraph.oppositeEdge(edge);
|
deba@2480
|
1026 |
|
deba@2480
|
1027 |
node_data[rn].first = edge;
|
deba@2480
|
1028 |
node_data[n].first = rev;
|
deba@2480
|
1029 |
|
deba@2480
|
1030 |
edge_lists[edge].prev = edge;
|
deba@2480
|
1031 |
edge_lists[edge].next = edge;
|
deba@2480
|
1032 |
|
deba@2480
|
1033 |
edge_lists[rev].prev = rev;
|
deba@2480
|
1034 |
edge_lists[rev].next = rev;
|
deba@2480
|
1035 |
|
deba@2480
|
1036 |
}
|
deba@2480
|
1037 |
|
deba@2480
|
1038 |
void mergeRemainingFaces(const Node& node, NodeData& node_data,
|
deba@2480
|
1039 |
OrderList& order_list, OrderMap& order_map,
|
deba@2480
|
1040 |
ChildLists& child_lists, EdgeLists& edge_lists) {
|
deba@2480
|
1041 |
while (child_lists[node].first != INVALID) {
|
deba@2480
|
1042 |
int dd = order_map[node];
|
deba@2480
|
1043 |
Node child = child_lists[node].first;
|
deba@2480
|
1044 |
int cd = order_map[child] + order_list.size();
|
deba@2480
|
1045 |
child_lists[node].first = child_lists[child].next;
|
deba@2480
|
1046 |
|
deba@2480
|
1047 |
Edge de = node_data[dd].first;
|
deba@2480
|
1048 |
Edge ce = node_data[cd].first;
|
deba@2480
|
1049 |
|
deba@2480
|
1050 |
if (de != INVALID) {
|
deba@2480
|
1051 |
Edge dne = edge_lists[de].next;
|
deba@2480
|
1052 |
Edge cne = edge_lists[ce].next;
|
deba@2480
|
1053 |
|
deba@2480
|
1054 |
edge_lists[de].next = cne;
|
deba@2480
|
1055 |
edge_lists[ce].next = dne;
|
deba@2480
|
1056 |
|
deba@2480
|
1057 |
edge_lists[dne].prev = ce;
|
deba@2480
|
1058 |
edge_lists[cne].prev = de;
|
deba@2480
|
1059 |
}
|
deba@2480
|
1060 |
|
deba@2480
|
1061 |
node_data[dd].first = ce;
|
deba@2480
|
1062 |
|
deba@2480
|
1063 |
}
|
deba@2480
|
1064 |
}
|
deba@2480
|
1065 |
|
deba@2480
|
1066 |
void storeEmbedding(const Node& node, NodeData& node_data,
|
deba@2480
|
1067 |
OrderMap& order_map, PredMap& pred_map,
|
deba@2480
|
1068 |
EdgeLists& edge_lists, FlipMap& flip_map) {
|
deba@2480
|
1069 |
|
deba@2480
|
1070 |
if (node_data[order_map[node]].first == INVALID) return;
|
deba@2480
|
1071 |
|
deba@2480
|
1072 |
if (pred_map[node] != INVALID) {
|
deba@2480
|
1073 |
Node source = _ugraph.source(pred_map[node]);
|
deba@2480
|
1074 |
flip_map[node] = flip_map[node] != flip_map[source];
|
deba@2480
|
1075 |
}
|
deba@2480
|
1076 |
|
deba@2480
|
1077 |
Edge first = node_data[order_map[node]].first;
|
deba@2480
|
1078 |
Edge prev = first;
|
deba@2480
|
1079 |
|
deba@2480
|
1080 |
Edge edge = flip_map[node] ?
|
deba@2480
|
1081 |
edge_lists[prev].prev : edge_lists[prev].next;
|
deba@2480
|
1082 |
|
deba@2480
|
1083 |
_embedding[prev] = edge;
|
deba@2480
|
1084 |
|
deba@2480
|
1085 |
while (edge != first) {
|
deba@2480
|
1086 |
Edge next = edge_lists[edge].prev == prev ?
|
deba@2480
|
1087 |
edge_lists[edge].next : edge_lists[edge].prev;
|
deba@2480
|
1088 |
prev = edge; edge = next;
|
deba@2480
|
1089 |
_embedding[prev] = edge;
|
deba@2480
|
1090 |
}
|
deba@2480
|
1091 |
}
|
deba@2480
|
1092 |
|
deba@2480
|
1093 |
|
deba@2480
|
1094 |
bool external(const Node& node, int rorder,
|
deba@2480
|
1095 |
ChildLists& child_lists, AncestorMap& ancestor_map,
|
deba@2480
|
1096 |
LowMap& low_map) {
|
deba@2480
|
1097 |
Node child = child_lists[node].first;
|
deba@2480
|
1098 |
|
deba@2480
|
1099 |
if (child != INVALID) {
|
deba@2480
|
1100 |
if (low_map[child] < rorder) return true;
|
deba@2480
|
1101 |
}
|
deba@2480
|
1102 |
|
deba@2480
|
1103 |
if (ancestor_map[node] < rorder) return true;
|
deba@2480
|
1104 |
|
deba@2480
|
1105 |
return false;
|
deba@2480
|
1106 |
}
|
deba@2480
|
1107 |
|
deba@2480
|
1108 |
bool pertinent(const Node& node, const EmbedEdge& embed_edge,
|
deba@2480
|
1109 |
const MergeRoots& merge_roots) {
|
deba@2480
|
1110 |
return !merge_roots[node].empty() || embed_edge[node] != INVALID;
|
deba@2480
|
1111 |
}
|
deba@2480
|
1112 |
|
deba@2480
|
1113 |
int lowPoint(const Node& node, OrderMap& order_map, ChildLists& child_lists,
|
deba@2480
|
1114 |
AncestorMap& ancestor_map, LowMap& low_map) {
|
deba@2480
|
1115 |
int low_point;
|
deba@2480
|
1116 |
|
deba@2480
|
1117 |
Node child = child_lists[node].first;
|
deba@2480
|
1118 |
|
deba@2480
|
1119 |
if (child != INVALID) {
|
deba@2480
|
1120 |
low_point = low_map[child];
|
deba@2480
|
1121 |
} else {
|
deba@2480
|
1122 |
low_point = order_map[node];
|
deba@2480
|
1123 |
}
|
deba@2480
|
1124 |
|
deba@2480
|
1125 |
if (low_point > ancestor_map[node]) {
|
deba@2480
|
1126 |
low_point = ancestor_map[node];
|
deba@2480
|
1127 |
}
|
deba@2480
|
1128 |
|
deba@2480
|
1129 |
return low_point;
|
deba@2480
|
1130 |
}
|
deba@2480
|
1131 |
|
deba@2480
|
1132 |
int findComponentRoot(Node root, Node node, ChildLists& child_lists,
|
deba@2480
|
1133 |
OrderMap& order_map, OrderList& order_list) {
|
deba@2480
|
1134 |
|
deba@2480
|
1135 |
int order = order_map[root];
|
deba@2480
|
1136 |
int norder = order_map[node];
|
deba@2480
|
1137 |
|
deba@2480
|
1138 |
Node child = child_lists[root].first;
|
deba@2480
|
1139 |
while (child != INVALID) {
|
deba@2480
|
1140 |
int corder = order_map[child];
|
deba@2480
|
1141 |
if (corder > order && corder < norder) {
|
deba@2480
|
1142 |
order = corder;
|
deba@2480
|
1143 |
}
|
deba@2480
|
1144 |
child = child_lists[child].next;
|
deba@2480
|
1145 |
}
|
deba@2480
|
1146 |
return order + order_list.size();
|
deba@2480
|
1147 |
}
|
deba@2480
|
1148 |
|
deba@2480
|
1149 |
Node findPertinent(Node node, OrderMap& order_map, NodeData& node_data,
|
deba@2480
|
1150 |
EmbedEdge& embed_edge, MergeRoots& merge_roots) {
|
deba@2480
|
1151 |
Node wnode =_ugraph.target(node_data[order_map[node]].first);
|
deba@2480
|
1152 |
while (!pertinent(wnode, embed_edge, merge_roots)) {
|
deba@2480
|
1153 |
wnode = _ugraph.target(node_data[order_map[wnode]].first);
|
deba@2480
|
1154 |
}
|
deba@2480
|
1155 |
return wnode;
|
deba@2480
|
1156 |
}
|
deba@2480
|
1157 |
|
deba@2480
|
1158 |
|
deba@2480
|
1159 |
Node findExternal(Node node, int rorder, OrderMap& order_map,
|
deba@2480
|
1160 |
ChildLists& child_lists, AncestorMap& ancestor_map,
|
deba@2480
|
1161 |
LowMap& low_map, NodeData& node_data) {
|
deba@2480
|
1162 |
Node wnode =_ugraph.target(node_data[order_map[node]].first);
|
deba@2480
|
1163 |
while (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
|
deba@2480
|
1164 |
wnode = _ugraph.target(node_data[order_map[wnode]].first);
|
deba@2480
|
1165 |
}
|
deba@2480
|
1166 |
return wnode;
|
deba@2480
|
1167 |
}
|
deba@2480
|
1168 |
|
deba@2480
|
1169 |
void markCommonPath(Node node, int rorder, Node& wnode, Node& znode,
|
deba@2480
|
1170 |
OrderList& order_list, OrderMap& order_map,
|
deba@2480
|
1171 |
NodeData& node_data, EdgeLists& edge_lists,
|
deba@2480
|
1172 |
EmbedEdge& embed_edge, MergeRoots& merge_roots,
|
deba@2480
|
1173 |
ChildLists& child_lists, AncestorMap& ancestor_map,
|
deba@2480
|
1174 |
LowMap& low_map) {
|
deba@2480
|
1175 |
|
deba@2480
|
1176 |
Node cnode = node;
|
deba@2480
|
1177 |
Node pred = INVALID;
|
deba@2480
|
1178 |
|
deba@2480
|
1179 |
while (true) {
|
deba@2480
|
1180 |
|
deba@2480
|
1181 |
bool pert = pertinent(cnode, embed_edge, merge_roots);
|
deba@2480
|
1182 |
bool ext = external(cnode, rorder, child_lists, ancestor_map, low_map);
|
deba@2480
|
1183 |
|
deba@2480
|
1184 |
if (pert && ext) {
|
deba@2480
|
1185 |
if (!merge_roots[cnode].empty()) {
|
deba@2480
|
1186 |
int cn = merge_roots[cnode].back();
|
deba@2480
|
1187 |
|
deba@2480
|
1188 |
if (low_map[order_list[cn - order_list.size()]] < rorder) {
|
deba@2480
|
1189 |
Edge edge = node_data[cn].first;
|
deba@2480
|
1190 |
_kuratowski.set(edge, true);
|
deba@2480
|
1191 |
|
deba@2480
|
1192 |
pred = cnode;
|
deba@2480
|
1193 |
cnode = _ugraph.target(edge);
|
deba@2480
|
1194 |
|
deba@2480
|
1195 |
continue;
|
deba@2480
|
1196 |
}
|
deba@2480
|
1197 |
}
|
deba@2480
|
1198 |
wnode = znode = cnode;
|
deba@2480
|
1199 |
return;
|
deba@2480
|
1200 |
|
deba@2480
|
1201 |
} else if (pert) {
|
deba@2480
|
1202 |
wnode = cnode;
|
deba@2480
|
1203 |
|
deba@2480
|
1204 |
while (!external(cnode, rorder, child_lists, ancestor_map, low_map)) {
|
deba@2480
|
1205 |
Edge edge = node_data[order_map[cnode]].first;
|
deba@2480
|
1206 |
|
deba@2480
|
1207 |
if (_ugraph.target(edge) == pred) {
|
deba@2480
|
1208 |
edge = edge_lists[edge].next;
|
deba@2480
|
1209 |
}
|
deba@2480
|
1210 |
_kuratowski.set(edge, true);
|
deba@2480
|
1211 |
|
deba@2480
|
1212 |
Node next = _ugraph.target(edge);
|
deba@2480
|
1213 |
pred = cnode; cnode = next;
|
deba@2480
|
1214 |
}
|
deba@2480
|
1215 |
|
deba@2480
|
1216 |
znode = cnode;
|
deba@2480
|
1217 |
return;
|
deba@2480
|
1218 |
|
deba@2480
|
1219 |
} else if (ext) {
|
deba@2480
|
1220 |
znode = cnode;
|
deba@2480
|
1221 |
|
deba@2480
|
1222 |
while (!pertinent(cnode, embed_edge, merge_roots)) {
|
deba@2480
|
1223 |
Edge edge = node_data[order_map[cnode]].first;
|
deba@2480
|
1224 |
|
deba@2480
|
1225 |
if (_ugraph.target(edge) == pred) {
|
deba@2480
|
1226 |
edge = edge_lists[edge].next;
|
deba@2480
|
1227 |
}
|
deba@2480
|
1228 |
_kuratowski.set(edge, true);
|
deba@2480
|
1229 |
|
deba@2480
|
1230 |
Node next = _ugraph.target(edge);
|
deba@2480
|
1231 |
pred = cnode; cnode = next;
|
deba@2480
|
1232 |
}
|
deba@2480
|
1233 |
|
deba@2480
|
1234 |
wnode = cnode;
|
deba@2480
|
1235 |
return;
|
deba@2480
|
1236 |
|
deba@2480
|
1237 |
} else {
|
deba@2480
|
1238 |
Edge edge = node_data[order_map[cnode]].first;
|
deba@2480
|
1239 |
|
deba@2480
|
1240 |
if (_ugraph.target(edge) == pred) {
|
deba@2480
|
1241 |
edge = edge_lists[edge].next;
|
deba@2480
|
1242 |
}
|
deba@2480
|
1243 |
_kuratowski.set(edge, true);
|
deba@2480
|
1244 |
|
deba@2480
|
1245 |
Node next = _ugraph.target(edge);
|
deba@2480
|
1246 |
pred = cnode; cnode = next;
|
deba@2480
|
1247 |
}
|
deba@2480
|
1248 |
|
deba@2480
|
1249 |
}
|
deba@2480
|
1250 |
|
deba@2480
|
1251 |
}
|
deba@2480
|
1252 |
|
deba@2480
|
1253 |
void orientComponent(Node root, int rn, OrderMap& order_map,
|
deba@2480
|
1254 |
PredMap& pred_map, NodeData& node_data,
|
deba@2480
|
1255 |
EdgeLists& edge_lists, FlipMap& flip_map,
|
deba@2480
|
1256 |
TypeMap& type_map) {
|
deba@2480
|
1257 |
node_data[order_map[root]].first = node_data[rn].first;
|
deba@2480
|
1258 |
type_map[root] = 1;
|
deba@2480
|
1259 |
|
deba@2480
|
1260 |
std::vector<Node> st, qu;
|
deba@2480
|
1261 |
|
deba@2480
|
1262 |
st.push_back(root);
|
deba@2480
|
1263 |
while (!st.empty()) {
|
deba@2480
|
1264 |
Node node = st.back();
|
deba@2480
|
1265 |
st.pop_back();
|
deba@2480
|
1266 |
qu.push_back(node);
|
deba@2480
|
1267 |
|
deba@2480
|
1268 |
Edge edge = node_data[order_map[node]].first;
|
deba@2480
|
1269 |
|
deba@2480
|
1270 |
if (type_map[_ugraph.target(edge)] == 0) {
|
deba@2480
|
1271 |
st.push_back(_ugraph.target(edge));
|
deba@2480
|
1272 |
type_map[_ugraph.target(edge)] = 1;
|
deba@2480
|
1273 |
}
|
deba@2480
|
1274 |
|
deba@2480
|
1275 |
Edge last = edge, pred = edge;
|
deba@2480
|
1276 |
edge = edge_lists[edge].next;
|
deba@2480
|
1277 |
while (edge != last) {
|
deba@2480
|
1278 |
|
deba@2480
|
1279 |
if (type_map[_ugraph.target(edge)] == 0) {
|
deba@2480
|
1280 |
st.push_back(_ugraph.target(edge));
|
deba@2480
|
1281 |
type_map[_ugraph.target(edge)] = 1;
|
deba@2480
|
1282 |
}
|
deba@2480
|
1283 |
|
deba@2480
|
1284 |
Edge next = edge_lists[edge].next != pred ?
|
deba@2480
|
1285 |
edge_lists[edge].next : edge_lists[edge].prev;
|
deba@2480
|
1286 |
pred = edge; edge = next;
|
deba@2480
|
1287 |
}
|
deba@2480
|
1288 |
|
deba@2480
|
1289 |
}
|
deba@2480
|
1290 |
|
deba@2480
|
1291 |
type_map[root] = 2;
|
deba@2480
|
1292 |
flip_map[root] = false;
|
deba@2480
|
1293 |
|
deba@2480
|
1294 |
for (int i = 1; i < int(qu.size()); ++i) {
|
deba@2480
|
1295 |
|
deba@2480
|
1296 |
Node node = qu[i];
|
deba@2480
|
1297 |
|
deba@2480
|
1298 |
while (type_map[node] != 2) {
|
deba@2480
|
1299 |
st.push_back(node);
|
deba@2480
|
1300 |
type_map[node] = 2;
|
deba@2480
|
1301 |
node = _ugraph.source(pred_map[node]);
|
deba@2480
|
1302 |
}
|
deba@2480
|
1303 |
|
deba@2480
|
1304 |
bool flip = flip_map[node];
|
deba@2480
|
1305 |
|
deba@2480
|
1306 |
while (!st.empty()) {
|
deba@2480
|
1307 |
node = st.back();
|
deba@2480
|
1308 |
st.pop_back();
|
deba@2480
|
1309 |
|
deba@2480
|
1310 |
flip_map[node] = flip != flip_map[node];
|
deba@2480
|
1311 |
flip = flip_map[node];
|
deba@2480
|
1312 |
|
deba@2480
|
1313 |
if (flip) {
|
deba@2480
|
1314 |
Edge edge = node_data[order_map[node]].first;
|
deba@2480
|
1315 |
std::swap(edge_lists[edge].prev, edge_lists[edge].next);
|
deba@2480
|
1316 |
edge = edge_lists[edge].prev;
|
deba@2480
|
1317 |
std::swap(edge_lists[edge].prev, edge_lists[edge].next);
|
deba@2480
|
1318 |
node_data[order_map[node]].first = edge;
|
deba@2480
|
1319 |
}
|
deba@2480
|
1320 |
}
|
deba@2480
|
1321 |
}
|
deba@2480
|
1322 |
|
deba@2480
|
1323 |
for (int i = 0; i < int(qu.size()); ++i) {
|
deba@2480
|
1324 |
|
deba@2480
|
1325 |
Edge edge = node_data[order_map[qu[i]]].first;
|
deba@2480
|
1326 |
Edge last = edge, pred = edge;
|
deba@2480
|
1327 |
|
deba@2480
|
1328 |
edge = edge_lists[edge].next;
|
deba@2480
|
1329 |
while (edge != last) {
|
deba@2480
|
1330 |
|
deba@2480
|
1331 |
if (edge_lists[edge].next == pred) {
|
deba@2480
|
1332 |
std::swap(edge_lists[edge].next, edge_lists[edge].prev);
|
deba@2480
|
1333 |
}
|
deba@2480
|
1334 |
pred = edge; edge = edge_lists[edge].next;
|
deba@2480
|
1335 |
}
|
deba@2480
|
1336 |
|
deba@2480
|
1337 |
}
|
deba@2480
|
1338 |
}
|
deba@2480
|
1339 |
|
deba@2480
|
1340 |
void setFaceFlags(Node root, Node wnode, Node ynode, Node xnode,
|
deba@2480
|
1341 |
OrderMap& order_map, NodeData& node_data,
|
deba@2480
|
1342 |
TypeMap& type_map) {
|
deba@2480
|
1343 |
Node node = _ugraph.target(node_data[order_map[root]].first);
|
deba@2480
|
1344 |
|
deba@2480
|
1345 |
while (node != ynode) {
|
deba@2480
|
1346 |
type_map[node] = HIGHY;
|
deba@2480
|
1347 |
node = _ugraph.target(node_data[order_map[node]].first);
|
deba@2480
|
1348 |
}
|
deba@2480
|
1349 |
|
deba@2480
|
1350 |
while (node != wnode) {
|
deba@2480
|
1351 |
type_map[node] = LOWY;
|
deba@2480
|
1352 |
node = _ugraph.target(node_data[order_map[node]].first);
|
deba@2480
|
1353 |
}
|
deba@2480
|
1354 |
|
deba@2480
|
1355 |
node = _ugraph.target(node_data[order_map[wnode]].first);
|
deba@2480
|
1356 |
|
deba@2480
|
1357 |
while (node != xnode) {
|
deba@2480
|
1358 |
type_map[node] = LOWX;
|
deba@2480
|
1359 |
node = _ugraph.target(node_data[order_map[node]].first);
|
deba@2480
|
1360 |
}
|
deba@2480
|
1361 |
type_map[node] = LOWX;
|
deba@2480
|
1362 |
|
deba@2480
|
1363 |
node = _ugraph.target(node_data[order_map[xnode]].first);
|
deba@2480
|
1364 |
while (node != root) {
|
deba@2480
|
1365 |
type_map[node] = HIGHX;
|
deba@2480
|
1366 |
node = _ugraph.target(node_data[order_map[node]].first);
|
deba@2480
|
1367 |
}
|
deba@2480
|
1368 |
|
deba@2480
|
1369 |
type_map[wnode] = PERTINENT;
|
deba@2480
|
1370 |
type_map[root] = ROOT;
|
deba@2480
|
1371 |
}
|
deba@2480
|
1372 |
|
deba@2480
|
1373 |
void findInternalPath(std::vector<Edge>& ipath,
|
deba@2480
|
1374 |
Node wnode, Node root, TypeMap& type_map,
|
deba@2480
|
1375 |
OrderMap& order_map, NodeData& node_data,
|
deba@2480
|
1376 |
EdgeLists& edge_lists) {
|
deba@2480
|
1377 |
std::vector<Edge> st;
|
deba@2480
|
1378 |
|
deba@2480
|
1379 |
Node node = wnode;
|
deba@2480
|
1380 |
|
deba@2480
|
1381 |
while (node != root) {
|
deba@2480
|
1382 |
Edge edge = edge_lists[node_data[order_map[node]].first].next;
|
deba@2480
|
1383 |
st.push_back(edge);
|
deba@2480
|
1384 |
node = _ugraph.target(edge);
|
deba@2480
|
1385 |
}
|
deba@2480
|
1386 |
|
deba@2480
|
1387 |
while (true) {
|
deba@2480
|
1388 |
Edge edge = st.back();
|
deba@2480
|
1389 |
if (type_map[_ugraph.target(edge)] == LOWX ||
|
deba@2480
|
1390 |
type_map[_ugraph.target(edge)] == HIGHX) {
|
deba@2480
|
1391 |
break;
|
deba@2480
|
1392 |
}
|
deba@2480
|
1393 |
if (type_map[_ugraph.target(edge)] == 2) {
|
deba@2480
|
1394 |
type_map[_ugraph.target(edge)] = 3;
|
deba@2480
|
1395 |
|
deba@2480
|
1396 |
edge = edge_lists[_ugraph.oppositeEdge(edge)].next;
|
deba@2480
|
1397 |
st.push_back(edge);
|
deba@2480
|
1398 |
} else {
|
deba@2480
|
1399 |
st.pop_back();
|
deba@2480
|
1400 |
edge = edge_lists[edge].next;
|
deba@2480
|
1401 |
|
deba@2480
|
1402 |
while (_ugraph.oppositeEdge(edge) == st.back()) {
|
deba@2480
|
1403 |
edge = st.back();
|
deba@2480
|
1404 |
st.pop_back();
|
deba@2480
|
1405 |
edge = edge_lists[edge].next;
|
deba@2480
|
1406 |
}
|
deba@2480
|
1407 |
st.push_back(edge);
|
deba@2480
|
1408 |
}
|
deba@2480
|
1409 |
}
|
deba@2480
|
1410 |
|
deba@2480
|
1411 |
for (int i = 0; i < int(st.size()); ++i) {
|
deba@2480
|
1412 |
if (type_map[_ugraph.target(st[i])] != LOWY &&
|
deba@2480
|
1413 |
type_map[_ugraph.target(st[i])] != HIGHY) {
|
deba@2480
|
1414 |
for (; i < int(st.size()); ++i) {
|
deba@2480
|
1415 |
ipath.push_back(st[i]);
|
deba@2480
|
1416 |
}
|
deba@2480
|
1417 |
}
|
deba@2480
|
1418 |
}
|
deba@2480
|
1419 |
}
|
deba@2480
|
1420 |
|
deba@2480
|
1421 |
void setInternalFlags(std::vector<Edge>& ipath, TypeMap& type_map) {
|
deba@2480
|
1422 |
for (int i = 1; i < int(ipath.size()); ++i) {
|
deba@2480
|
1423 |
type_map[_ugraph.source(ipath[i])] = INTERNAL;
|
deba@2480
|
1424 |
}
|
deba@2480
|
1425 |
}
|
deba@2480
|
1426 |
|
deba@2480
|
1427 |
void findPilePath(std::vector<Edge>& ppath,
|
deba@2480
|
1428 |
Node root, TypeMap& type_map, OrderMap& order_map,
|
deba@2480
|
1429 |
NodeData& node_data, EdgeLists& edge_lists) {
|
deba@2480
|
1430 |
std::vector<Edge> st;
|
deba@2480
|
1431 |
|
deba@2480
|
1432 |
st.push_back(_ugraph.oppositeEdge(node_data[order_map[root]].first));
|
deba@2480
|
1433 |
st.push_back(node_data[order_map[root]].first);
|
deba@2480
|
1434 |
|
deba@2480
|
1435 |
while (st.size() > 1) {
|
deba@2480
|
1436 |
Edge edge = st.back();
|
deba@2480
|
1437 |
if (type_map[_ugraph.target(edge)] == INTERNAL) {
|
deba@2480
|
1438 |
break;
|
deba@2480
|
1439 |
}
|
deba@2480
|
1440 |
if (type_map[_ugraph.target(edge)] == 3) {
|
deba@2480
|
1441 |
type_map[_ugraph.target(edge)] = 4;
|
deba@2480
|
1442 |
|
deba@2480
|
1443 |
edge = edge_lists[_ugraph.oppositeEdge(edge)].next;
|
deba@2480
|
1444 |
st.push_back(edge);
|
deba@2480
|
1445 |
} else {
|
deba@2480
|
1446 |
st.pop_back();
|
deba@2480
|
1447 |
edge = edge_lists[edge].next;
|
deba@2480
|
1448 |
|
deba@2480
|
1449 |
while (!st.empty() && _ugraph.oppositeEdge(edge) == st.back()) {
|
deba@2480
|
1450 |
edge = st.back();
|
deba@2480
|
1451 |
st.pop_back();
|
deba@2480
|
1452 |
edge = edge_lists[edge].next;
|
deba@2480
|
1453 |
}
|
deba@2480
|
1454 |
st.push_back(edge);
|
deba@2480
|
1455 |
}
|
deba@2480
|
1456 |
}
|
deba@2480
|
1457 |
|
deba@2480
|
1458 |
for (int i = 1; i < int(st.size()); ++i) {
|
deba@2480
|
1459 |
ppath.push_back(st[i]);
|
deba@2480
|
1460 |
}
|
deba@2480
|
1461 |
}
|
deba@2480
|
1462 |
|
deba@2480
|
1463 |
|
deba@2480
|
1464 |
int markExternalPath(Node node, OrderMap& order_map,
|
deba@2480
|
1465 |
ChildLists& child_lists, PredMap& pred_map,
|
deba@2480
|
1466 |
AncestorMap& ancestor_map, LowMap& low_map) {
|
deba@2480
|
1467 |
int lp = lowPoint(node, order_map, child_lists,
|
deba@2480
|
1468 |
ancestor_map, low_map);
|
deba@2480
|
1469 |
|
deba@2480
|
1470 |
if (ancestor_map[node] != lp) {
|
deba@2480
|
1471 |
node = child_lists[node].first;
|
deba@2480
|
1472 |
_kuratowski[pred_map[node]] = true;
|
deba@2480
|
1473 |
|
deba@2480
|
1474 |
while (ancestor_map[node] != lp) {
|
deba@2480
|
1475 |
for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
|
deba@2480
|
1476 |
Node tnode = _ugraph.target(e);
|
deba@2480
|
1477 |
if (order_map[tnode] > order_map[node] && low_map[tnode] == lp) {
|
deba@2480
|
1478 |
node = tnode;
|
deba@2480
|
1479 |
_kuratowski[e] = true;
|
deba@2480
|
1480 |
break;
|
deba@2480
|
1481 |
}
|
deba@2480
|
1482 |
}
|
deba@2480
|
1483 |
}
|
deba@2480
|
1484 |
}
|
deba@2480
|
1485 |
|
deba@2480
|
1486 |
for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
|
deba@2480
|
1487 |
if (order_map[_ugraph.target(e)] == lp) {
|
deba@2480
|
1488 |
_kuratowski[e] = true;
|
deba@2480
|
1489 |
break;
|
deba@2480
|
1490 |
}
|
deba@2480
|
1491 |
}
|
deba@2480
|
1492 |
|
deba@2480
|
1493 |
return lp;
|
deba@2480
|
1494 |
}
|
deba@2480
|
1495 |
|
deba@2480
|
1496 |
void markPertinentPath(Node node, OrderMap& order_map,
|
deba@2480
|
1497 |
NodeData& node_data, EdgeLists& edge_lists,
|
deba@2480
|
1498 |
EmbedEdge& embed_edge, MergeRoots& merge_roots) {
|
deba@2480
|
1499 |
while (embed_edge[node] == INVALID) {
|
deba@2480
|
1500 |
int n = merge_roots[node].front();
|
deba@2480
|
1501 |
Edge edge = node_data[n].first;
|
deba@2480
|
1502 |
|
deba@2480
|
1503 |
_kuratowski.set(edge, true);
|
deba@2480
|
1504 |
|
deba@2480
|
1505 |
Node pred = node;
|
deba@2480
|
1506 |
node = _ugraph.target(edge);
|
deba@2480
|
1507 |
while (!pertinent(node, embed_edge, merge_roots)) {
|
deba@2480
|
1508 |
edge = node_data[order_map[node]].first;
|
deba@2480
|
1509 |
if (_ugraph.target(edge) == pred) {
|
deba@2480
|
1510 |
edge = edge_lists[edge].next;
|
deba@2480
|
1511 |
}
|
deba@2480
|
1512 |
_kuratowski.set(edge, true);
|
deba@2480
|
1513 |
pred = node;
|
deba@2480
|
1514 |
node = _ugraph.target(edge);
|
deba@2480
|
1515 |
}
|
deba@2480
|
1516 |
}
|
deba@2480
|
1517 |
_kuratowski.set(embed_edge[node], true);
|
deba@2480
|
1518 |
}
|
deba@2480
|
1519 |
|
deba@2480
|
1520 |
void markPredPath(Node node, Node snode, PredMap& pred_map) {
|
deba@2480
|
1521 |
while (node != snode) {
|
deba@2480
|
1522 |
_kuratowski.set(pred_map[node], true);
|
deba@2480
|
1523 |
node = _ugraph.source(pred_map[node]);
|
deba@2480
|
1524 |
}
|
deba@2480
|
1525 |
}
|
deba@2480
|
1526 |
|
deba@2480
|
1527 |
void markFacePath(Node ynode, Node xnode,
|
deba@2480
|
1528 |
OrderMap& order_map, NodeData& node_data) {
|
deba@2480
|
1529 |
Edge edge = node_data[order_map[ynode]].first;
|
deba@2480
|
1530 |
Node node = _ugraph.target(edge);
|
deba@2480
|
1531 |
_kuratowski.set(edge, true);
|
deba@2480
|
1532 |
|
deba@2480
|
1533 |
while (node != xnode) {
|
deba@2480
|
1534 |
edge = node_data[order_map[node]].first;
|
deba@2480
|
1535 |
_kuratowski.set(edge, true);
|
deba@2480
|
1536 |
node = _ugraph.target(edge);
|
deba@2480
|
1537 |
}
|
deba@2480
|
1538 |
}
|
deba@2480
|
1539 |
|
deba@2480
|
1540 |
void markInternalPath(std::vector<Edge>& path) {
|
deba@2480
|
1541 |
for (int i = 0; i < int(path.size()); ++i) {
|
deba@2480
|
1542 |
_kuratowski.set(path[i], true);
|
deba@2480
|
1543 |
}
|
deba@2480
|
1544 |
}
|
deba@2480
|
1545 |
|
deba@2480
|
1546 |
void markPilePath(std::vector<Edge>& path) {
|
deba@2480
|
1547 |
for (int i = 0; i < int(path.size()); ++i) {
|
deba@2480
|
1548 |
_kuratowski.set(path[i], true);
|
deba@2480
|
1549 |
}
|
deba@2480
|
1550 |
}
|
deba@2480
|
1551 |
|
deba@2480
|
1552 |
void isolateKuratowski(Edge edge, NodeData& node_data,
|
deba@2480
|
1553 |
EdgeLists& edge_lists, FlipMap& flip_map,
|
deba@2480
|
1554 |
OrderMap& order_map, OrderList& order_list,
|
deba@2480
|
1555 |
PredMap& pred_map, ChildLists& child_lists,
|
deba@2480
|
1556 |
AncestorMap& ancestor_map, LowMap& low_map,
|
deba@2480
|
1557 |
EmbedEdge& embed_edge, MergeRoots& merge_roots) {
|
deba@2480
|
1558 |
|
deba@2480
|
1559 |
Node root = _ugraph.source(edge);
|
deba@2480
|
1560 |
Node enode = _ugraph.target(edge);
|
deba@2480
|
1561 |
|
deba@2480
|
1562 |
int rorder = order_map[root];
|
deba@2480
|
1563 |
|
deba@2480
|
1564 |
TypeMap type_map(_ugraph, 0);
|
deba@2480
|
1565 |
|
deba@2480
|
1566 |
int rn = findComponentRoot(root, enode, child_lists,
|
deba@2480
|
1567 |
order_map, order_list);
|
deba@2480
|
1568 |
|
deba@2480
|
1569 |
Node xnode = order_list[node_data[rn].next];
|
deba@2480
|
1570 |
Node ynode = order_list[node_data[rn].prev];
|
deba@2480
|
1571 |
|
deba@2480
|
1572 |
// Minor-A
|
deba@2480
|
1573 |
{
|
deba@2480
|
1574 |
while (!merge_roots[xnode].empty() || !merge_roots[ynode].empty()) {
|
deba@2480
|
1575 |
|
deba@2480
|
1576 |
if (!merge_roots[xnode].empty()) {
|
deba@2480
|
1577 |
root = xnode;
|
deba@2480
|
1578 |
rn = merge_roots[xnode].front();
|
deba@2480
|
1579 |
} else {
|
deba@2480
|
1580 |
root = ynode;
|
deba@2480
|
1581 |
rn = merge_roots[ynode].front();
|
deba@2480
|
1582 |
}
|
deba@2480
|
1583 |
|
deba@2480
|
1584 |
xnode = order_list[node_data[rn].next];
|
deba@2480
|
1585 |
ynode = order_list[node_data[rn].prev];
|
deba@2480
|
1586 |
}
|
deba@2480
|
1587 |
|
deba@2480
|
1588 |
if (root != _ugraph.source(edge)) {
|
deba@2480
|
1589 |
orientComponent(root, rn, order_map, pred_map,
|
deba@2480
|
1590 |
node_data, edge_lists, flip_map, type_map);
|
deba@2480
|
1591 |
markFacePath(root, root, order_map, node_data);
|
deba@2480
|
1592 |
int xlp = markExternalPath(xnode, order_map, child_lists,
|
deba@2480
|
1593 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1594 |
int ylp = markExternalPath(ynode, order_map, child_lists,
|
deba@2480
|
1595 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1596 |
markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
|
deba@2480
|
1597 |
Node lwnode = findPertinent(ynode, order_map, node_data,
|
deba@2480
|
1598 |
embed_edge, merge_roots);
|
deba@2480
|
1599 |
|
deba@2480
|
1600 |
markPertinentPath(lwnode, order_map, node_data, edge_lists,
|
deba@2480
|
1601 |
embed_edge, merge_roots);
|
deba@2480
|
1602 |
|
deba@2480
|
1603 |
return;
|
deba@2480
|
1604 |
}
|
deba@2480
|
1605 |
}
|
deba@2480
|
1606 |
|
deba@2480
|
1607 |
orientComponent(root, rn, order_map, pred_map,
|
deba@2480
|
1608 |
node_data, edge_lists, flip_map, type_map);
|
deba@2480
|
1609 |
|
deba@2480
|
1610 |
Node wnode = findPertinent(ynode, order_map, node_data,
|
deba@2480
|
1611 |
embed_edge, merge_roots);
|
deba@2480
|
1612 |
setFaceFlags(root, wnode, ynode, xnode, order_map, node_data, type_map);
|
deba@2480
|
1613 |
|
deba@2480
|
1614 |
|
deba@2480
|
1615 |
//Minor-B
|
deba@2480
|
1616 |
if (!merge_roots[wnode].empty()) {
|
deba@2480
|
1617 |
int cn = merge_roots[wnode].back();
|
deba@2480
|
1618 |
Node rep = order_list[cn - order_list.size()];
|
deba@2480
|
1619 |
if (low_map[rep] < rorder) {
|
deba@2480
|
1620 |
markFacePath(root, root, order_map, node_data);
|
deba@2480
|
1621 |
int xlp = markExternalPath(xnode, order_map, child_lists,
|
deba@2480
|
1622 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1623 |
int ylp = markExternalPath(ynode, order_map, child_lists,
|
deba@2480
|
1624 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1625 |
|
deba@2480
|
1626 |
Node lwnode, lznode;
|
deba@2480
|
1627 |
markCommonPath(wnode, rorder, lwnode, lznode, order_list,
|
deba@2480
|
1628 |
order_map, node_data, edge_lists, embed_edge,
|
deba@2480
|
1629 |
merge_roots, child_lists, ancestor_map, low_map);
|
deba@2480
|
1630 |
|
deba@2480
|
1631 |
markPertinentPath(lwnode, order_map, node_data, edge_lists,
|
deba@2480
|
1632 |
embed_edge, merge_roots);
|
deba@2480
|
1633 |
int zlp = markExternalPath(lznode, order_map, child_lists,
|
deba@2480
|
1634 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1635 |
|
deba@2480
|
1636 |
int minlp = xlp < ylp ? xlp : ylp;
|
deba@2480
|
1637 |
if (zlp < minlp) minlp = zlp;
|
deba@2480
|
1638 |
|
deba@2480
|
1639 |
int maxlp = xlp > ylp ? xlp : ylp;
|
deba@2480
|
1640 |
if (zlp > maxlp) maxlp = zlp;
|
deba@2480
|
1641 |
|
deba@2480
|
1642 |
markPredPath(order_list[maxlp], order_list[minlp], pred_map);
|
deba@2480
|
1643 |
|
deba@2480
|
1644 |
return;
|
deba@2480
|
1645 |
}
|
deba@2480
|
1646 |
}
|
deba@2480
|
1647 |
|
deba@2480
|
1648 |
Node pxnode, pynode;
|
deba@2480
|
1649 |
std::vector<Edge> ipath;
|
deba@2480
|
1650 |
findInternalPath(ipath, wnode, root, type_map, order_map,
|
deba@2480
|
1651 |
node_data, edge_lists);
|
deba@2480
|
1652 |
setInternalFlags(ipath, type_map);
|
deba@2480
|
1653 |
pynode = _ugraph.source(ipath.front());
|
deba@2480
|
1654 |
pxnode = _ugraph.target(ipath.back());
|
deba@2480
|
1655 |
|
deba@2480
|
1656 |
wnode = findPertinent(pynode, order_map, node_data,
|
deba@2480
|
1657 |
embed_edge, merge_roots);
|
deba@2480
|
1658 |
|
deba@2480
|
1659 |
// Minor-C
|
deba@2480
|
1660 |
{
|
deba@2480
|
1661 |
if (type_map[_ugraph.source(ipath.front())] == HIGHY) {
|
deba@2480
|
1662 |
if (type_map[_ugraph.target(ipath.back())] == HIGHX) {
|
deba@2480
|
1663 |
markFacePath(xnode, pxnode, order_map, node_data);
|
deba@2480
|
1664 |
}
|
deba@2480
|
1665 |
markFacePath(root, xnode, order_map, node_data);
|
deba@2480
|
1666 |
markPertinentPath(wnode, order_map, node_data, edge_lists,
|
deba@2480
|
1667 |
embed_edge, merge_roots);
|
deba@2480
|
1668 |
markInternalPath(ipath);
|
deba@2480
|
1669 |
int xlp = markExternalPath(xnode, order_map, child_lists,
|
deba@2480
|
1670 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1671 |
int ylp = markExternalPath(ynode, order_map, child_lists,
|
deba@2480
|
1672 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1673 |
markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
|
deba@2480
|
1674 |
return;
|
deba@2480
|
1675 |
}
|
deba@2480
|
1676 |
|
deba@2480
|
1677 |
if (type_map[_ugraph.target(ipath.back())] == HIGHX) {
|
deba@2480
|
1678 |
markFacePath(ynode, root, order_map, node_data);
|
deba@2480
|
1679 |
markPertinentPath(wnode, order_map, node_data, edge_lists,
|
deba@2480
|
1680 |
embed_edge, merge_roots);
|
deba@2480
|
1681 |
markInternalPath(ipath);
|
deba@2480
|
1682 |
int xlp = markExternalPath(xnode, order_map, child_lists,
|
deba@2480
|
1683 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1684 |
int ylp = markExternalPath(ynode, order_map, child_lists,
|
deba@2480
|
1685 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1686 |
markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
|
deba@2480
|
1687 |
return;
|
deba@2480
|
1688 |
}
|
deba@2480
|
1689 |
}
|
deba@2480
|
1690 |
|
deba@2480
|
1691 |
std::vector<Edge> ppath;
|
deba@2480
|
1692 |
findPilePath(ppath, root, type_map, order_map, node_data, edge_lists);
|
deba@2480
|
1693 |
|
deba@2480
|
1694 |
// Minor-D
|
deba@2480
|
1695 |
if (!ppath.empty()) {
|
deba@2480
|
1696 |
markFacePath(ynode, xnode, order_map, node_data);
|
deba@2480
|
1697 |
markPertinentPath(wnode, order_map, node_data, edge_lists,
|
deba@2480
|
1698 |
embed_edge, merge_roots);
|
deba@2480
|
1699 |
markPilePath(ppath);
|
deba@2480
|
1700 |
markInternalPath(ipath);
|
deba@2480
|
1701 |
int xlp = markExternalPath(xnode, order_map, child_lists,
|
deba@2480
|
1702 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1703 |
int ylp = markExternalPath(ynode, order_map, child_lists,
|
deba@2480
|
1704 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1705 |
markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
|
deba@2480
|
1706 |
return;
|
deba@2480
|
1707 |
}
|
deba@2480
|
1708 |
|
deba@2480
|
1709 |
// Minor-E*
|
deba@2480
|
1710 |
{
|
deba@2480
|
1711 |
|
deba@2480
|
1712 |
if (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
|
deba@2480
|
1713 |
Node znode = findExternal(pynode, rorder, order_map,
|
deba@2480
|
1714 |
child_lists, ancestor_map,
|
deba@2480
|
1715 |
low_map, node_data);
|
deba@2480
|
1716 |
|
deba@2480
|
1717 |
if (type_map[znode] == LOWY) {
|
deba@2480
|
1718 |
markFacePath(root, xnode, order_map, node_data);
|
deba@2480
|
1719 |
markPertinentPath(wnode, order_map, node_data, edge_lists,
|
deba@2480
|
1720 |
embed_edge, merge_roots);
|
deba@2480
|
1721 |
markInternalPath(ipath);
|
deba@2480
|
1722 |
int xlp = markExternalPath(xnode, order_map, child_lists,
|
deba@2480
|
1723 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1724 |
int zlp = markExternalPath(znode, order_map, child_lists,
|
deba@2480
|
1725 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1726 |
markPredPath(root, order_list[xlp < zlp ? xlp : zlp], pred_map);
|
deba@2480
|
1727 |
} else {
|
deba@2480
|
1728 |
markFacePath(ynode, root, order_map, node_data);
|
deba@2480
|
1729 |
markPertinentPath(wnode, order_map, node_data, edge_lists,
|
deba@2480
|
1730 |
embed_edge, merge_roots);
|
deba@2480
|
1731 |
markInternalPath(ipath);
|
deba@2480
|
1732 |
int ylp = markExternalPath(ynode, order_map, child_lists,
|
deba@2480
|
1733 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1734 |
int zlp = markExternalPath(znode, order_map, child_lists,
|
deba@2480
|
1735 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1736 |
markPredPath(root, order_list[ylp < zlp ? ylp : zlp], pred_map);
|
deba@2480
|
1737 |
}
|
deba@2480
|
1738 |
return;
|
deba@2480
|
1739 |
}
|
deba@2480
|
1740 |
|
deba@2480
|
1741 |
int xlp = markExternalPath(xnode, order_map, child_lists,
|
deba@2480
|
1742 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1743 |
int ylp = markExternalPath(ynode, order_map, child_lists,
|
deba@2480
|
1744 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1745 |
int wlp = markExternalPath(wnode, order_map, child_lists,
|
deba@2480
|
1746 |
pred_map, ancestor_map, low_map);
|
deba@2480
|
1747 |
|
deba@2480
|
1748 |
if (wlp > xlp && wlp > ylp) {
|
deba@2480
|
1749 |
markFacePath(root, root, order_map, node_data);
|
deba@2480
|
1750 |
markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
|
deba@2480
|
1751 |
return;
|
deba@2480
|
1752 |
}
|
deba@2480
|
1753 |
|
deba@2480
|
1754 |
markInternalPath(ipath);
|
deba@2480
|
1755 |
markPertinentPath(wnode, order_map, node_data, edge_lists,
|
deba@2480
|
1756 |
embed_edge, merge_roots);
|
deba@2480
|
1757 |
|
deba@2480
|
1758 |
if (xlp > ylp && xlp > wlp) {
|
deba@2480
|
1759 |
markFacePath(root, pynode, order_map, node_data);
|
deba@2480
|
1760 |
markFacePath(wnode, xnode, order_map, node_data);
|
deba@2480
|
1761 |
markPredPath(root, order_list[ylp < wlp ? ylp : wlp], pred_map);
|
deba@2480
|
1762 |
return;
|
deba@2480
|
1763 |
}
|
deba@2480
|
1764 |
|
deba@2480
|
1765 |
if (ylp > xlp && ylp > wlp) {
|
deba@2480
|
1766 |
markFacePath(pxnode, root, order_map, node_data);
|
deba@2480
|
1767 |
markFacePath(ynode, wnode, order_map, node_data);
|
deba@2480
|
1768 |
markPredPath(root, order_list[xlp < wlp ? xlp : wlp], pred_map);
|
deba@2480
|
1769 |
return;
|
deba@2480
|
1770 |
}
|
deba@2480
|
1771 |
|
deba@2480
|
1772 |
if (pynode != ynode) {
|
deba@2480
|
1773 |
markFacePath(pxnode, wnode, order_map, node_data);
|
deba@2480
|
1774 |
|
deba@2480
|
1775 |
int minlp = xlp < ylp ? xlp : ylp;
|
deba@2480
|
1776 |
if (wlp < minlp) minlp = wlp;
|
deba@2480
|
1777 |
|
deba@2480
|
1778 |
int maxlp = xlp > ylp ? xlp : ylp;
|
deba@2480
|
1779 |
if (wlp > maxlp) maxlp = wlp;
|
deba@2480
|
1780 |
|
deba@2480
|
1781 |
markPredPath(order_list[maxlp], order_list[minlp], pred_map);
|
deba@2480
|
1782 |
return;
|
deba@2480
|
1783 |
}
|
deba@2480
|
1784 |
|
deba@2480
|
1785 |
if (pxnode != xnode) {
|
deba@2480
|
1786 |
markFacePath(wnode, pynode, order_map, node_data);
|
deba@2480
|
1787 |
|
deba@2480
|
1788 |
int minlp = xlp < ylp ? xlp : ylp;
|
deba@2480
|
1789 |
if (wlp < minlp) minlp = wlp;
|
deba@2480
|
1790 |
|
deba@2480
|
1791 |
int maxlp = xlp > ylp ? xlp : ylp;
|
deba@2480
|
1792 |
if (wlp > maxlp) maxlp = wlp;
|
deba@2480
|
1793 |
|
deba@2480
|
1794 |
markPredPath(order_list[maxlp], order_list[minlp], pred_map);
|
deba@2480
|
1795 |
return;
|
deba@2480
|
1796 |
}
|
deba@2480
|
1797 |
|
deba@2480
|
1798 |
markFacePath(root, root, order_map, node_data);
|
deba@2480
|
1799 |
int minlp = xlp < ylp ? xlp : ylp;
|
deba@2480
|
1800 |
if (wlp < minlp) minlp = wlp;
|
deba@2480
|
1801 |
markPredPath(root, order_list[minlp], pred_map);
|
deba@2480
|
1802 |
return;
|
deba@2480
|
1803 |
}
|
deba@2480
|
1804 |
|
deba@2480
|
1805 |
}
|
deba@2480
|
1806 |
|
deba@2480
|
1807 |
};
|
deba@2480
|
1808 |
|
deba@2480
|
1809 |
}
|
deba@2480
|
1810 |
|
deba@2480
|
1811 |
#endif
|