|
1 /* -*- C++ -*- |
|
2 * |
|
3 * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++ |
|
4 * optimization library |
|
5 * |
|
6 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi |
|
7 * Kutatocsoport (Egervary Combinatorial Optimization Research Group, |
|
8 * EGRES). |
|
9 * |
|
10 * Permission to use, modify and distribute this software is granted |
|
11 * provided that this copyright notice appears in all copies. For |
|
12 * precise terms see the accompanying LICENSE file. |
|
13 * |
|
14 * This software is provided "AS IS" with no warranty of any kind, |
|
15 * express or implied, and with no claim as to its suitability for any |
|
16 * purpose. |
|
17 * |
|
18 */ |
|
19 |
|
20 #ifndef LEMON_UNDIR_GRAPH_EXTENDER_H |
|
21 #define LEMON_UNDIR_GRAPH_EXTENDER_H |
|
22 |
|
23 #include <lemon/invalid.h> |
|
24 |
|
25 namespace lemon { |
|
26 |
|
27 template <typename _Base> |
|
28 class UndirGraphExtender : public _Base { |
|
29 typedef _Base Parent; |
|
30 typedef UndirGraphExtender Graph; |
|
31 |
|
32 public: |
|
33 |
|
34 typedef typename Parent::Edge UndirEdge; |
|
35 typedef typename Parent::Node Node; |
|
36 |
|
37 class Edge : public UndirEdge { |
|
38 friend class Graph; |
|
39 |
|
40 protected: |
|
41 // FIXME: Marci use opposite logic in his graph wrappers. It would |
|
42 // be reasonable to syncronize... |
|
43 bool forward; |
|
44 |
|
45 public: |
|
46 Edge() {} |
|
47 /// Construct a direct edge from undirect edge and a direction. |
|
48 Edge(const UndirEdge &ue, bool _forward) : |
|
49 UndirEdge(ue), forward(_forward) {} |
|
50 /// Invalid edge constructor |
|
51 Edge(Invalid i) : UndirEdge(i), forward(false) {} |
|
52 |
|
53 bool operator==(const Edge &that) const { |
|
54 return forward==that.forward && UndirEdge(*this)==UndirEdge(that); |
|
55 } |
|
56 bool operator!=(const Edge &that) const { |
|
57 return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that); |
|
58 } |
|
59 bool operator<(const Edge &that) const { |
|
60 return forward<that.forward || |
|
61 (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that)); |
|
62 } |
|
63 }; |
|
64 |
|
65 |
|
66 /// \brief Returns the Edge of opposite direction. |
|
67 /// |
|
68 /// \bug Is this a good name for this? Or "reverse" is better? |
|
69 Edge opposite(const Edge &e) const { |
|
70 return Edge(e,!e.forward); |
|
71 } |
|
72 |
|
73 /// Tail of the given Edge. |
|
74 Node tail(const Edge &e) const { |
|
75 return e.forward ? Parent::tail(e) : Parent::head(e); |
|
76 } |
|
77 |
|
78 /// \todo Shouldn't the "tail" of an undirected edge be called "aNode" |
|
79 /// or something??? |
|
80 using Parent::tail; |
|
81 |
|
82 /// Head of the given Edge. |
|
83 Node head(const Edge &e) const { |
|
84 return e.forward ? Parent::head(e) : Parent::tail(e); |
|
85 } |
|
86 |
|
87 /// \todo Shouldn't the "head" of an undirected edge be called "bNode" |
|
88 /// or something??? |
|
89 using Parent::head; |
|
90 |
|
91 /// Returns whether the given directed edge is same orientation as the |
|
92 /// corresponding undirected edge. |
|
93 /// |
|
94 /// \todo reference to the corresponding point of the undirected graph |
|
95 /// concept. "What does the direction of an undirected edge mean?" |
|
96 bool forward(const Edge &e) const { return e.forward; } |
|
97 |
|
98 Node oppsiteNode(const Node &n, const Edge &e) const { |
|
99 if( n == Parent::tail(e)) |
|
100 return Parent::head(e); |
|
101 else if( n == Parent::head(e)) |
|
102 return Parent::tail(e); |
|
103 else |
|
104 return INVALID; |
|
105 } |
|
106 |
|
107 |
|
108 using Parent::first; |
|
109 void first(Edge &e) const { |
|
110 Parent::first(e); |
|
111 e.forward=true; |
|
112 } |
|
113 |
|
114 using Parent::next; |
|
115 void next(Edge &e) const { |
|
116 if( e.forward ) { |
|
117 e.forward = false; |
|
118 } |
|
119 else { |
|
120 Parent::next(e); |
|
121 e.forward = true; |
|
122 } |
|
123 } |
|
124 |
|
125 void firstOut(Edge &e, const Node &n) const { |
|
126 Parent::firstOut(e,n); |
|
127 if( UndirEdge(e) != INVALID ) { |
|
128 e.forward = true; |
|
129 } |
|
130 else { |
|
131 Parent::firstIn(e,n); |
|
132 e.forward = false; |
|
133 } |
|
134 } |
|
135 void firstIn(Edge &e, const Node &n) const { |
|
136 Parent::firstIn(e,n); |
|
137 if( UndirEdge(e) != INVALID ) { |
|
138 e.forward = true; |
|
139 } |
|
140 else { |
|
141 Parent::firstOut(e,n); |
|
142 e.forward = false; |
|
143 } |
|
144 } |
|
145 |
|
146 void nextOut(Edge &e) const { |
|
147 if( e.forward ) { |
|
148 Parent::nextOut(e); |
|
149 if( UndirEdge(e) == INVALID ) { |
|
150 Parent::firstIn(e, Parent::tail(e)); |
|
151 e.forward = false; |
|
152 } |
|
153 } |
|
154 else { |
|
155 Parent::nextIn(e); |
|
156 } |
|
157 } |
|
158 void nextIn(Edge &e) const { |
|
159 if( e.forward ) { |
|
160 Parent::nextIn(e); |
|
161 if( UndirEdge(e) == INVALID ) { |
|
162 Parent::firstOut(e, Parent::head(e)); |
|
163 e.forward = false; |
|
164 } |
|
165 } |
|
166 else { |
|
167 Parent::nextOut(e); |
|
168 } |
|
169 } |
|
170 |
|
171 // Miscellaneous stuff: |
|
172 |
|
173 /// \todo these methods (id, maxEdgeId) should be moved into separate |
|
174 /// Extender |
|
175 |
|
176 using Parent::id; |
|
177 |
|
178 int id(const Edge &e) const { |
|
179 return 2*Parent::id(e) + int(e.forward); |
|
180 } |
|
181 |
|
182 int maxEdgeId() const { |
|
183 return 2*Parent::maxEdgeId() + 1; |
|
184 } |
|
185 int maxUndirEdgeId() const { |
|
186 return Parent::maxEdgeId(); |
|
187 } |
|
188 |
|
189 }; |
|
190 |
|
191 } |
|
192 |
|
193 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H |