alpar@209
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
deba@57
|
2 |
*
|
alpar@209
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
deba@57
|
4 |
*
|
alpar@107
|
5 |
* Copyright (C) 2003-2008
|
deba@57
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@57
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@57
|
8 |
*
|
deba@57
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@57
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@57
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@57
|
12 |
*
|
deba@57
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@57
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@57
|
15 |
* purpose.
|
deba@57
|
16 |
*
|
deba@57
|
17 |
*/
|
deba@57
|
18 |
|
deba@57
|
19 |
#ifndef LEMON_BITS_BASE_EXTENDER_H
|
deba@57
|
20 |
#define LEMON_BITS_BASE_EXTENDER_H
|
deba@57
|
21 |
|
deba@220
|
22 |
#include <lemon/core.h>
|
deba@57
|
23 |
#include <lemon/error.h>
|
deba@57
|
24 |
|
deba@57
|
25 |
#include <lemon/bits/map_extender.h>
|
deba@57
|
26 |
#include <lemon/bits/default_map.h>
|
deba@57
|
27 |
|
deba@57
|
28 |
#include <lemon/concept_check.h>
|
deba@57
|
29 |
#include <lemon/concepts/maps.h>
|
deba@57
|
30 |
|
deba@57
|
31 |
///\ingroup digraphbits
|
deba@57
|
32 |
///\file
|
deba@57
|
33 |
///\brief Extenders for the digraph types
|
deba@57
|
34 |
namespace lemon {
|
deba@57
|
35 |
|
deba@57
|
36 |
/// \ingroup digraphbits
|
deba@57
|
37 |
///
|
deba@57
|
38 |
/// \brief BaseDigraph to BaseGraph extender
|
deba@57
|
39 |
template <typename Base>
|
deba@57
|
40 |
class UndirDigraphExtender : public Base {
|
deba@57
|
41 |
|
deba@57
|
42 |
public:
|
deba@57
|
43 |
|
deba@57
|
44 |
typedef Base Parent;
|
deba@57
|
45 |
typedef typename Parent::Arc Edge;
|
deba@57
|
46 |
typedef typename Parent::Node Node;
|
deba@57
|
47 |
|
deba@57
|
48 |
typedef True UndirectedTag;
|
deba@57
|
49 |
|
deba@57
|
50 |
class Arc : public Edge {
|
deba@57
|
51 |
friend class UndirDigraphExtender;
|
deba@57
|
52 |
|
deba@57
|
53 |
protected:
|
deba@57
|
54 |
bool forward;
|
deba@57
|
55 |
|
deba@57
|
56 |
Arc(const Edge &ue, bool _forward) :
|
deba@57
|
57 |
Edge(ue), forward(_forward) {}
|
deba@57
|
58 |
|
deba@57
|
59 |
public:
|
deba@57
|
60 |
Arc() {}
|
deba@57
|
61 |
|
deba@57
|
62 |
/// Invalid arc constructor
|
deba@57
|
63 |
Arc(Invalid i) : Edge(i), forward(true) {}
|
deba@57
|
64 |
|
deba@57
|
65 |
bool operator==(const Arc &that) const {
|
alpar@209
|
66 |
return forward==that.forward && Edge(*this)==Edge(that);
|
deba@57
|
67 |
}
|
deba@57
|
68 |
bool operator!=(const Arc &that) const {
|
alpar@209
|
69 |
return forward!=that.forward || Edge(*this)!=Edge(that);
|
deba@57
|
70 |
}
|
deba@57
|
71 |
bool operator<(const Arc &that) const {
|
alpar@209
|
72 |
return forward<that.forward ||
|
alpar@209
|
73 |
(!(that.forward<forward) && Edge(*this)<Edge(that));
|
deba@57
|
74 |
}
|
deba@57
|
75 |
};
|
deba@57
|
76 |
|
deba@57
|
77 |
|
deba@57
|
78 |
|
deba@57
|
79 |
using Parent::source;
|
deba@57
|
80 |
|
deba@57
|
81 |
/// Source of the given Arc.
|
deba@57
|
82 |
Node source(const Arc &e) const {
|
deba@57
|
83 |
return e.forward ? Parent::source(e) : Parent::target(e);
|
deba@57
|
84 |
}
|
deba@57
|
85 |
|
deba@57
|
86 |
using Parent::target;
|
deba@57
|
87 |
|
deba@57
|
88 |
/// Target of the given Arc.
|
deba@57
|
89 |
Node target(const Arc &e) const {
|
deba@57
|
90 |
return e.forward ? Parent::target(e) : Parent::source(e);
|
deba@57
|
91 |
}
|
deba@57
|
92 |
|
deba@57
|
93 |
/// \brief Directed arc from an edge.
|
deba@57
|
94 |
///
|
deba@57
|
95 |
/// Returns a directed arc corresponding to the specified Edge.
|
deba@57
|
96 |
/// If the given bool is true the given edge and the
|
deba@57
|
97 |
/// returned arc have the same source node.
|
deba@57
|
98 |
static Arc direct(const Edge &ue, bool d) {
|
deba@57
|
99 |
return Arc(ue, d);
|
deba@57
|
100 |
}
|
deba@57
|
101 |
|
deba@57
|
102 |
/// Returns whether the given directed arc is same orientation as the
|
deba@57
|
103 |
/// corresponding edge.
|
deba@57
|
104 |
///
|
deba@57
|
105 |
/// \todo reference to the corresponding point of the undirected digraph
|
deba@57
|
106 |
/// concept. "What does the direction of an edge mean?"
|
deba@57
|
107 |
static bool direction(const Arc &e) { return e.forward; }
|
deba@57
|
108 |
|
deba@57
|
109 |
|
deba@57
|
110 |
using Parent::first;
|
deba@57
|
111 |
using Parent::next;
|
deba@57
|
112 |
|
deba@57
|
113 |
void first(Arc &e) const {
|
deba@57
|
114 |
Parent::first(e);
|
deba@57
|
115 |
e.forward=true;
|
deba@57
|
116 |
}
|
deba@57
|
117 |
|
deba@57
|
118 |
void next(Arc &e) const {
|
deba@57
|
119 |
if( e.forward ) {
|
alpar@209
|
120 |
e.forward = false;
|
deba@57
|
121 |
}
|
deba@57
|
122 |
else {
|
alpar@209
|
123 |
Parent::next(e);
|
alpar@209
|
124 |
e.forward = true;
|
deba@57
|
125 |
}
|
deba@57
|
126 |
}
|
deba@57
|
127 |
|
deba@57
|
128 |
void firstOut(Arc &e, const Node &n) const {
|
deba@57
|
129 |
Parent::firstIn(e,n);
|
deba@57
|
130 |
if( Edge(e) != INVALID ) {
|
alpar@209
|
131 |
e.forward = false;
|
deba@57
|
132 |
}
|
deba@57
|
133 |
else {
|
alpar@209
|
134 |
Parent::firstOut(e,n);
|
alpar@209
|
135 |
e.forward = true;
|
deba@57
|
136 |
}
|
deba@57
|
137 |
}
|
deba@57
|
138 |
void nextOut(Arc &e) const {
|
deba@57
|
139 |
if( ! e.forward ) {
|
alpar@209
|
140 |
Node n = Parent::target(e);
|
alpar@209
|
141 |
Parent::nextIn(e);
|
alpar@209
|
142 |
if( Edge(e) == INVALID ) {
|
alpar@209
|
143 |
Parent::firstOut(e, n);
|
alpar@209
|
144 |
e.forward = true;
|
alpar@209
|
145 |
}
|
deba@57
|
146 |
}
|
deba@57
|
147 |
else {
|
alpar@209
|
148 |
Parent::nextOut(e);
|
deba@57
|
149 |
}
|
deba@57
|
150 |
}
|
deba@57
|
151 |
|
deba@57
|
152 |
void firstIn(Arc &e, const Node &n) const {
|
deba@57
|
153 |
Parent::firstOut(e,n);
|
deba@57
|
154 |
if( Edge(e) != INVALID ) {
|
alpar@209
|
155 |
e.forward = false;
|
deba@57
|
156 |
}
|
deba@57
|
157 |
else {
|
alpar@209
|
158 |
Parent::firstIn(e,n);
|
alpar@209
|
159 |
e.forward = true;
|
deba@57
|
160 |
}
|
deba@57
|
161 |
}
|
deba@57
|
162 |
void nextIn(Arc &e) const {
|
deba@57
|
163 |
if( ! e.forward ) {
|
alpar@209
|
164 |
Node n = Parent::source(e);
|
alpar@209
|
165 |
Parent::nextOut(e);
|
alpar@209
|
166 |
if( Edge(e) == INVALID ) {
|
alpar@209
|
167 |
Parent::firstIn(e, n);
|
alpar@209
|
168 |
e.forward = true;
|
alpar@209
|
169 |
}
|
deba@57
|
170 |
}
|
deba@57
|
171 |
else {
|
alpar@209
|
172 |
Parent::nextIn(e);
|
deba@57
|
173 |
}
|
deba@57
|
174 |
}
|
deba@57
|
175 |
|
deba@57
|
176 |
void firstInc(Edge &e, bool &d, const Node &n) const {
|
deba@57
|
177 |
d = true;
|
deba@57
|
178 |
Parent::firstOut(e, n);
|
deba@57
|
179 |
if (e != INVALID) return;
|
deba@57
|
180 |
d = false;
|
deba@57
|
181 |
Parent::firstIn(e, n);
|
deba@57
|
182 |
}
|
deba@57
|
183 |
|
deba@57
|
184 |
void nextInc(Edge &e, bool &d) const {
|
deba@57
|
185 |
if (d) {
|
alpar@209
|
186 |
Node s = Parent::source(e);
|
alpar@209
|
187 |
Parent::nextOut(e);
|
alpar@209
|
188 |
if (e != INVALID) return;
|
alpar@209
|
189 |
d = false;
|
alpar@209
|
190 |
Parent::firstIn(e, s);
|
deba@57
|
191 |
} else {
|
alpar@209
|
192 |
Parent::nextIn(e);
|
deba@57
|
193 |
}
|
deba@57
|
194 |
}
|
deba@57
|
195 |
|
deba@57
|
196 |
Node nodeFromId(int ix) const {
|
deba@57
|
197 |
return Parent::nodeFromId(ix);
|
deba@57
|
198 |
}
|
deba@57
|
199 |
|
deba@57
|
200 |
Arc arcFromId(int ix) const {
|
deba@57
|
201 |
return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
|
deba@57
|
202 |
}
|
deba@57
|
203 |
|
deba@57
|
204 |
Edge edgeFromId(int ix) const {
|
deba@57
|
205 |
return Parent::arcFromId(ix);
|
deba@57
|
206 |
}
|
deba@57
|
207 |
|
deba@57
|
208 |
int id(const Node &n) const {
|
deba@57
|
209 |
return Parent::id(n);
|
deba@57
|
210 |
}
|
deba@57
|
211 |
|
deba@57
|
212 |
int id(const Edge &e) const {
|
deba@57
|
213 |
return Parent::id(e);
|
deba@57
|
214 |
}
|
deba@57
|
215 |
|
deba@57
|
216 |
int id(const Arc &e) const {
|
deba@57
|
217 |
return 2 * Parent::id(e) + int(e.forward);
|
deba@57
|
218 |
}
|
deba@57
|
219 |
|
deba@57
|
220 |
int maxNodeId() const {
|
deba@57
|
221 |
return Parent::maxNodeId();
|
deba@57
|
222 |
}
|
deba@57
|
223 |
|
deba@57
|
224 |
int maxArcId() const {
|
deba@57
|
225 |
return 2 * Parent::maxArcId() + 1;
|
deba@57
|
226 |
}
|
deba@57
|
227 |
|
deba@57
|
228 |
int maxEdgeId() const {
|
deba@57
|
229 |
return Parent::maxArcId();
|
deba@57
|
230 |
}
|
deba@57
|
231 |
|
deba@57
|
232 |
|
deba@57
|
233 |
int arcNum() const {
|
deba@57
|
234 |
return 2 * Parent::arcNum();
|
deba@57
|
235 |
}
|
deba@57
|
236 |
|
deba@57
|
237 |
int edgeNum() const {
|
deba@57
|
238 |
return Parent::arcNum();
|
deba@57
|
239 |
}
|
deba@57
|
240 |
|
deba@57
|
241 |
Arc findArc(Node s, Node t, Arc p = INVALID) const {
|
deba@57
|
242 |
if (p == INVALID) {
|
alpar@209
|
243 |
Edge arc = Parent::findArc(s, t);
|
alpar@209
|
244 |
if (arc != INVALID) return direct(arc, true);
|
alpar@209
|
245 |
arc = Parent::findArc(t, s);
|
alpar@209
|
246 |
if (arc != INVALID) return direct(arc, false);
|
deba@57
|
247 |
} else if (direction(p)) {
|
alpar@209
|
248 |
Edge arc = Parent::findArc(s, t, p);
|
alpar@209
|
249 |
if (arc != INVALID) return direct(arc, true);
|
alpar@209
|
250 |
arc = Parent::findArc(t, s);
|
alpar@209
|
251 |
if (arc != INVALID) return direct(arc, false);
|
deba@57
|
252 |
} else {
|
alpar@209
|
253 |
Edge arc = Parent::findArc(t, s, p);
|
alpar@209
|
254 |
if (arc != INVALID) return direct(arc, false);
|
deba@57
|
255 |
}
|
deba@57
|
256 |
return INVALID;
|
deba@57
|
257 |
}
|
deba@57
|
258 |
|
deba@57
|
259 |
Edge findEdge(Node s, Node t, Edge p = INVALID) const {
|
deba@57
|
260 |
if (s != t) {
|
deba@57
|
261 |
if (p == INVALID) {
|
deba@57
|
262 |
Edge arc = Parent::findArc(s, t);
|
deba@57
|
263 |
if (arc != INVALID) return arc;
|
deba@57
|
264 |
arc = Parent::findArc(t, s);
|
deba@57
|
265 |
if (arc != INVALID) return arc;
|
deba@57
|
266 |
} else if (Parent::s(p) == s) {
|
deba@57
|
267 |
Edge arc = Parent::findArc(s, t, p);
|
deba@57
|
268 |
if (arc != INVALID) return arc;
|
deba@57
|
269 |
arc = Parent::findArc(t, s);
|
alpar@209
|
270 |
if (arc != INVALID) return arc;
|
deba@57
|
271 |
} else {
|
deba@57
|
272 |
Edge arc = Parent::findArc(t, s, p);
|
alpar@209
|
273 |
if (arc != INVALID) return arc;
|
deba@57
|
274 |
}
|
deba@57
|
275 |
} else {
|
deba@57
|
276 |
return Parent::findArc(s, t, p);
|
deba@57
|
277 |
}
|
deba@57
|
278 |
return INVALID;
|
deba@57
|
279 |
}
|
deba@57
|
280 |
};
|
deba@57
|
281 |
|
deba@57
|
282 |
template <typename Base>
|
deba@57
|
283 |
class BidirBpGraphExtender : public Base {
|
deba@57
|
284 |
public:
|
deba@57
|
285 |
typedef Base Parent;
|
deba@57
|
286 |
typedef BidirBpGraphExtender Digraph;
|
deba@57
|
287 |
|
deba@57
|
288 |
typedef typename Parent::Node Node;
|
deba@57
|
289 |
typedef typename Parent::Edge Edge;
|
deba@57
|
290 |
|
deba@57
|
291 |
|
deba@57
|
292 |
using Parent::first;
|
deba@57
|
293 |
using Parent::next;
|
deba@57
|
294 |
|
deba@57
|
295 |
using Parent::id;
|
deba@57
|
296 |
|
deba@57
|
297 |
class Red : public Node {
|
deba@57
|
298 |
friend class BidirBpGraphExtender;
|
deba@57
|
299 |
public:
|
deba@57
|
300 |
Red() {}
|
deba@57
|
301 |
Red(const Node& node) : Node(node) {
|
alpar@209
|
302 |
LEMON_ASSERT(Parent::red(node) || node == INVALID,
|
alpar@209
|
303 |
typename Parent::NodeSetError());
|
deba@57
|
304 |
}
|
deba@57
|
305 |
Red& operator=(const Node& node) {
|
alpar@209
|
306 |
LEMON_ASSERT(Parent::red(node) || node == INVALID,
|
alpar@209
|
307 |
typename Parent::NodeSetError());
|
deba@57
|
308 |
Node::operator=(node);
|
deba@57
|
309 |
return *this;
|
deba@57
|
310 |
}
|
deba@57
|
311 |
Red(Invalid) : Node(INVALID) {}
|
deba@57
|
312 |
Red& operator=(Invalid) {
|
deba@57
|
313 |
Node::operator=(INVALID);
|
deba@57
|
314 |
return *this;
|
deba@57
|
315 |
}
|
deba@57
|
316 |
};
|
deba@57
|
317 |
|
deba@57
|
318 |
void first(Red& node) const {
|
deba@57
|
319 |
Parent::firstRed(static_cast<Node&>(node));
|
deba@57
|
320 |
}
|
deba@57
|
321 |
void next(Red& node) const {
|
deba@57
|
322 |
Parent::nextRed(static_cast<Node&>(node));
|
deba@57
|
323 |
}
|
deba@57
|
324 |
|
deba@57
|
325 |
int id(const Red& node) const {
|
deba@57
|
326 |
return Parent::redId(node);
|
deba@57
|
327 |
}
|
deba@57
|
328 |
|
deba@57
|
329 |
class Blue : public Node {
|
deba@57
|
330 |
friend class BidirBpGraphExtender;
|
deba@57
|
331 |
public:
|
deba@57
|
332 |
Blue() {}
|
deba@57
|
333 |
Blue(const Node& node) : Node(node) {
|
alpar@209
|
334 |
LEMON_ASSERT(Parent::blue(node) || node == INVALID,
|
alpar@209
|
335 |
typename Parent::NodeSetError());
|
deba@57
|
336 |
}
|
deba@57
|
337 |
Blue& operator=(const Node& node) {
|
alpar@209
|
338 |
LEMON_ASSERT(Parent::blue(node) || node == INVALID,
|
alpar@209
|
339 |
typename Parent::NodeSetError());
|
deba@57
|
340 |
Node::operator=(node);
|
deba@57
|
341 |
return *this;
|
deba@57
|
342 |
}
|
deba@57
|
343 |
Blue(Invalid) : Node(INVALID) {}
|
deba@57
|
344 |
Blue& operator=(Invalid) {
|
deba@57
|
345 |
Node::operator=(INVALID);
|
deba@57
|
346 |
return *this;
|
deba@57
|
347 |
}
|
deba@57
|
348 |
};
|
deba@57
|
349 |
|
deba@57
|
350 |
void first(Blue& node) const {
|
deba@57
|
351 |
Parent::firstBlue(static_cast<Node&>(node));
|
deba@57
|
352 |
}
|
deba@57
|
353 |
void next(Blue& node) const {
|
deba@57
|
354 |
Parent::nextBlue(static_cast<Node&>(node));
|
deba@57
|
355 |
}
|
alpar@209
|
356 |
|
deba@57
|
357 |
int id(const Blue& node) const {
|
deba@57
|
358 |
return Parent::redId(node);
|
deba@57
|
359 |
}
|
deba@57
|
360 |
|
deba@57
|
361 |
Node source(const Edge& arc) const {
|
deba@57
|
362 |
return red(arc);
|
deba@57
|
363 |
}
|
deba@57
|
364 |
Node target(const Edge& arc) const {
|
deba@57
|
365 |
return blue(arc);
|
deba@57
|
366 |
}
|
deba@57
|
367 |
|
deba@57
|
368 |
void firstInc(Edge& arc, bool& dir, const Node& node) const {
|
deba@57
|
369 |
if (Parent::red(node)) {
|
alpar@209
|
370 |
Parent::firstFromRed(arc, node);
|
alpar@209
|
371 |
dir = true;
|
deba@57
|
372 |
} else {
|
alpar@209
|
373 |
Parent::firstFromBlue(arc, node);
|
alpar@209
|
374 |
dir = static_cast<Edge&>(arc) == INVALID;
|
deba@57
|
375 |
}
|
deba@57
|
376 |
}
|
deba@57
|
377 |
void nextInc(Edge& arc, bool& dir) const {
|
deba@57
|
378 |
if (dir) {
|
alpar@209
|
379 |
Parent::nextFromRed(arc);
|
deba@57
|
380 |
} else {
|
alpar@209
|
381 |
Parent::nextFromBlue(arc);
|
alpar@209
|
382 |
if (arc == INVALID) dir = true;
|
deba@57
|
383 |
}
|
deba@57
|
384 |
}
|
deba@57
|
385 |
|
deba@57
|
386 |
class Arc : public Edge {
|
deba@57
|
387 |
friend class BidirBpGraphExtender;
|
deba@57
|
388 |
protected:
|
deba@57
|
389 |
bool forward;
|
deba@57
|
390 |
|
deba@57
|
391 |
Arc(const Edge& arc, bool _forward)
|
alpar@209
|
392 |
: Edge(arc), forward(_forward) {}
|
deba@57
|
393 |
|
deba@57
|
394 |
public:
|
deba@57
|
395 |
Arc() {}
|
deba@57
|
396 |
Arc (Invalid) : Edge(INVALID), forward(true) {}
|
deba@57
|
397 |
bool operator==(const Arc& i) const {
|
alpar@209
|
398 |
return Edge::operator==(i) && forward == i.forward;
|
deba@57
|
399 |
}
|
deba@57
|
400 |
bool operator!=(const Arc& i) const {
|
alpar@209
|
401 |
return Edge::operator!=(i) || forward != i.forward;
|
deba@57
|
402 |
}
|
deba@57
|
403 |
bool operator<(const Arc& i) const {
|
alpar@209
|
404 |
return Edge::operator<(i) ||
|
alpar@209
|
405 |
(!(i.forward<forward) && Edge(*this)<Edge(i));
|
deba@57
|
406 |
}
|
deba@57
|
407 |
};
|
deba@57
|
408 |
|
deba@57
|
409 |
void first(Arc& arc) const {
|
deba@57
|
410 |
Parent::first(static_cast<Edge&>(arc));
|
deba@57
|
411 |
arc.forward = true;
|
deba@57
|
412 |
}
|
deba@57
|
413 |
|
deba@57
|
414 |
void next(Arc& arc) const {
|
deba@57
|
415 |
if (!arc.forward) {
|
alpar@209
|
416 |
Parent::next(static_cast<Edge&>(arc));
|
deba@57
|
417 |
}
|
deba@57
|
418 |
arc.forward = !arc.forward;
|
deba@57
|
419 |
}
|
deba@57
|
420 |
|
deba@57
|
421 |
void firstOut(Arc& arc, const Node& node) const {
|
deba@57
|
422 |
if (Parent::red(node)) {
|
alpar@209
|
423 |
Parent::firstFromRed(arc, node);
|
alpar@209
|
424 |
arc.forward = true;
|
deba@57
|
425 |
} else {
|
alpar@209
|
426 |
Parent::firstFromBlue(arc, node);
|
alpar@209
|
427 |
arc.forward = static_cast<Edge&>(arc) == INVALID;
|
deba@57
|
428 |
}
|
deba@57
|
429 |
}
|
deba@57
|
430 |
void nextOut(Arc& arc) const {
|
deba@57
|
431 |
if (arc.forward) {
|
alpar@209
|
432 |
Parent::nextFromRed(arc);
|
deba@57
|
433 |
} else {
|
alpar@209
|
434 |
Parent::nextFromBlue(arc);
|
deba@57
|
435 |
arc.forward = static_cast<Edge&>(arc) == INVALID;
|
deba@57
|
436 |
}
|
deba@57
|
437 |
}
|
deba@57
|
438 |
|
deba@57
|
439 |
void firstIn(Arc& arc, const Node& node) const {
|
deba@57
|
440 |
if (Parent::blue(node)) {
|
alpar@209
|
441 |
Parent::firstFromBlue(arc, node);
|
alpar@209
|
442 |
arc.forward = true;
|
deba@57
|
443 |
} else {
|
alpar@209
|
444 |
Parent::firstFromRed(arc, node);
|
alpar@209
|
445 |
arc.forward = static_cast<Edge&>(arc) == INVALID;
|
deba@57
|
446 |
}
|
deba@57
|
447 |
}
|
deba@57
|
448 |
void nextIn(Arc& arc) const {
|
deba@57
|
449 |
if (arc.forward) {
|
alpar@209
|
450 |
Parent::nextFromBlue(arc);
|
deba@57
|
451 |
} else {
|
alpar@209
|
452 |
Parent::nextFromRed(arc);
|
alpar@209
|
453 |
arc.forward = static_cast<Edge&>(arc) == INVALID;
|
deba@57
|
454 |
}
|
deba@57
|
455 |
}
|
deba@57
|
456 |
|
deba@57
|
457 |
Node source(const Arc& arc) const {
|
deba@57
|
458 |
return arc.forward ? Parent::red(arc) : Parent::blue(arc);
|
deba@57
|
459 |
}
|
deba@57
|
460 |
Node target(const Arc& arc) const {
|
deba@57
|
461 |
return arc.forward ? Parent::blue(arc) : Parent::red(arc);
|
deba@57
|
462 |
}
|
deba@57
|
463 |
|
deba@57
|
464 |
int id(const Arc& arc) const {
|
alpar@209
|
465 |
return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
|
deba@57
|
466 |
(arc.forward ? 0 : 1);
|
deba@57
|
467 |
}
|
deba@57
|
468 |
Arc arcFromId(int ix) const {
|
deba@57
|
469 |
return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
|
deba@57
|
470 |
}
|
deba@57
|
471 |
int maxArcId() const {
|
deba@57
|
472 |
return (Parent::maxEdgeId() << 1) + 1;
|
deba@57
|
473 |
}
|
deba@57
|
474 |
|
deba@57
|
475 |
bool direction(const Arc& arc) const {
|
deba@57
|
476 |
return arc.forward;
|
deba@57
|
477 |
}
|
deba@57
|
478 |
|
deba@57
|
479 |
Arc direct(const Edge& arc, bool dir) const {
|
deba@57
|
480 |
return Arc(arc, dir);
|
deba@57
|
481 |
}
|
deba@57
|
482 |
|
deba@57
|
483 |
int arcNum() const {
|
deba@57
|
484 |
return 2 * Parent::edgeNum();
|
deba@57
|
485 |
}
|
deba@57
|
486 |
|
deba@57
|
487 |
int edgeNum() const {
|
deba@57
|
488 |
return Parent::edgeNum();
|
deba@57
|
489 |
}
|
deba@57
|
490 |
|
deba@57
|
491 |
|
deba@57
|
492 |
};
|
deba@57
|
493 |
}
|
deba@57
|
494 |
|
deba@57
|
495 |
#endif
|