Added copyright header and description.
3 * lemon/concept/undir_graph_component.h - Part of LEMON, a generic
4 * C++ optimization library
6 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
7 * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
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.
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
20 ///\ingroup graph_concepts
22 ///\brief Undirected graphs and components of.
25 #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
26 #define LEMON_CONCEPT_UNDIR_GRAPH_H
28 #include <lemon/concept/graph_component.h>
29 #include <lemon/concept/graph.h>
30 #include <lemon/utility.h>
35 /// Skeleton class which describes an edge with direction in \ref
36 /// UndirGraph "undirected graph".
37 template <typename UndirGraph>
38 class UndirGraphEdge : public UndirGraph::UndirEdge {
39 typedef typename UndirGraph::UndirEdge UndirEdge;
40 typedef typename UndirGraph::Node Node;
47 UndirGraphEdge(const UndirGraphEdge& e) : UndirGraph::UndirEdge(e) {}
50 UndirGraphEdge(Invalid) {}
52 /// \brief Directed edge from undirected edge and a source node.
54 /// Constructs a directed edge from undirected edge and a source node.
56 /// \note You have to specify the graph for this constructor.
57 UndirGraphEdge(const UndirGraph &g,
58 UndirEdge undir_edge, Node n) {
59 ignore_unused_variable_warning(undir_edge);
60 ignore_unused_variable_warning(g);
61 ignore_unused_variable_warning(n);
65 UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
68 bool operator==(UndirGraphEdge) const { return true; }
70 bool operator!=(UndirGraphEdge) const { return false; }
73 bool operator<(UndirGraphEdge) const { return false; }
75 template <typename Edge>
80 void const_constraints() const {
81 /// \bug This should be is_base_and_derived ...
85 Edge e_with_source(graph,ue,n);
86 ignore_unused_variable_warning(e_with_source);
96 struct BaseIterableUndirGraphConcept {
98 template <typename Graph>
101 typedef typename Graph::UndirEdge UndirEdge;
102 typedef typename Graph::Edge Edge;
103 typedef typename Graph::Node Node;
106 checkConcept<BaseIterableGraphComponent, Graph>();
107 checkConcept<GraphItem<>, UndirEdge>();
108 //checkConcept<UndirGraphEdge<Graph>, Edge>();
115 void const_constraints() {
117 n = graph.target(ue);
118 n = graph.source(ue);
119 n = graph.oppositeNode(n0, ue);
122 b = graph.forward(e);
123 ignore_unused_variable_warning(b);
135 struct IterableUndirGraphConcept {
137 template <typename Graph>
140 /// \todo we don't need the iterable component to be base iterable
141 /// Don't we really???
142 //checkConcept< BaseIterableUndirGraphConcept, Graph > ();
144 checkConcept<IterableGraphComponent, Graph> ();
146 typedef typename Graph::UndirEdge UndirEdge;
147 typedef typename Graph::UndirEdgeIt UndirEdgeIt;
148 typedef typename Graph::IncEdgeIt IncEdgeIt;
150 checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
151 checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
157 struct MappableUndirGraphConcept {
159 template <typename Graph>
164 Dummy() : value(0) {}
165 Dummy(int _v) : value(_v) {}
169 checkConcept<MappableGraphComponent, Graph>();
171 typedef typename Graph::template UndirEdgeMap<int> IntMap;
172 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,
175 typedef typename Graph::template UndirEdgeMap<bool> BoolMap;
176 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,
179 typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;
180 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,
187 struct ExtendableUndirGraphConcept {
189 template <typename Graph>
192 node_a = graph.addNode();
193 uedge = graph.addEdge(node_a, node_b);
195 typename Graph::Node node_a, node_b;
196 typename Graph::UndirEdge uedge;
202 struct ErasableUndirGraphConcept {
204 template <typename Graph>
211 typename Graph::Node n;
212 typename Graph::UndirEdge e;
217 /// \addtogroup graph_concepts
221 /// Class describing the concept of Undirected Graphs.
223 /// This class describes the common interface of all Undirected
226 /// As all concept describing classes it provides only interface
227 /// without any sensible implementation. So any algorithm for
228 /// undirected graph should compile with this class, but it will not
229 /// run properly, of couse.
231 /// In LEMON undirected graphs also fulfill the concept of directed
232 /// graphs (\ref lemon::concept::Graph "Graph Concept"). For
233 /// explanation of this and more see also the page \ref undir_graphs,
234 /// a tutorial about undirected graphs.
236 class UndirGraph : public StaticGraph {
240 ///\todo undocumented
242 typedef True UndirTag;
244 /// The base type of the undirected edge iterators.
246 /// The base type of the undirected edge iterators.
250 /// Default constructor
252 /// @warning The default constructor sets the iterator
253 /// to an undefined value.
255 /// Copy constructor.
257 /// Copy constructor.
259 UndirEdge(const UndirEdge&) { }
260 /// Edge -> UndirEdge conversion
262 /// Edge -> UndirEdge conversion
264 UndirEdge(const Edge&) { }
265 /// Initialize the iterator to be invalid.
267 /// Initialize the iterator to be invalid.
269 UndirEdge(Invalid) { }
270 /// Equality operator
272 /// Two iterators are equal if and only if they point to the
273 /// same object or both are invalid.
274 bool operator==(UndirEdge) const { return true; }
275 /// Inequality operator
277 /// \sa operator==(UndirEdge n)
279 bool operator!=(UndirEdge) const { return true; }
283 ///\todo Do we need this?
285 bool operator<(const UndirEdge &that) const { return true; }
288 /// This iterator goes through each undirected edge.
290 /// This iterator goes through each undirected edge of a graph.
291 /// Its usage is quite simple, for example you can count the number
292 /// of edges in a graph \c g of type \c Graph as follows:
295 /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count;
297 class UndirEdgeIt : public UndirEdge {
299 /// Default constructor
301 /// @warning The default constructor sets the iterator
302 /// to an undefined value.
304 /// Copy constructor.
306 /// Copy constructor.
308 UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }
309 /// Initialize the iterator to be invalid.
311 /// Initialize the iterator to be invalid.
313 UndirEdgeIt(Invalid) { }
314 /// This constructor sets the iterator to the first edge.
316 /// This constructor sets the iterator to the first edge of \c g.
317 UndirEdgeIt(const UndirGraph&) { }
318 /// UndirEdge -> UndirEdgeIt conversion
320 /// Sets the iterator to the value of the trivial iterator \c e.
321 /// This feature necessitates that each time we
322 /// iterate the edge-set, the iteration order is the same.
323 UndirEdgeIt(const UndirGraph&, const UndirEdge&) { }
326 /// Assign the iterator to the next edge.
327 UndirEdgeIt& operator++() { return *this; }
330 /// This iterator goes trough the incident undirected edges of a node.
332 /// This iterator goes trough the incident undirected edges
333 /// of a certain node
335 /// Its usage is quite simple, for example you can compute the
336 /// degree (i.e. count the number
337 /// of incident edges of a node \c n
338 /// in graph \c g of type \c Graph as follows.
341 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
343 class IncEdgeIt : public UndirEdge {
345 /// Default constructor
347 /// @warning The default constructor sets the iterator
348 /// to an undefined value.
350 /// Copy constructor.
352 /// Copy constructor.
354 IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { }
355 /// Initialize the iterator to be invalid.
357 /// Initialize the iterator to be invalid.
359 IncEdgeIt(Invalid) { }
360 /// This constructor sets the iterator to first incident edge.
362 /// This constructor set the iterator to the first incident edge of
364 IncEdgeIt(const UndirGraph&, const Node&) { }
365 /// UndirEdge -> IncEdgeIt conversion
367 /// Sets the iterator to the value of the trivial iterator \c e.
368 /// This feature necessitates that each time we
369 /// iterate the edge-set, the iteration order is the same.
370 IncEdgeIt(const UndirGraph&, const UndirEdge&) { }
371 /// Next incident edge
373 /// Assign the iterator to the next incident edge
374 /// of the corresponding node.
375 IncEdgeIt& operator++() { return *this; }
378 /// Read write map of the undirected edges to type \c T.
380 /// Reference map of the edges to type \c T.
382 /// \warning Making maps that can handle bool type (UndirEdgeMap<bool>)
383 /// needs some extra attention!
385 class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>
390 UndirEdgeMap(const UndirGraph&) { }
392 UndirEdgeMap(const UndirGraph&, T) { }
394 UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) { }
395 ///Assignment operator
396 UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
397 // \todo fix this concept
400 /// Is the Edge oriented "forward"?
402 /// Returns whether the given directed edge is same orientation as
403 /// the corresponding undirected edge.
405 /// \todo "What does the direction of an undirected edge mean?"
406 bool forward(Edge) const { return true; }
408 /// Opposite node on an edge
410 /// \return the opposite of the given Node on the given Edge
412 /// \todo What should we do if given Node and Edge are not incident?
413 Node oppositeNode(Node, UndirEdge) const { return INVALID; }
415 /// First node of the undirected edge.
417 /// \return the first node of the given UndirEdge.
419 /// Naturally undirectected edges don't have direction and thus
420 /// don't have source and target node. But we use these two methods
421 /// to query the two endnodes of the edge. The direction of the edge
422 /// which arises this way is called the inherent direction of the
423 /// undirected edge, and is used to define the "forward" direction
424 /// of the directed versions of the edges.
426 Node source(UndirEdge) const { return INVALID; }
428 /// Second node of the undirected edge.
429 Node target(UndirEdge) const { return INVALID; }
431 /// Source node of the directed edge.
432 Node source(Edge) const { return INVALID; }
434 /// Target node of the directed edge.
435 Node target(Edge) const { return INVALID; }
437 /// First node of the graph
439 /// \note This method is part of so called \ref
440 /// developpers_interface "Developpers' interface", so it shouldn't
441 /// be used in an end-user program.
442 void first(Node&) const {}
443 /// Next node of the graph
445 /// \note This method is part of so called \ref
446 /// developpers_interface "Developpers' interface", so it shouldn't
447 /// be used in an end-user program.
448 void next(Node&) const {}
450 /// First undirected edge of the graph
452 /// \note This method is part of so called \ref
453 /// developpers_interface "Developpers' interface", so it shouldn't
454 /// be used in an end-user program.
455 void first(UndirEdge&) const {}
456 /// Next undirected edge of the graph
458 /// \note This method is part of so called \ref
459 /// developpers_interface "Developpers' interface", so it shouldn't
460 /// be used in an end-user program.
461 void next(UndirEdge&) const {}
463 /// First directed edge of the graph
465 /// \note This method is part of so called \ref
466 /// developpers_interface "Developpers' interface", so it shouldn't
467 /// be used in an end-user program.
468 void first(Edge&) const {}
469 /// Next directed edge of the graph
471 /// \note This method is part of so called \ref
472 /// developpers_interface "Developpers' interface", so it shouldn't
473 /// be used in an end-user program.
474 void next(Edge&) const {}
476 /// First outgoing edge from a given node
478 /// \note This method is part of so called \ref
479 /// developpers_interface "Developpers' interface", so it shouldn't
480 /// be used in an end-user program.
481 void firstOut(Edge&, Node) const {}
482 /// Next outgoing edge to a node
484 /// \note This method is part of so called \ref
485 /// developpers_interface "Developpers' interface", so it shouldn't
486 /// be used in an end-user program.
487 void nextOut(Edge&) const {}
489 /// First incoming edge to a given node
491 /// \note This method is part of so called \ref
492 /// developpers_interface "Developpers' interface", so it shouldn't
493 /// be used in an end-user program.
494 void firstIn(Edge&, Node) const {}
495 /// Next incoming edge to a node
497 /// \note This method is part of so called \ref
498 /// developpers_interface "Developpers' interface", so it shouldn't
499 /// be used in an end-user program.
500 void nextIn(Edge&) const {}
503 /// Base node of the iterator
505 /// Returns the base node (the source in this case) of the iterator
506 Node baseNode(OutEdgeIt e) const {
509 /// Running node of the iterator
511 /// Returns the running node (the target in this case) of the
513 Node runningNode(OutEdgeIt e) const {
517 /// Base node of the iterator
519 /// Returns the base node (the target in this case) of the iterator
520 Node baseNode(InEdgeIt e) const {
523 /// Running node of the iterator
525 /// Returns the running node (the source in this case) of the
527 Node runningNode(InEdgeIt e) const {
531 /// Base node of the iterator
533 /// Returns the base node of the iterator
534 Node baseNode(IncEdgeIt) const {
537 /// Running node of the iterator
539 /// Returns the running node of the iterator
540 Node runningNode(IncEdgeIt) const {
545 template <typename Graph>
548 checkConcept<BaseIterableUndirGraphConcept, Graph>();
549 checkConcept<IterableUndirGraphConcept, Graph>();
550 checkConcept<MappableUndirGraphConcept, Graph>();
556 class ExtendableUndirGraph : public UndirGraph {
559 template <typename Graph>
562 checkConcept<BaseIterableUndirGraphConcept, Graph>();
563 checkConcept<IterableUndirGraphConcept, Graph>();
564 checkConcept<MappableUndirGraphConcept, Graph>();
566 checkConcept<UndirGraph, Graph>();
567 checkConcept<ExtendableUndirGraphConcept, Graph>();
568 checkConcept<ClearableGraphComponent, Graph>();
574 class ErasableUndirGraph : public ExtendableUndirGraph {
577 template <typename Graph>
580 checkConcept<ExtendableUndirGraph, Graph>();
581 checkConcept<ErasableUndirGraphConcept, Graph>();