- Changes in doc (spell check).
- SmallGraph is a class instead of being a typedef. (For the sake of doxygen.)
2 * src/lemon/skeletons/graph_component.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
19 ///\brief The graph components.
22 #ifndef LEMON_SKELETON_GRAPH_COMPONENT_H
23 #define LEMON_SKELETON_GRAPH_COMPONENT_H
25 #include <lemon/invalid.h>
26 #include <lemon/skeletons/maps.h>
31 /// An empty base graph class.
33 /// This class provides the most minimal features of a graph structure.
34 /// All the graph concepts have to be conform to this base graph.
36 class BaseGraphComponent {
39 typedef BaseGraphComponent Graph;
41 /// Node class of the graph.
43 /// This class represents the Nodes of the graph.
48 /// Default constructor.
50 /// @warning The default constructor sets the iterator
51 /// to an undefined value.
60 /// Invalid constructor \& conversion.
62 /// This constructor initializes the iterator to be invalid.
63 /// \sa Invalid for more details.
67 Node& operator=(const Node&) { return *this;}
69 /// Equality operator.
71 /// Two iterators are equal if and only if they represents the
72 /// same node in the graph or both are invalid.
73 bool operator==(const Node&) { return true;}
76 /// Inequality operator.
78 /// \sa operator==(const Node& n)
80 bool operator!=(const Node&) { return true;}
82 /// Comparison operator.
84 /// This is a strict ordering between the nodes.
86 /// This ordering can be different from the iterating order of nodes.
87 /// \todo Possibly we don't need it.
88 bool operator<(const Node&) { return true;}
91 /// Edge class of the graph.
93 /// This class represents the Edges of the graph.
98 /// Default constructor.
100 /// @warning The default constructor sets the iterator
101 /// to an undefined value.
104 /// Copy constructor.
106 /// Copy constructor.
110 /// Invalid constructor \& conversion.
112 /// This constructor initializes the iterator to be invalid.
113 /// \sa Invalid for more details.
117 Edge& operator=(const Edge&) { return *this;}
119 /// Equality operator.
121 /// Two iterators are equal if and only if they represents the
122 /// same edge in the graph or both are invalid.
123 bool operator==(const Edge&) { return true;}
126 /// Inequality operator.
128 /// \sa operator==(const Edge& n)
130 bool operator!=(const Edge&) { return true;}
132 /// Comparison operator.
134 /// This is a strict ordering between the edges.
136 /// This ordering can be different from the iterating order of edges.
137 /// \todo Possibly we don't need it.
138 bool operator<(const Edge&) { return true;}
141 ///Gives back the head node of an edge.
143 ///Gives back the head node of an edge.
145 Node head(const Edge&) const { return INVALID;}
147 ///Gives back the tail node of an edge.
149 ///Gives back the tail node of an edge.
151 Node tail(const Edge&) const { return INVALID;}
154 /// Concept check structure for BaseGraph.
156 /// Concept check structure for BaseGraph.
159 template <typename Graph>
160 struct BaseGraphComponentConcept {
161 typedef typename Graph::Node Node;
162 typedef typename Graph::Edge Edge;
171 b = (ni == INVALID); b = (ni != INVALID);
172 b = (ni==nj); b = (ni != nj); b=( ni < nj);
180 b = (ei == INVALID); b = (ei != INVALID);
181 b = (ei==ej); b = (ei != ej); b=( ei < ej);
184 const Graph& const_graph = graph;
187 n = const_graph.tail(e);
188 n = const_graph.head(e);
195 /// An empty iterable base graph class.
197 /// This class provides beside the core graph features
198 /// core iterable interface for the graph structure.
199 /// Most of the base graphs should be conform to this concept.
201 class BaseIterableGraphComponent : virtual public BaseGraphComponent {
204 typedef BaseGraphComponent::Node Node;
205 typedef BaseGraphComponent::Edge Edge;
207 /// Gives back the first Node in the iterating order.
209 /// Gives back the first Node in the iterating order.
211 void first(Node&) const {}
213 /// Gives back the next Node in the iterating order.
215 /// Gives back the next Node in the iterating order.
217 void next(Node&) const {}
219 /// Gives back the first Edge in the iterating order.
221 /// Gives back the first Edge in the iterating order.
223 void first(Edge&) const {}
224 /// Gives back the next Edge in the iterating order.
226 /// Gives back the next Edge in the iterating order.
228 void next(Edge&) const {}
231 /// Gives back the first of the Edges point to the given Node.
233 /// Gives back the first of the Edges point to the given Node.
235 void firstIn(Edge&, const Node&) const {}
237 /// Gives back the next of the Edges points to the given Node.
240 /// Gives back the next of the Edges points to the given Node.
242 void nextIn(Edge&) const {}
244 /// Gives back the first of the Edges start from the given Node.
246 /// Gives back the first of the Edges start from the given Node.
248 void firstOut(Edge&, const Node&) const {}
250 /// Gives back the next of the Edges start from the given Node.
252 /// Gives back the next of the Edges start from the given Node.
254 void nextOut(Edge&) const {}
258 /// Concept check structure for IterableBaseGraph.
260 /// Concept check structure for IterableBaseGraph.
262 template <typename Graph>
263 struct BaseIterableGraphComponentConcept {
266 const Graph& const_graph = graph;
267 typename Graph::Node node;
268 typename Graph::Edge edge;
270 const_graph.first(node);
271 const_graph.next(node);
274 const_graph.first(edge);
275 const_graph.next(edge);
278 const_graph.firstIn(edge, node);
279 const_graph.nextIn(edge);
282 const_graph.firstOut(edge, node);
283 const_graph.nextOut(edge);
290 /// An empty idable base graph class.
292 /// This class provides beside the core graph features
293 /// core id functions for the graph structure.
294 /// The most of the base graphs should be conform to this concept.
295 /// The id's are unique and immutable.
297 class IDableGraphComponent : virtual public BaseGraphComponent {
300 typedef BaseGraphComponent::Node Node;
301 typedef BaseGraphComponent::Edge Edge;
303 /// Gives back an unique integer id for the Node.
305 /// Gives back an unique integer id for the Node.
307 int id(const Node&) const { return -1;}
309 /// Gives back an unique integer id for the Edge.
311 /// Gives back an unique integer id for the Edge.
313 int id(const Edge&) const { return -1;}
317 /// Concept check structure for IdableBaseGraph.
319 /// Concept check structure for IdableBaseGraph.
321 template <typename Graph>
322 struct IDableGraphComponentConcept {
325 const Graph& const_graph = graph;
326 typename Graph::Node node;
327 int nid = const_graph.id(node);
328 nid = const_graph.id(node);
329 typename Graph::Edge edge;
330 int eid = const_graph.id(edge);
331 eid = const_graph.id(edge);
338 /// An empty max-idable base graph class.
340 /// This class provides beside the core graph features
341 /// core max id functions for the graph structure.
342 /// The most of the base graphs should be conform to this concept.
343 /// The id's are unique and immutable.
344 class MaxIDableGraphComponent : virtual public BaseGraphComponent {
347 /// Gives back an integer greater or equal to the maximum Node id.
349 /// Gives back an integer greater or equal to the maximum Node id.
351 int maxEdgeId() const { return -1;}
353 /// Gives back an integer greater or equal to the maximum Edge id.
355 /// Gives back an integer greater or equal to the maximum Edge id.
357 int maxNodeId() const { return -1;}
360 /// Concept check structure for MaxIdableBaseGraph.
362 /// Concept check structure for MaxIdableBaseGraph.
364 template <typename Graph>
365 struct MaxIDableGraphComponentConcept {
368 const Graph& const_graph = graph;
369 int nid = const_graph.maxEdgeId();
370 ignore_unused_variable_warning(nid);
371 int eid = const_graph.maxNodeId();
372 ignore_unused_variable_warning(eid);
378 /// An empty extendable base graph class.
380 /// This class provides beside the core graph features
381 /// core graph extend interface for the graph structure.
382 /// The most of the base graphs should be conform to this concept.
383 class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
386 typedef BaseGraphComponent::Node Node;
387 typedef BaseGraphComponent::Edge Edge;
389 /// Adds a new Node to the graph.
391 /// Adds a new Node to the graph.
397 /// Adds a new Edge connects the two Nodes to the graph.
399 /// Adds a new Edge connects the two Nodes to the graph.
401 Edge addEdge(const Node& from, const Node& to) {
407 /// Concept check structure for ExtendableBaseGraph.
409 /// Concept check structure for ExtendableBaseGraph.
411 template <typename Graph>
412 struct BaseExtendableGraphComponentConcept {
414 typename Graph::Node node_a, node_b;
415 node_a = graph.addNode();
416 typename Graph::Edge edge;
417 edge = graph.addEdge(node_a, node_b);
423 /// An empty erasable base graph class.
425 /// This class provides beside the core graph features
426 /// core erase functions for the graph structure.
427 /// The most of the base graphs should be conform to this concept.
428 class BaseErasableGraphComponent : virtual public BaseGraphComponent {
431 typedef BaseGraphComponent::Node Node;
432 typedef BaseGraphComponent::Edge Edge;
434 /// Erase a Node from the graph.
436 /// Erase a Node from the graph. This function should not
437 /// erase edges connecting to the Node.
438 void erase(const Node&) {}
440 /// Erase an Edge from the graph.
442 /// Erase an Edge from the graph.
444 void erase(const Edge&) {}
448 /// Concept check structure for ErasableBaseGraph.
450 /// Concept check structure for ErasableBaseGraph.
452 template <typename Graph>
453 struct BaseErasableGraphComponentConcept {
455 typename Graph::Node node;
457 typename Graph::Edge edge;
464 /// An empty clearable base graph class.
466 /// This class provides beside the core graph features
467 /// core clear functions for the graph structure.
468 /// The most of the base graphs should be conform to this concept.
469 class BaseClearableGraphComponent : virtual public BaseGraphComponent {
472 /// Erase all the Nodes and Edges from the graph.
474 /// Erase all the Nodes and Edges from the graph.
479 /// Concept check function for ErasableBaseGraph.
481 /// Concept check function for ErasableBaseGraph.
483 template <typename Graph>
484 struct BaseClearableGraphComponentConcept {
493 class IterableGraphComponent : virtual public BaseGraphComponent {
497 typedef IterableGraphComponent Graph;
499 typedef BaseGraphComponent::Node Node;
500 typedef BaseGraphComponent::Edge Edge;
502 class NodeIt : public Node {
506 NodeIt(const Graph&) {}
508 NodeIt& operator++() { return *this; }
509 // Node operator*() const { return INVALID; }
511 bool operator==(const NodeIt&) { return true;}
512 bool operator!=(const NodeIt&) { return true;}
515 class EdgeIt : public Edge {
519 EdgeIt(const Graph&) {}
521 EdgeIt& operator++() { return *this; }
522 // Edge operator*() const { return INVALID; }
524 bool operator==(const EdgeIt&) { return true;}
525 bool operator!=(const EdgeIt&) { return true;}
528 class InEdgeIt : public Edge {
532 InEdgeIt(const Graph&, const Node&) {}
534 InEdgeIt& operator++() { return *this; }
535 // Edge operator*() const { return INVALID; }
537 bool operator==(const InEdgeIt&) { return true;}
538 bool operator!=(const InEdgeIt&) { return true;}
541 class OutEdgeIt : public Edge {
544 OutEdgeIt(Invalid) {}
545 OutEdgeIt(const Graph&, const Node&) {}
547 OutEdgeIt& operator++() { return *this; }
548 // Edge operator*() const { return INVALID; }
550 bool operator==(const OutEdgeIt&) { return true;}
551 bool operator!=(const OutEdgeIt&) { return true;}
556 template <typename Graph>
557 struct IterableGraphComponentConcept {
561 typedef typename Graph::Node Node;
562 typedef typename Graph::NodeIt NodeIt;
563 typedef typename Graph::Edge Edge;
564 typedef typename Graph::EdgeIt EdgeIt;
565 typedef typename Graph::InEdgeIt InEdgeIt;
566 typedef typename Graph::OutEdgeIt OutEdgeIt;
601 InEdgeIt kt(INVALID);
603 InEdgeIt lt(graph, node);
617 OutEdgeIt kt(INVALID);
619 OutEdgeIt lt(graph, node);
635 class IdMappableGraphComponent : virtual public BaseGraphComponent {
637 typedef IdMappableGraphComponent Graph;
639 typedef BaseGraphComponent::Node Node;
640 typedef BaseGraphComponent::Edge Edge;
644 class NodeIdMap : public ReadMap<Node, int> {
646 NodeIdMap(const Graph&) {}
647 int maxId() const { return -1;}
650 class EdgeIdMap : public ReadMap<Edge, int> {
652 EdgeIdMap(const Graph&) {}
653 int maxId() const { return -1;}
658 template <typename Graph>
659 struct IdMappableGraphComponentConcept {
662 typedef typename Graph::EdgeIdMap EdgeIdMap;
663 function_requires<ReadMapConcept<EdgeIdMap> >();
664 EdgeIdMap edge_map(graph);
665 int n = edge_map.maxId();
666 ignore_unused_variable_warning(n);
669 typedef typename Graph::NodeIdMap NodeIdMap;
670 function_requires<ReadMapConcept<NodeIdMap> >();
671 NodeIdMap node_map(graph);
672 int n = node_map.maxId();
673 ignore_unused_variable_warning(n);
680 class MappableGraphComponent : virtual public BaseGraphComponent {
683 typedef MappableGraphComponent Graph;
685 typedef BaseGraphComponent::Node Node;
686 typedef BaseGraphComponent::Edge Edge;
688 template <typename Value>
689 class NodeMap : public ReferenceMap<Node, Value> {
691 NodeMap(const Graph&) {}
692 NodeMap(const Graph&, const Value&) {}
693 NodeMap(const NodeMap&) {}
695 NodeMap& operator=(const NodeMap&) { return *this;}
699 template <typename Value>
700 class EdgeMap : public ReferenceMap<Edge, Value> {
702 EdgeMap(const Graph&) {}
703 EdgeMap(const Graph&, const Value&) {}
704 EdgeMap(const EdgeMap&) {}
706 EdgeMap& operator=(const EdgeMap&) { return *this;}
712 template <typename Graph>
713 struct MappableGraphComponentConcept {
718 Type(int _v) : value(_v) {}
723 typedef typename Graph::template NodeMap<int> IntNodeMap;
724 function_requires<GraphMapConcept<IntNodeMap,Graph> >();
726 typedef typename Graph::template NodeMap<bool> BoolNodeMap;
727 function_requires<GraphMapConcept<BoolNodeMap,Graph> >();
729 typedef typename Graph::template NodeMap<Type> TypeNodeMap;
730 function_requires<GraphMapConcept<TypeNodeMap,Graph> >();
734 typedef typename Graph::template EdgeMap<int> IntEdgeMap;
735 function_requires<GraphMapConcept<IntEdgeMap,Graph> >();
737 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;
738 function_requires<GraphMapConcept<BoolEdgeMap,Graph> >();
740 typedef typename Graph::template EdgeMap<Type> TypeEdgeMap;
741 function_requires<GraphMapConcept<TypeEdgeMap,Graph> >();
749 class ExtendableGraphComponent : virtual public BaseGraphComponent {
752 typedef ExtendableGraphComponent Graph;
754 typedef BaseGraphComponent::Node Node;
755 typedef BaseGraphComponent::Edge Edge;
761 Edge addEdge(const Node& from, const Node& to) {
767 template <typename Graph>
768 struct ExtendableGraphComponentConcept {
770 typename Graph::Node node_a, node_b;
771 node_a = graph.addNode();
772 typename Graph::Edge edge;
773 edge = graph.addEdge(node_a, node_b);
778 class ErasableGraphComponent : virtual public BaseGraphComponent {
781 typedef ErasableGraphComponent Graph;
783 typedef BaseGraphComponent::Node Node;
784 typedef BaseGraphComponent::Edge Edge;
786 void erase(const Node&) {}
787 void erase(const Edge&) {}
791 template <typename Graph>
792 struct ErasableGraphComponentConcept {
794 typename Graph::Node node;
796 typename Graph::Edge edge;
803 class ClearableGraphComponent : virtual public BaseGraphComponent {
806 typedef ClearableGraphComponent Graph;
808 typedef BaseGraphComponent::Node Node;
809 typedef BaseGraphComponent::Edge Edge;
815 template <typename Graph>
816 struct ClearableGraphComponentConcept {