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 |
///\ingroup graph_concepts
|
deba@57
|
20 |
///\file
|
deba@57
|
21 |
///\brief The concept of Undirected Graphs.
|
deba@57
|
22 |
|
deba@57
|
23 |
#ifndef LEMON_CONCEPT_GRAPH_H
|
deba@57
|
24 |
#define LEMON_CONCEPT_GRAPH_H
|
deba@57
|
25 |
|
deba@57
|
26 |
#include <lemon/concepts/graph_components.h>
|
deba@57
|
27 |
#include <lemon/concepts/graph.h>
|
deba@220
|
28 |
#include <lemon/core.h>
|
deba@57
|
29 |
|
deba@57
|
30 |
namespace lemon {
|
deba@57
|
31 |
namespace concepts {
|
deba@57
|
32 |
|
deba@57
|
33 |
/// \ingroup graph_concepts
|
deba@57
|
34 |
///
|
deba@57
|
35 |
/// \brief Class describing the concept of Undirected Graphs.
|
deba@57
|
36 |
///
|
deba@57
|
37 |
/// This class describes the common interface of all Undirected
|
deba@57
|
38 |
/// Graphs.
|
deba@57
|
39 |
///
|
deba@57
|
40 |
/// As all concept describing classes it provides only interface
|
deba@57
|
41 |
/// without any sensible implementation. So any algorithm for
|
deba@57
|
42 |
/// undirected graph should compile with this class, but it will not
|
deba@57
|
43 |
/// run properly, of course.
|
deba@57
|
44 |
///
|
deba@57
|
45 |
/// The LEMON undirected graphs also fulfill the concept of
|
deba@57
|
46 |
/// directed graphs (\ref lemon::concepts::Digraph "Digraph
|
deba@57
|
47 |
/// Concept"). Each edges can be seen as two opposite
|
deba@57
|
48 |
/// directed arc and consequently the undirected graph can be
|
deba@57
|
49 |
/// seen as the direceted graph of these directed arcs. The
|
deba@57
|
50 |
/// Graph has the Edge inner class for the edges and
|
deba@57
|
51 |
/// the Arc type for the directed arcs. The Arc type is
|
deba@57
|
52 |
/// convertible to Edge or inherited from it so from a directed
|
deba@57
|
53 |
/// arc we can get the represented edge.
|
deba@57
|
54 |
///
|
deba@57
|
55 |
/// In the sense of the LEMON each edge has a default
|
deba@57
|
56 |
/// direction (it should be in every computer implementation,
|
deba@57
|
57 |
/// because the order of edge's nodes defines an
|
deba@57
|
58 |
/// orientation). With the default orientation we can define that
|
deba@57
|
59 |
/// the directed arc is forward or backward directed. With the \c
|
deba@57
|
60 |
/// direction() and \c direct() function we can get the direction
|
deba@57
|
61 |
/// of the directed arc and we can direct an edge.
|
deba@57
|
62 |
///
|
deba@57
|
63 |
/// The EdgeIt is an iterator for the edges. We can use
|
deba@57
|
64 |
/// the EdgeMap to map values for the edges. The InArcIt and
|
deba@57
|
65 |
/// OutArcIt iterates on the same edges but with opposite
|
deba@78
|
66 |
/// direction. The IncEdgeIt iterates also on the same edges
|
deba@57
|
67 |
/// as the OutArcIt and InArcIt but it is not convertible to Arc just
|
alpar@209
|
68 |
/// to Edge.
|
deba@57
|
69 |
class Graph {
|
deba@57
|
70 |
public:
|
deba@57
|
71 |
/// \brief The undirected graph should be tagged by the
|
deba@57
|
72 |
/// UndirectedTag.
|
deba@57
|
73 |
///
|
deba@57
|
74 |
/// The undirected graph should be tagged by the UndirectedTag. This
|
alpar@209
|
75 |
/// tag helps the enable_if technics to make compile time
|
alpar@209
|
76 |
/// specializations for undirected graphs.
|
deba@57
|
77 |
typedef True UndirectedTag;
|
deba@57
|
78 |
|
alpar@209
|
79 |
/// \brief The base type of node iterators,
|
deba@57
|
80 |
/// or in other words, the trivial node iterator.
|
deba@57
|
81 |
///
|
deba@57
|
82 |
/// This is the base type of each node iterator,
|
deba@57
|
83 |
/// thus each kind of node iterator converts to this.
|
alpar@209
|
84 |
/// More precisely each kind of node iterator should be inherited
|
deba@57
|
85 |
/// from the trivial node iterator.
|
deba@57
|
86 |
class Node {
|
deba@57
|
87 |
public:
|
deba@57
|
88 |
/// Default constructor
|
deba@57
|
89 |
|
deba@57
|
90 |
/// @warning The default constructor sets the iterator
|
deba@57
|
91 |
/// to an undefined value.
|
deba@57
|
92 |
Node() { }
|
deba@57
|
93 |
/// Copy constructor.
|
deba@57
|
94 |
|
deba@57
|
95 |
/// Copy constructor.
|
deba@57
|
96 |
///
|
deba@57
|
97 |
Node(const Node&) { }
|
deba@57
|
98 |
|
deba@57
|
99 |
/// Invalid constructor \& conversion.
|
deba@57
|
100 |
|
deba@57
|
101 |
/// This constructor initializes the iterator to be invalid.
|
deba@57
|
102 |
/// \sa Invalid for more details.
|
deba@57
|
103 |
Node(Invalid) { }
|
deba@57
|
104 |
/// Equality operator
|
deba@57
|
105 |
|
deba@57
|
106 |
/// Two iterators are equal if and only if they point to the
|
deba@57
|
107 |
/// same object or both are invalid.
|
deba@57
|
108 |
bool operator==(Node) const { return true; }
|
deba@57
|
109 |
|
deba@57
|
110 |
/// Inequality operator
|
alpar@209
|
111 |
|
deba@57
|
112 |
/// \sa operator==(Node n)
|
deba@57
|
113 |
///
|
deba@57
|
114 |
bool operator!=(Node) const { return true; }
|
deba@57
|
115 |
|
alpar@209
|
116 |
/// Artificial ordering operator.
|
alpar@209
|
117 |
|
alpar@209
|
118 |
/// To allow the use of graph descriptors as key type in std::map or
|
alpar@209
|
119 |
/// similar associative container we require this.
|
alpar@209
|
120 |
///
|
alpar@209
|
121 |
/// \note This operator only have to define some strict ordering of
|
alpar@209
|
122 |
/// the items; this order has nothing to do with the iteration
|
alpar@209
|
123 |
/// ordering of the items.
|
alpar@209
|
124 |
bool operator<(Node) const { return false; }
|
deba@57
|
125 |
|
deba@57
|
126 |
};
|
alpar@209
|
127 |
|
deba@57
|
128 |
/// This iterator goes through each node.
|
deba@57
|
129 |
|
deba@57
|
130 |
/// This iterator goes through each node.
|
deba@57
|
131 |
/// Its usage is quite simple, for example you can count the number
|
deba@57
|
132 |
/// of nodes in graph \c g of type \c Graph like this:
|
deba@57
|
133 |
///\code
|
deba@57
|
134 |
/// int count=0;
|
deba@57
|
135 |
/// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
|
deba@57
|
136 |
///\endcode
|
deba@57
|
137 |
class NodeIt : public Node {
|
deba@57
|
138 |
public:
|
deba@57
|
139 |
/// Default constructor
|
deba@57
|
140 |
|
deba@57
|
141 |
/// @warning The default constructor sets the iterator
|
deba@57
|
142 |
/// to an undefined value.
|
deba@57
|
143 |
NodeIt() { }
|
deba@57
|
144 |
/// Copy constructor.
|
alpar@209
|
145 |
|
deba@57
|
146 |
/// Copy constructor.
|
deba@57
|
147 |
///
|
deba@57
|
148 |
NodeIt(const NodeIt& n) : Node(n) { }
|
deba@57
|
149 |
/// Invalid constructor \& conversion.
|
deba@57
|
150 |
|
deba@57
|
151 |
/// Initialize the iterator to be invalid.
|
deba@57
|
152 |
/// \sa Invalid for more details.
|
deba@57
|
153 |
NodeIt(Invalid) { }
|
deba@57
|
154 |
/// Sets the iterator to the first node.
|
deba@57
|
155 |
|
deba@57
|
156 |
/// Sets the iterator to the first node of \c g.
|
deba@57
|
157 |
///
|
deba@57
|
158 |
NodeIt(const Graph&) { }
|
deba@57
|
159 |
/// Node -> NodeIt conversion.
|
deba@57
|
160 |
|
alpar@209
|
161 |
/// Sets the iterator to the node of \c the graph pointed by
|
alpar@209
|
162 |
/// the trivial iterator.
|
alpar@209
|
163 |
/// This feature necessitates that each time we
|
deba@57
|
164 |
/// iterate the arc-set, the iteration order is the same.
|
deba@57
|
165 |
NodeIt(const Graph&, const Node&) { }
|
deba@57
|
166 |
/// Next node.
|
deba@57
|
167 |
|
deba@57
|
168 |
/// Assign the iterator to the next node.
|
deba@57
|
169 |
///
|
deba@57
|
170 |
NodeIt& operator++() { return *this; }
|
deba@57
|
171 |
};
|
alpar@209
|
172 |
|
alpar@209
|
173 |
|
deba@57
|
174 |
/// The base type of the edge iterators.
|
deba@57
|
175 |
|
deba@57
|
176 |
/// The base type of the edge iterators.
|
deba@57
|
177 |
///
|
deba@57
|
178 |
class Edge {
|
deba@57
|
179 |
public:
|
deba@57
|
180 |
/// Default constructor
|
deba@57
|
181 |
|
deba@57
|
182 |
/// @warning The default constructor sets the iterator
|
deba@57
|
183 |
/// to an undefined value.
|
deba@57
|
184 |
Edge() { }
|
deba@57
|
185 |
/// Copy constructor.
|
deba@57
|
186 |
|
deba@57
|
187 |
/// Copy constructor.
|
deba@57
|
188 |
///
|
deba@57
|
189 |
Edge(const Edge&) { }
|
deba@57
|
190 |
/// Initialize the iterator to be invalid.
|
deba@57
|
191 |
|
deba@57
|
192 |
/// Initialize the iterator to be invalid.
|
deba@57
|
193 |
///
|
deba@57
|
194 |
Edge(Invalid) { }
|
deba@57
|
195 |
/// Equality operator
|
deba@57
|
196 |
|
deba@57
|
197 |
/// Two iterators are equal if and only if they point to the
|
deba@57
|
198 |
/// same object or both are invalid.
|
deba@57
|
199 |
bool operator==(Edge) const { return true; }
|
deba@57
|
200 |
/// Inequality operator
|
deba@57
|
201 |
|
deba@57
|
202 |
/// \sa operator==(Edge n)
|
deba@57
|
203 |
///
|
deba@57
|
204 |
bool operator!=(Edge) const { return true; }
|
deba@57
|
205 |
|
alpar@209
|
206 |
/// Artificial ordering operator.
|
alpar@209
|
207 |
|
alpar@209
|
208 |
/// To allow the use of graph descriptors as key type in std::map or
|
alpar@209
|
209 |
/// similar associative container we require this.
|
alpar@209
|
210 |
///
|
alpar@209
|
211 |
/// \note This operator only have to define some strict ordering of
|
alpar@209
|
212 |
/// the items; this order has nothing to do with the iteration
|
alpar@209
|
213 |
/// ordering of the items.
|
alpar@209
|
214 |
bool operator<(Edge) const { return false; }
|
deba@57
|
215 |
};
|
deba@57
|
216 |
|
deba@57
|
217 |
/// This iterator goes through each edge.
|
deba@57
|
218 |
|
deba@57
|
219 |
/// This iterator goes through each edge of a graph.
|
deba@57
|
220 |
/// Its usage is quite simple, for example you can count the number
|
deba@57
|
221 |
/// of edges in a graph \c g of type \c Graph as follows:
|
deba@57
|
222 |
///\code
|
deba@57
|
223 |
/// int count=0;
|
deba@57
|
224 |
/// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
|
deba@57
|
225 |
///\endcode
|
deba@57
|
226 |
class EdgeIt : public Edge {
|
deba@57
|
227 |
public:
|
deba@57
|
228 |
/// Default constructor
|
deba@57
|
229 |
|
deba@57
|
230 |
/// @warning The default constructor sets the iterator
|
deba@57
|
231 |
/// to an undefined value.
|
deba@57
|
232 |
EdgeIt() { }
|
deba@57
|
233 |
/// Copy constructor.
|
deba@57
|
234 |
|
deba@57
|
235 |
/// Copy constructor.
|
deba@57
|
236 |
///
|
deba@57
|
237 |
EdgeIt(const EdgeIt& e) : Edge(e) { }
|
deba@57
|
238 |
/// Initialize the iterator to be invalid.
|
deba@57
|
239 |
|
deba@57
|
240 |
/// Initialize the iterator to be invalid.
|
deba@57
|
241 |
///
|
deba@57
|
242 |
EdgeIt(Invalid) { }
|
deba@57
|
243 |
/// This constructor sets the iterator to the first edge.
|
alpar@209
|
244 |
|
deba@57
|
245 |
/// This constructor sets the iterator to the first edge.
|
deba@57
|
246 |
EdgeIt(const Graph&) { }
|
deba@57
|
247 |
/// Edge -> EdgeIt conversion
|
deba@57
|
248 |
|
deba@57
|
249 |
/// Sets the iterator to the value of the trivial iterator.
|
deba@57
|
250 |
/// This feature necessitates that each time we
|
alpar@209
|
251 |
/// iterate the edge-set, the iteration order is the
|
alpar@209
|
252 |
/// same.
|
alpar@209
|
253 |
EdgeIt(const Graph&, const Edge&) { }
|
deba@57
|
254 |
/// Next edge
|
alpar@209
|
255 |
|
deba@57
|
256 |
/// Assign the iterator to the next edge.
|
deba@57
|
257 |
EdgeIt& operator++() { return *this; }
|
deba@57
|
258 |
};
|
deba@57
|
259 |
|
alpar@209
|
260 |
/// \brief This iterator goes trough the incident undirected
|
deba@57
|
261 |
/// arcs of a node.
|
deba@57
|
262 |
///
|
deba@57
|
263 |
/// This iterator goes trough the incident edges
|
alpar@209
|
264 |
/// of a certain node of a graph. You should assume that the
|
deba@57
|
265 |
/// loop arcs will be iterated twice.
|
alpar@209
|
266 |
///
|
deba@57
|
267 |
/// Its usage is quite simple, for example you can compute the
|
deba@57
|
268 |
/// degree (i.e. count the number of incident arcs of a node \c n
|
alpar@209
|
269 |
/// in graph \c g of type \c Graph as follows.
|
deba@57
|
270 |
///
|
deba@57
|
271 |
///\code
|
deba@57
|
272 |
/// int count=0;
|
deba@78
|
273 |
/// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
|
deba@57
|
274 |
///\endcode
|
deba@78
|
275 |
class IncEdgeIt : public Edge {
|
deba@57
|
276 |
public:
|
deba@57
|
277 |
/// Default constructor
|
deba@57
|
278 |
|
deba@57
|
279 |
/// @warning The default constructor sets the iterator
|
deba@57
|
280 |
/// to an undefined value.
|
deba@78
|
281 |
IncEdgeIt() { }
|
deba@57
|
282 |
/// Copy constructor.
|
deba@57
|
283 |
|
deba@57
|
284 |
/// Copy constructor.
|
deba@57
|
285 |
///
|
deba@78
|
286 |
IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
|
deba@57
|
287 |
/// Initialize the iterator to be invalid.
|
deba@57
|
288 |
|
deba@57
|
289 |
/// Initialize the iterator to be invalid.
|
deba@57
|
290 |
///
|
deba@78
|
291 |
IncEdgeIt(Invalid) { }
|
deba@57
|
292 |
/// This constructor sets the iterator to first incident arc.
|
alpar@209
|
293 |
|
deba@57
|
294 |
/// This constructor set the iterator to the first incident arc of
|
deba@57
|
295 |
/// the node.
|
deba@78
|
296 |
IncEdgeIt(const Graph&, const Node&) { }
|
deba@78
|
297 |
/// Edge -> IncEdgeIt conversion
|
deba@57
|
298 |
|
deba@57
|
299 |
/// Sets the iterator to the value of the trivial iterator \c e.
|
alpar@209
|
300 |
/// This feature necessitates that each time we
|
deba@57
|
301 |
/// iterate the arc-set, the iteration order is the same.
|
deba@78
|
302 |
IncEdgeIt(const Graph&, const Edge&) { }
|
deba@57
|
303 |
/// Next incident arc
|
deba@57
|
304 |
|
deba@57
|
305 |
/// Assign the iterator to the next incident arc
|
alpar@209
|
306 |
/// of the corresponding node.
|
deba@78
|
307 |
IncEdgeIt& operator++() { return *this; }
|
deba@57
|
308 |
};
|
deba@57
|
309 |
|
deba@57
|
310 |
/// The directed arc type.
|
deba@57
|
311 |
|
deba@57
|
312 |
/// The directed arc type. It can be converted to the
|
deba@57
|
313 |
/// edge or it should be inherited from the undirected
|
deba@57
|
314 |
/// arc.
|
deba@57
|
315 |
class Arc : public Edge {
|
deba@57
|
316 |
public:
|
deba@57
|
317 |
/// Default constructor
|
deba@57
|
318 |
|
deba@57
|
319 |
/// @warning The default constructor sets the iterator
|
deba@57
|
320 |
/// to an undefined value.
|
deba@57
|
321 |
Arc() { }
|
deba@57
|
322 |
/// Copy constructor.
|
deba@57
|
323 |
|
deba@57
|
324 |
/// Copy constructor.
|
deba@57
|
325 |
///
|
deba@57
|
326 |
Arc(const Arc& e) : Edge(e) { }
|
deba@57
|
327 |
/// Initialize the iterator to be invalid.
|
deba@57
|
328 |
|
deba@57
|
329 |
/// Initialize the iterator to be invalid.
|
deba@57
|
330 |
///
|
deba@57
|
331 |
Arc(Invalid) { }
|
deba@57
|
332 |
/// Equality operator
|
deba@57
|
333 |
|
deba@57
|
334 |
/// Two iterators are equal if and only if they point to the
|
deba@57
|
335 |
/// same object or both are invalid.
|
deba@57
|
336 |
bool operator==(Arc) const { return true; }
|
deba@57
|
337 |
/// Inequality operator
|
deba@57
|
338 |
|
deba@57
|
339 |
/// \sa operator==(Arc n)
|
deba@57
|
340 |
///
|
deba@57
|
341 |
bool operator!=(Arc) const { return true; }
|
deba@57
|
342 |
|
alpar@209
|
343 |
/// Artificial ordering operator.
|
alpar@209
|
344 |
|
alpar@209
|
345 |
/// To allow the use of graph descriptors as key type in std::map or
|
alpar@209
|
346 |
/// similar associative container we require this.
|
alpar@209
|
347 |
///
|
alpar@209
|
348 |
/// \note This operator only have to define some strict ordering of
|
alpar@209
|
349 |
/// the items; this order has nothing to do with the iteration
|
alpar@209
|
350 |
/// ordering of the items.
|
alpar@209
|
351 |
bool operator<(Arc) const { return false; }
|
alpar@209
|
352 |
|
alpar@209
|
353 |
};
|
deba@57
|
354 |
/// This iterator goes through each directed arc.
|
deba@57
|
355 |
|
deba@57
|
356 |
/// This iterator goes through each arc of a graph.
|
deba@57
|
357 |
/// Its usage is quite simple, for example you can count the number
|
deba@57
|
358 |
/// of arcs in a graph \c g of type \c Graph as follows:
|
deba@57
|
359 |
///\code
|
deba@57
|
360 |
/// int count=0;
|
deba@57
|
361 |
/// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
|
deba@57
|
362 |
///\endcode
|
deba@57
|
363 |
class ArcIt : public Arc {
|
deba@57
|
364 |
public:
|
deba@57
|
365 |
/// Default constructor
|
deba@57
|
366 |
|
deba@57
|
367 |
/// @warning The default constructor sets the iterator
|
deba@57
|
368 |
/// to an undefined value.
|
deba@57
|
369 |
ArcIt() { }
|
deba@57
|
370 |
/// Copy constructor.
|
deba@57
|
371 |
|
deba@57
|
372 |
/// Copy constructor.
|
deba@57
|
373 |
///
|
deba@57
|
374 |
ArcIt(const ArcIt& e) : Arc(e) { }
|
deba@57
|
375 |
/// Initialize the iterator to be invalid.
|
deba@57
|
376 |
|
deba@57
|
377 |
/// Initialize the iterator to be invalid.
|
deba@57
|
378 |
///
|
deba@57
|
379 |
ArcIt(Invalid) { }
|
deba@57
|
380 |
/// This constructor sets the iterator to the first arc.
|
alpar@209
|
381 |
|
deba@57
|
382 |
/// This constructor sets the iterator to the first arc of \c g.
|
deba@57
|
383 |
///@param g the graph
|
deba@57
|
384 |
ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
|
deba@57
|
385 |
/// Arc -> ArcIt conversion
|
deba@57
|
386 |
|
deba@57
|
387 |
/// Sets the iterator to the value of the trivial iterator \c e.
|
alpar@209
|
388 |
/// This feature necessitates that each time we
|
deba@57
|
389 |
/// iterate the arc-set, the iteration order is the same.
|
alpar@209
|
390 |
ArcIt(const Graph&, const Arc&) { }
|
deba@57
|
391 |
///Next arc
|
alpar@209
|
392 |
|
deba@57
|
393 |
/// Assign the iterator to the next arc.
|
deba@57
|
394 |
ArcIt& operator++() { return *this; }
|
deba@57
|
395 |
};
|
alpar@209
|
396 |
|
deba@57
|
397 |
/// This iterator goes trough the outgoing directed arcs of a node.
|
deba@57
|
398 |
|
deba@57
|
399 |
/// This iterator goes trough the \e outgoing arcs of a certain node
|
deba@57
|
400 |
/// of a graph.
|
deba@57
|
401 |
/// Its usage is quite simple, for example you can count the number
|
deba@57
|
402 |
/// of outgoing arcs of a node \c n
|
deba@57
|
403 |
/// in graph \c g of type \c Graph as follows.
|
deba@57
|
404 |
///\code
|
deba@57
|
405 |
/// int count=0;
|
deba@57
|
406 |
/// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
|
deba@57
|
407 |
///\endcode
|
alpar@209
|
408 |
|
deba@57
|
409 |
class OutArcIt : public Arc {
|
deba@57
|
410 |
public:
|
deba@57
|
411 |
/// Default constructor
|
deba@57
|
412 |
|
deba@57
|
413 |
/// @warning The default constructor sets the iterator
|
deba@57
|
414 |
/// to an undefined value.
|
deba@57
|
415 |
OutArcIt() { }
|
deba@57
|
416 |
/// Copy constructor.
|
deba@57
|
417 |
|
deba@57
|
418 |
/// Copy constructor.
|
deba@57
|
419 |
///
|
deba@57
|
420 |
OutArcIt(const OutArcIt& e) : Arc(e) { }
|
deba@57
|
421 |
/// Initialize the iterator to be invalid.
|
deba@57
|
422 |
|
deba@57
|
423 |
/// Initialize the iterator to be invalid.
|
deba@57
|
424 |
///
|
deba@57
|
425 |
OutArcIt(Invalid) { }
|
deba@57
|
426 |
/// This constructor sets the iterator to the first outgoing arc.
|
alpar@209
|
427 |
|
deba@57
|
428 |
/// This constructor sets the iterator to the first outgoing arc of
|
deba@57
|
429 |
/// the node.
|
deba@57
|
430 |
///@param n the node
|
deba@57
|
431 |
///@param g the graph
|
deba@57
|
432 |
OutArcIt(const Graph& n, const Node& g) {
|
alpar@209
|
433 |
ignore_unused_variable_warning(n);
|
alpar@209
|
434 |
ignore_unused_variable_warning(g);
|
alpar@209
|
435 |
}
|
deba@57
|
436 |
/// Arc -> OutArcIt conversion
|
deba@57
|
437 |
|
deba@57
|
438 |
/// Sets the iterator to the value of the trivial iterator.
|
alpar@209
|
439 |
/// This feature necessitates that each time we
|
deba@57
|
440 |
/// iterate the arc-set, the iteration order is the same.
|
deba@57
|
441 |
OutArcIt(const Graph&, const Arc&) { }
|
deba@57
|
442 |
///Next outgoing arc
|
alpar@209
|
443 |
|
alpar@209
|
444 |
/// Assign the iterator to the next
|
deba@57
|
445 |
/// outgoing arc of the corresponding node.
|
deba@57
|
446 |
OutArcIt& operator++() { return *this; }
|
deba@57
|
447 |
};
|
deba@57
|
448 |
|
deba@57
|
449 |
/// This iterator goes trough the incoming directed arcs of a node.
|
deba@57
|
450 |
|
deba@57
|
451 |
/// This iterator goes trough the \e incoming arcs of a certain node
|
deba@57
|
452 |
/// of a graph.
|
deba@57
|
453 |
/// Its usage is quite simple, for example you can count the number
|
deba@57
|
454 |
/// of outgoing arcs of a node \c n
|
deba@57
|
455 |
/// in graph \c g of type \c Graph as follows.
|
deba@57
|
456 |
///\code
|
deba@57
|
457 |
/// int count=0;
|
deba@57
|
458 |
/// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
|
deba@57
|
459 |
///\endcode
|
deba@57
|
460 |
|
deba@57
|
461 |
class InArcIt : public Arc {
|
deba@57
|
462 |
public:
|
deba@57
|
463 |
/// Default constructor
|
deba@57
|
464 |
|
deba@57
|
465 |
/// @warning The default constructor sets the iterator
|
deba@57
|
466 |
/// to an undefined value.
|
deba@57
|
467 |
InArcIt() { }
|
deba@57
|
468 |
/// Copy constructor.
|
deba@57
|
469 |
|
deba@57
|
470 |
/// Copy constructor.
|
deba@57
|
471 |
///
|
deba@57
|
472 |
InArcIt(const InArcIt& e) : Arc(e) { }
|
deba@57
|
473 |
/// Initialize the iterator to be invalid.
|
deba@57
|
474 |
|
deba@57
|
475 |
/// Initialize the iterator to be invalid.
|
deba@57
|
476 |
///
|
deba@57
|
477 |
InArcIt(Invalid) { }
|
deba@57
|
478 |
/// This constructor sets the iterator to first incoming arc.
|
alpar@209
|
479 |
|
deba@57
|
480 |
/// This constructor set the iterator to the first incoming arc of
|
deba@57
|
481 |
/// the node.
|
deba@57
|
482 |
///@param n the node
|
deba@57
|
483 |
///@param g the graph
|
alpar@209
|
484 |
InArcIt(const Graph& g, const Node& n) {
|
alpar@209
|
485 |
ignore_unused_variable_warning(n);
|
alpar@209
|
486 |
ignore_unused_variable_warning(g);
|
alpar@209
|
487 |
}
|
deba@57
|
488 |
/// Arc -> InArcIt conversion
|
deba@57
|
489 |
|
deba@57
|
490 |
/// Sets the iterator to the value of the trivial iterator \c e.
|
alpar@209
|
491 |
/// This feature necessitates that each time we
|
deba@57
|
492 |
/// iterate the arc-set, the iteration order is the same.
|
deba@57
|
493 |
InArcIt(const Graph&, const Arc&) { }
|
deba@57
|
494 |
/// Next incoming arc
|
deba@57
|
495 |
|
deba@57
|
496 |
/// Assign the iterator to the next inarc of the corresponding node.
|
deba@57
|
497 |
///
|
deba@57
|
498 |
InArcIt& operator++() { return *this; }
|
deba@57
|
499 |
};
|
deba@57
|
500 |
|
deba@57
|
501 |
/// \brief Read write map of the nodes to type \c T.
|
alpar@209
|
502 |
///
|
deba@57
|
503 |
/// ReadWrite map of the nodes to type \c T.
|
deba@57
|
504 |
/// \sa Reference
|
alpar@209
|
505 |
template<class T>
|
deba@57
|
506 |
class NodeMap : public ReadWriteMap< Node, T >
|
deba@57
|
507 |
{
|
deba@57
|
508 |
public:
|
deba@57
|
509 |
|
deba@57
|
510 |
///\e
|
deba@57
|
511 |
NodeMap(const Graph&) { }
|
deba@57
|
512 |
///\e
|
deba@57
|
513 |
NodeMap(const Graph&, T) { }
|
deba@57
|
514 |
|
deba@57
|
515 |
///Copy constructor
|
deba@57
|
516 |
NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
|
deba@57
|
517 |
///Assignment operator
|
deba@57
|
518 |
template <typename CMap>
|
alpar@209
|
519 |
NodeMap& operator=(const CMap&) {
|
deba@57
|
520 |
checkConcept<ReadMap<Node, T>, CMap>();
|
alpar@209
|
521 |
return *this;
|
deba@57
|
522 |
}
|
deba@57
|
523 |
};
|
deba@57
|
524 |
|
deba@57
|
525 |
/// \brief Read write map of the directed arcs to type \c T.
|
deba@57
|
526 |
///
|
deba@57
|
527 |
/// Reference map of the directed arcs to type \c T.
|
deba@57
|
528 |
/// \sa Reference
|
alpar@209
|
529 |
template<class T>
|
deba@57
|
530 |
class ArcMap : public ReadWriteMap<Arc,T>
|
deba@57
|
531 |
{
|
deba@57
|
532 |
public:
|
deba@57
|
533 |
|
deba@57
|
534 |
///\e
|
deba@57
|
535 |
ArcMap(const Graph&) { }
|
deba@57
|
536 |
///\e
|
deba@57
|
537 |
ArcMap(const Graph&, T) { }
|
deba@57
|
538 |
///Copy constructor
|
deba@57
|
539 |
ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
|
deba@57
|
540 |
///Assignment operator
|
deba@57
|
541 |
template <typename CMap>
|
alpar@209
|
542 |
ArcMap& operator=(const CMap&) {
|
deba@57
|
543 |
checkConcept<ReadMap<Arc, T>, CMap>();
|
alpar@209
|
544 |
return *this;
|
deba@57
|
545 |
}
|
deba@57
|
546 |
};
|
deba@57
|
547 |
|
deba@57
|
548 |
/// Read write map of the edges to type \c T.
|
deba@57
|
549 |
|
deba@57
|
550 |
/// Reference map of the arcs to type \c T.
|
deba@57
|
551 |
/// \sa Reference
|
alpar@209
|
552 |
template<class T>
|
deba@57
|
553 |
class EdgeMap : public ReadWriteMap<Edge,T>
|
deba@57
|
554 |
{
|
deba@57
|
555 |
public:
|
deba@57
|
556 |
|
deba@57
|
557 |
///\e
|
deba@57
|
558 |
EdgeMap(const Graph&) { }
|
deba@57
|
559 |
///\e
|
deba@57
|
560 |
EdgeMap(const Graph&, T) { }
|
deba@57
|
561 |
///Copy constructor
|
deba@57
|
562 |
EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
|
deba@57
|
563 |
///Assignment operator
|
deba@57
|
564 |
template <typename CMap>
|
alpar@209
|
565 |
EdgeMap& operator=(const CMap&) {
|
deba@57
|
566 |
checkConcept<ReadMap<Edge, T>, CMap>();
|
alpar@209
|
567 |
return *this;
|
deba@57
|
568 |
}
|
deba@57
|
569 |
};
|
deba@57
|
570 |
|
deba@57
|
571 |
/// \brief Direct the given edge.
|
deba@57
|
572 |
///
|
deba@57
|
573 |
/// Direct the given edge. The returned arc source
|
deba@57
|
574 |
/// will be the given node.
|
deba@57
|
575 |
Arc direct(const Edge&, const Node&) const {
|
alpar@209
|
576 |
return INVALID;
|
deba@57
|
577 |
}
|
deba@57
|
578 |
|
deba@57
|
579 |
/// \brief Direct the given edge.
|
deba@57
|
580 |
///
|
deba@57
|
581 |
/// Direct the given edge. The returned arc
|
deba@57
|
582 |
/// represents the given edge and the direction comes
|
deba@57
|
583 |
/// from the bool parameter. The source of the edge and
|
deba@57
|
584 |
/// the directed arc is the same when the given bool is true.
|
deba@57
|
585 |
Arc direct(const Edge&, bool) const {
|
alpar@209
|
586 |
return INVALID;
|
deba@57
|
587 |
}
|
deba@57
|
588 |
|
deba@57
|
589 |
/// \brief Returns true if the arc has default orientation.
|
deba@57
|
590 |
///
|
deba@57
|
591 |
/// Returns whether the given directed arc is same orientation as
|
deba@57
|
592 |
/// the corresponding edge's default orientation.
|
deba@57
|
593 |
bool direction(Arc) const { return true; }
|
deba@57
|
594 |
|
deba@57
|
595 |
/// \brief Returns the opposite directed arc.
|
deba@57
|
596 |
///
|
deba@57
|
597 |
/// Returns the opposite directed arc.
|
deba@57
|
598 |
Arc oppositeArc(Arc) const { return INVALID; }
|
deba@57
|
599 |
|
deba@57
|
600 |
/// \brief Opposite node on an arc
|
deba@57
|
601 |
///
|
deba@57
|
602 |
/// \return the opposite of the given Node on the given Edge
|
deba@57
|
603 |
Node oppositeNode(Node, Edge) const { return INVALID; }
|
deba@57
|
604 |
|
deba@57
|
605 |
/// \brief First node of the edge.
|
deba@57
|
606 |
///
|
deba@57
|
607 |
/// \return the first node of the given Edge.
|
deba@57
|
608 |
///
|
deba@57
|
609 |
/// Naturally edges don't have direction and thus
|
deba@57
|
610 |
/// don't have source and target node. But we use these two methods
|
deba@57
|
611 |
/// to query the two nodes of the arc. The direction of the arc
|
deba@57
|
612 |
/// which arises this way is called the inherent direction of the
|
deba@57
|
613 |
/// edge, and is used to define the "default" direction
|
deba@57
|
614 |
/// of the directed versions of the arcs.
|
deba@57
|
615 |
/// \sa direction
|
deba@57
|
616 |
Node u(Edge) const { return INVALID; }
|
deba@57
|
617 |
|
deba@57
|
618 |
/// \brief Second node of the edge.
|
deba@57
|
619 |
Node v(Edge) const { return INVALID; }
|
deba@57
|
620 |
|
deba@57
|
621 |
/// \brief Source node of the directed arc.
|
deba@57
|
622 |
Node source(Arc) const { return INVALID; }
|
deba@57
|
623 |
|
deba@57
|
624 |
/// \brief Target node of the directed arc.
|
deba@57
|
625 |
Node target(Arc) const { return INVALID; }
|
deba@57
|
626 |
|
deba@61
|
627 |
/// \brief Returns the id of the node.
|
alpar@209
|
628 |
int id(Node) const { return -1; }
|
deba@61
|
629 |
|
deba@61
|
630 |
/// \brief Returns the id of the edge.
|
alpar@209
|
631 |
int id(Edge) const { return -1; }
|
deba@61
|
632 |
|
deba@61
|
633 |
/// \brief Returns the id of the arc.
|
alpar@209
|
634 |
int id(Arc) const { return -1; }
|
deba@61
|
635 |
|
deba@61
|
636 |
/// \brief Returns the node with the given id.
|
deba@61
|
637 |
///
|
deba@61
|
638 |
/// \pre The argument should be a valid node id in the graph.
|
alpar@209
|
639 |
Node nodeFromId(int) const { return INVALID; }
|
deba@61
|
640 |
|
deba@61
|
641 |
/// \brief Returns the edge with the given id.
|
deba@61
|
642 |
///
|
deba@61
|
643 |
/// \pre The argument should be a valid edge id in the graph.
|
alpar@209
|
644 |
Edge edgeFromId(int) const { return INVALID; }
|
deba@61
|
645 |
|
deba@61
|
646 |
/// \brief Returns the arc with the given id.
|
deba@61
|
647 |
///
|
deba@61
|
648 |
/// \pre The argument should be a valid arc id in the graph.
|
alpar@209
|
649 |
Arc arcFromId(int) const { return INVALID; }
|
deba@61
|
650 |
|
deba@61
|
651 |
/// \brief Returns an upper bound on the node IDs.
|
alpar@209
|
652 |
int maxNodeId() const { return -1; }
|
deba@61
|
653 |
|
deba@61
|
654 |
/// \brief Returns an upper bound on the edge IDs.
|
alpar@209
|
655 |
int maxEdgeId() const { return -1; }
|
deba@61
|
656 |
|
deba@61
|
657 |
/// \brief Returns an upper bound on the arc IDs.
|
alpar@209
|
658 |
int maxArcId() const { return -1; }
|
deba@61
|
659 |
|
deba@57
|
660 |
void first(Node&) const {}
|
deba@57
|
661 |
void next(Node&) const {}
|
deba@57
|
662 |
|
deba@57
|
663 |
void first(Edge&) const {}
|
deba@57
|
664 |
void next(Edge&) const {}
|
deba@57
|
665 |
|
deba@57
|
666 |
void first(Arc&) const {}
|
deba@57
|
667 |
void next(Arc&) const {}
|
deba@57
|
668 |
|
deba@57
|
669 |
void firstOut(Arc&, Node) const {}
|
deba@57
|
670 |
void nextOut(Arc&) const {}
|
deba@57
|
671 |
|
deba@57
|
672 |
void firstIn(Arc&, Node) const {}
|
deba@57
|
673 |
void nextIn(Arc&) const {}
|
deba@57
|
674 |
|
deba@57
|
675 |
void firstInc(Edge &, bool &, const Node &) const {}
|
deba@57
|
676 |
void nextInc(Edge &, bool &) const {}
|
deba@57
|
677 |
|
deba@61
|
678 |
// The second parameter is dummy.
|
deba@61
|
679 |
Node fromId(int, Node) const { return INVALID; }
|
deba@61
|
680 |
// The second parameter is dummy.
|
deba@61
|
681 |
Edge fromId(int, Edge) const { return INVALID; }
|
deba@61
|
682 |
// The second parameter is dummy.
|
deba@61
|
683 |
Arc fromId(int, Arc) const { return INVALID; }
|
deba@61
|
684 |
|
deba@61
|
685 |
// Dummy parameter.
|
alpar@209
|
686 |
int maxId(Node) const { return -1; }
|
deba@61
|
687 |
// Dummy parameter.
|
alpar@209
|
688 |
int maxId(Edge) const { return -1; }
|
deba@61
|
689 |
// Dummy parameter.
|
alpar@209
|
690 |
int maxId(Arc) const { return -1; }
|
deba@61
|
691 |
|
deba@57
|
692 |
/// \brief Base node of the iterator
|
deba@57
|
693 |
///
|
deba@57
|
694 |
/// Returns the base node (the source in this case) of the iterator
|
deba@57
|
695 |
Node baseNode(OutArcIt e) const {
|
alpar@209
|
696 |
return source(e);
|
deba@57
|
697 |
}
|
deba@57
|
698 |
/// \brief Running node of the iterator
|
deba@57
|
699 |
///
|
deba@57
|
700 |
/// Returns the running node (the target in this case) of the
|
deba@57
|
701 |
/// iterator
|
deba@57
|
702 |
Node runningNode(OutArcIt e) const {
|
alpar@209
|
703 |
return target(e);
|
deba@57
|
704 |
}
|
deba@57
|
705 |
|
deba@57
|
706 |
/// \brief Base node of the iterator
|
deba@57
|
707 |
///
|
deba@57
|
708 |
/// Returns the base node (the target in this case) of the iterator
|
deba@57
|
709 |
Node baseNode(InArcIt e) const {
|
alpar@209
|
710 |
return target(e);
|
deba@57
|
711 |
}
|
deba@57
|
712 |
/// \brief Running node of the iterator
|
deba@57
|
713 |
///
|
deba@57
|
714 |
/// Returns the running node (the source in this case) of the
|
deba@57
|
715 |
/// iterator
|
deba@57
|
716 |
Node runningNode(InArcIt e) const {
|
alpar@209
|
717 |
return source(e);
|
deba@57
|
718 |
}
|
deba@57
|
719 |
|
deba@57
|
720 |
/// \brief Base node of the iterator
|
deba@57
|
721 |
///
|
deba@57
|
722 |
/// Returns the base node of the iterator
|
deba@78
|
723 |
Node baseNode(IncEdgeIt) const {
|
alpar@209
|
724 |
return INVALID;
|
deba@57
|
725 |
}
|
alpar@209
|
726 |
|
deba@57
|
727 |
/// \brief Running node of the iterator
|
deba@57
|
728 |
///
|
deba@57
|
729 |
/// Returns the running node of the iterator
|
deba@78
|
730 |
Node runningNode(IncEdgeIt) const {
|
alpar@209
|
731 |
return INVALID;
|
deba@57
|
732 |
}
|
deba@57
|
733 |
|
deba@125
|
734 |
template <typename _Graph>
|
deba@57
|
735 |
struct Constraints {
|
alpar@209
|
736 |
void constraints() {
|
alpar@209
|
737 |
checkConcept<IterableGraphComponent<>, _Graph>();
|
alpar@209
|
738 |
checkConcept<IDableGraphComponent<>, _Graph>();
|
alpar@209
|
739 |
checkConcept<MappableGraphComponent<>, _Graph>();
|
alpar@209
|
740 |
}
|
deba@57
|
741 |
};
|
deba@57
|
742 |
|
deba@57
|
743 |
};
|
deba@57
|
744 |
|
deba@57
|
745 |
}
|
deba@57
|
746 |
|
deba@57
|
747 |
}
|
deba@57
|
748 |
|
deba@57
|
749 |
#endif
|