* Somewhat less redundant and a bit more correct graph concepts.
* graph_wrapper_test does not compile
2 * src/lemon/concept/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_CONCEPT_GRAPH_COMPONENT_H
23 #define LEMON_CONCEPT_GRAPH_COMPONENT_H
25 #include <lemon/invalid.h>
26 #include <lemon/concept/maps.h>
32 /**************** Graph iterator concepts ****************/
34 /// Skeleton class for graph Node and Edge
36 /// \note Because Node and Edge are forbidden to inherit from the same
37 /// base class, this is a template. For Node you shoul instantiate it
38 /// with character 'n' and for Edge with 'e'.
46 // We explicitely list these:
47 GraphItem(GraphItem const&) {}
48 GraphItem& operator=(GraphItem const&) { return *this; }
50 bool operator==(GraphItem) const { return false; }
51 bool operator!=(GraphItem) const { return false; }
53 // Technical requirement. Do we really need this?
54 bool operator<(GraphItem) const { return false; }
59 struct GraphItemConcept {
68 b = (ia == ib) && (ia != ib) && (ia < ib);
69 b = (ia == INVALID) && (ib != INVALID);
77 template<typename Iter, typename Graph, typename BaseItem>
78 struct GraphIteratorConcept {
80 function_requires< GraphItemConcept<Iter> >();
83 /// \todo Do we need NodeIt(Node) kind of constructor?
90 /// \bug This should be: is_base_and_derived<BaseItem, Iter>
99 template<typename Iter, typename Graph>
100 struct GraphIncIteratorConcept {
101 typedef typename Graph::Node Node;
102 typedef typename Graph::Edge Edge;
104 function_requires< GraphItemConcept<Iter> >();
105 Iter it1(graph, node);
106 /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
124 /// An empty base graph class.
126 /// This class provides the minimal set of features needed for a graph
127 /// structure. All graph concepts have to be conform to this base
130 /// \bug This is not true. The minimal graph concept is the
131 /// BaseIterableGraphComponent.
133 class BaseGraphComponent {
136 typedef BaseGraphComponent Graph;
138 /// Node class of the graph.
140 /// This class represents the Nodes of the graph.
145 /// Default constructor.
147 /// @warning The default constructor sets the iterator
148 /// to an undefined value.
151 /// Copy constructor.
153 /// Copy constructor.
157 /// Invalid constructor \& conversion.
159 /// This constructor initializes the iterator to be invalid.
160 /// \sa Invalid for more details.
164 Node& operator=(const Node&) { return *this;}
166 /// Equality operator.
168 /// Two iterators are equal if and only if they represents the
169 /// same node in the graph or both are invalid.
170 bool operator==(const Node&) const { return true;}
173 /// Inequality operator.
175 /// \sa operator==(const Node& n)
177 bool operator!=(const Node&) const { return true;}
179 /// Comparison operator.
181 /// This is a strict ordering between the nodes.
183 /// This ordering can be different from the iterating order of nodes.
184 /// \todo Possibly we don't need it.
185 bool operator<(const Node&) const { return true;}
188 /// Edge class of the graph.
190 /// This class represents the Edges of the graph.
195 /// Default constructor.
197 /// @warning The default constructor sets the iterator
198 /// to an undefined value.
201 /// Copy constructor.
203 /// Copy constructor.
207 /// Invalid constructor \& conversion.
209 /// This constructor initializes the iterator to be invalid.
210 /// \sa Invalid for more details.
214 Edge& operator=(const Edge&) { return *this;}
216 /// Equality operator.
218 /// Two iterators are equal if and only if they represents the
219 /// same edge in the graph or both are invalid.
220 bool operator==(const Edge&) const { return true;}
223 /// Inequality operator.
225 /// \sa operator==(const Edge& n)
227 bool operator!=(const Edge&) const { return true;}
229 /// Comparison operator.
231 /// This is a strict ordering between the edges.
233 /// This ordering can be different from the iterating order of edges.
234 /// \todo Possibly we don't need it.
235 bool operator<(const Edge&) const { return true;}
238 ///Gives back the head node of an edge.
240 ///Gives back the head node of an edge.
242 Node head(const Edge&) const { return INVALID;}
244 ///Gives back the tail node of an edge.
246 ///Gives back the tail node of an edge.
248 Node tail(const Edge&) const { return INVALID;}
252 /// Concept check structure for BaseGraph.
254 /// Concept check structure for BaseGraph.
257 template <typename Graph>
258 struct BaseGraphComponentConcept {
259 typedef typename Graph::Node Node;
260 typedef typename Graph::Edge Edge;
263 function_requires< GraphItemConcept<Node> >();
264 function_requires< GraphItemConcept<Edge> >();
266 const Graph& const_graph = graph;
269 n = const_graph.tail(e);
270 n = const_graph.head(e);
277 /// An empty iterable base graph class.
279 /// This class provides beside the core graph features
280 /// core iterable interface for the graph structure.
281 /// Most of the base graphs should be conform to this concept.
283 class BaseIterableGraphComponent : virtual public BaseGraphComponent {
286 typedef BaseGraphComponent::Node Node;
287 typedef BaseGraphComponent::Edge Edge;
289 /// Gives back the first Node in the iterating order.
291 /// Gives back the first Node in the iterating order.
293 void first(Node&) const {}
295 /// Gives back the next Node in the iterating order.
297 /// Gives back the next Node in the iterating order.
299 void next(Node&) const {}
301 /// Gives back the first Edge in the iterating order.
303 /// Gives back the first Edge in the iterating order.
305 void first(Edge&) const {}
306 /// Gives back the next Edge in the iterating order.
308 /// Gives back the next Edge in the iterating order.
310 void next(Edge&) const {}
313 /// Gives back the first of the Edges point to the given Node.
315 /// Gives back the first of the Edges point to the given Node.
317 void firstIn(Edge&, const Node&) const {}
319 /// Gives back the next of the Edges points to the given Node.
322 /// Gives back the next of the Edges points to the given Node.
324 void nextIn(Edge&) const {}
326 /// Gives back the first of the Edges start from the given Node.
328 /// Gives back the first of the Edges start from the given Node.
330 void firstOut(Edge&, const Node&) const {}
332 /// Gives back the next of the Edges start from the given Node.
334 /// Gives back the next of the Edges start from the given Node.
336 void nextOut(Edge&) const {}
340 /// Concept check structure for IterableBaseGraph.
342 /// Concept check structure for IterableBaseGraph.
344 template <typename Graph>
345 struct BaseIterableGraphComponentConcept {
348 function_requires< BaseGraphComponentConcept<Graph> >();
349 typename Graph::Node node;
350 typename Graph::Edge edge;
360 graph.firstIn(edge, node);
364 graph.firstOut(edge, node);
372 /// An empty idable base graph class.
374 /// This class provides beside the core graph features
375 /// core id functions for the graph structure.
376 /// The most of the base graphs should be conform to this concept.
377 /// The id's are unique and immutable.
379 class IDableGraphComponent : virtual public BaseGraphComponent {
382 typedef BaseGraphComponent::Node Node;
383 typedef BaseGraphComponent::Edge Edge;
385 /// Gives back an unique integer id for the Node.
387 /// Gives back an unique integer id for the Node.
389 int id(const Node&) const { return -1;}
391 /// Gives back an unique integer id for the Edge.
393 /// Gives back an unique integer id for the Edge.
395 int id(const Edge&) const { return -1;}
399 /// Concept check structure for IdableBaseGraph.
401 /// Concept check structure for IdableBaseGraph.
403 template <typename Graph>
404 struct IDableGraphComponentConcept {
407 function_requires< BaseGraphComponentConcept<Graph> >();
408 typename Graph::Node node;
409 int nid = graph.id(node);
410 nid = graph.id(node);
411 typename Graph::Edge edge;
412 int eid = graph.id(edge);
413 eid = graph.id(edge);
420 /// An empty max-idable base graph class.
422 /// This class provides beside the core graph features
423 /// core max id functions for the graph structure.
424 /// The most of the base graphs should be conform to this concept.
425 /// The id's are unique and immutable.
426 class MaxIDableGraphComponent : virtual public BaseGraphComponent {
429 /// Gives back an integer greater or equal to the maximum Node id.
431 /// Gives back an integer greater or equal to the maximum Node id.
433 int maxEdgeId() const { return -1;}
435 /// Gives back an integer greater or equal to the maximum Edge id.
437 /// Gives back an integer greater or equal to the maximum Edge id.
439 int maxNodeId() const { return -1;}
442 /// Concept check structure for MaxIdableBaseGraph.
444 /// Concept check structure for MaxIdableBaseGraph.
446 template <typename Graph>
447 struct MaxIDableGraphComponentConcept {
450 function_requires< BaseGraphComponentConcept<Graph> >();
451 int nid = graph.maxEdgeId();
452 ignore_unused_variable_warning(nid);
453 int eid = graph.maxNodeId();
454 ignore_unused_variable_warning(eid);
460 /// An empty extendable base graph class.
462 /// This class provides beside the core graph features
463 /// core graph extend interface for the graph structure.
464 /// The most of the base graphs should be conform to this concept.
465 class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
468 typedef BaseGraphComponent::Node Node;
469 typedef BaseGraphComponent::Edge Edge;
471 /// Adds a new Node to the graph.
473 /// Adds a new Node to the graph.
479 /// Adds a new Edge connects the two Nodes to the graph.
481 /// Adds a new Edge connects the two Nodes to the graph.
483 Edge addEdge(const Node& from, const Node& to) {
489 /// Concept check structure for ExtendableBaseGraph.
491 /// Concept check structure for ExtendableBaseGraph.
493 template <typename Graph>
494 struct BaseExtendableGraphComponentConcept {
496 function_requires< BaseGraphComponentConcept<Graph> >();
497 typename Graph::Node node_a, node_b;
498 node_a = graph.addNode();
499 typename Graph::Edge edge;
500 edge = graph.addEdge(node_a, node_b);
506 /// An empty erasable base graph class.
508 /// This class provides beside the core graph features
509 /// core erase functions for the graph structure.
510 /// The most of the base graphs should be conform to this concept.
511 class BaseErasableGraphComponent : virtual public BaseGraphComponent {
514 typedef BaseGraphComponent::Node Node;
515 typedef BaseGraphComponent::Edge Edge;
517 /// Erase a Node from the graph.
519 /// Erase a Node from the graph. This function should not
520 /// erase edges connecting to the Node.
521 void erase(const Node&) {}
523 /// Erase an Edge from the graph.
525 /// Erase an Edge from the graph.
527 void erase(const Edge&) {}
531 /// Concept check structure for ErasableBaseGraph.
533 /// Concept check structure for ErasableBaseGraph.
535 template <typename Graph>
536 struct BaseErasableGraphComponentConcept {
538 function_requires< BaseGraphComponentConcept<Graph> >();
539 typename Graph::Node node;
541 typename Graph::Edge edge;
548 /// An empty clearable base graph class.
550 /// This class provides beside the core graph features
551 /// core clear functions for the graph structure.
552 /// The most of the base graphs should be conform to this concept.
553 class BaseClearableGraphComponent : virtual public BaseGraphComponent {
556 /// Erase all the Nodes and Edges from the graph.
558 /// Erase all the Nodes and Edges from the graph.
563 /// Concept check function for ErasableBaseGraph.
565 /// Concept check function for ErasableBaseGraph.
567 template <typename Graph>
568 struct BaseClearableGraphComponentConcept {
570 function_requires< BaseGraphComponentConcept<Graph> >();
578 class IterableGraphComponent :
579 virtual public BaseIterableGraphComponent {
583 typedef IterableGraphComponent Graph;
585 typedef BaseGraphComponent::Node Node;
586 typedef BaseGraphComponent::Edge Edge;
588 class NodeIt : public Node {
592 // explicit NodeIt(Node) {}
593 explicit NodeIt(const Graph&) {}
595 NodeIt& operator++() { return *this; }
596 // Node operator*() const { return INVALID; }
598 bool operator==(const NodeIt&) const { return true;}
599 bool operator!=(const NodeIt&) const { return true;}
602 class EdgeIt : public Edge {
606 // explicit EdgeIt(Edge) {}
607 explicit EdgeIt(const Graph&) {}
609 EdgeIt& operator++() { return *this; }
610 // Edge operator*() const { return INVALID; }
612 bool operator==(const EdgeIt&) const { return true;}
613 bool operator!=(const EdgeIt&) const { return true;}
616 class InEdgeIt : public Edge {
620 // explicit InEdgeIt(Edge) {}
621 explicit InEdgeIt(const Graph&, const Node&) {}
623 InEdgeIt& operator++() { return *this; }
624 // Edge operator*() const { return INVALID; }
626 bool operator==(const InEdgeIt&) const { return true;}
627 bool operator!=(const InEdgeIt&) const { return true;}
630 class OutEdgeIt : public Edge {
633 OutEdgeIt(Invalid) {}
634 // explicit OutEdgeIt(Edge) {}
635 explicit OutEdgeIt(const Graph&, const Node&) {}
637 OutEdgeIt& operator++() { return *this; }
638 // Edge operator*() const { return INVALID; }
640 bool operator==(const OutEdgeIt&) const { return true;}
641 bool operator!=(const OutEdgeIt&) const { return true;}
646 template <typename Graph>
647 struct IterableGraphComponentConcept {
650 function_requires< BaseIterableGraphComponentConcept<Graph> >();
652 typedef typename Graph::Node Node;
653 typedef typename Graph::NodeIt NodeIt;
654 typedef typename Graph::Edge Edge;
655 typedef typename Graph::EdgeIt EdgeIt;
656 typedef typename Graph::InEdgeIt InEdgeIt;
657 typedef typename Graph::OutEdgeIt OutEdgeIt;
659 function_requires< GraphIteratorConcept<NodeIt, Graph, Node> >();
660 function_requires< GraphIteratorConcept<EdgeIt, Graph, Edge> >();
661 function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >();
662 function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
668 class IdMappableGraphComponent : virtual public BaseGraphComponent {
670 typedef IdMappableGraphComponent Graph;
674 typedef BaseGraphComponent::Node Node;
675 typedef BaseGraphComponent::Edge Edge;
677 class NodeIdMap : public ReadMap<Node, int> {
679 NodeIdMap(const Graph&) {}
680 int maxId() const { return -1;}
683 class EdgeIdMap : public ReadMap<Edge, int> {
685 EdgeIdMap(const Graph&) {}
686 int maxId() const { return -1;}
691 template <typename Graph>
692 struct IdMappableGraphComponentConcept {
694 function_requires< BaseGraphComponentConcept<Graph> >();
696 typedef typename Graph::EdgeIdMap EdgeIdMap;
697 function_requires<ReadMapConcept<EdgeIdMap> >();
698 EdgeIdMap edge_map(graph);
699 int n = edge_map.maxId();
700 ignore_unused_variable_warning(n);
703 typedef typename Graph::NodeIdMap NodeIdMap;
704 function_requires<ReadMapConcept<NodeIdMap> >();
705 NodeIdMap node_map(graph);
706 int n = node_map.maxId();
707 ignore_unused_variable_warning(n);
714 class MappableGraphComponent : virtual public BaseGraphComponent {
717 typedef MappableGraphComponent Graph;
719 typedef BaseGraphComponent::Node Node;
720 typedef BaseGraphComponent::Edge Edge;
722 template <typename Value>
723 class NodeMap : public ReferenceMap<Node, Value> {
725 NodeMap(const Graph&) {}
726 NodeMap(const Graph&, const Value&) {}
727 NodeMap(const NodeMap&) {}
729 NodeMap& operator=(const NodeMap&) { return *this;}
733 template <typename Value>
734 class EdgeMap : public ReferenceMap<Edge, Value> {
736 EdgeMap(const Graph&) {}
737 EdgeMap(const Graph&, const Value&) {}
738 EdgeMap(const EdgeMap&) {}
740 EdgeMap& operator=(const EdgeMap&) { return *this;}
746 template <typename Graph>
747 struct MappableGraphComponentConcept {
752 Type(int _v) : value(_v) {}
756 function_requires< BaseGraphComponentConcept<Graph> >();
758 typedef typename Graph::template NodeMap<int> IntNodeMap;
759 function_requires<GraphMapConcept<IntNodeMap,Graph> >();
761 typedef typename Graph::template NodeMap<bool> BoolNodeMap;
762 function_requires<GraphMapConcept<BoolNodeMap,Graph> >();
764 typedef typename Graph::template NodeMap<Type> TypeNodeMap;
765 function_requires<GraphMapConcept<TypeNodeMap,Graph> >();
769 typedef typename Graph::template EdgeMap<int> IntEdgeMap;
770 function_requires<GraphMapConcept<IntEdgeMap,Graph> >();
772 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;
773 function_requires<GraphMapConcept<BoolEdgeMap,Graph> >();
775 typedef typename Graph::template EdgeMap<Type> TypeEdgeMap;
776 function_requires<GraphMapConcept<TypeEdgeMap,Graph> >();
784 class ExtendableGraphComponent : virtual public BaseGraphComponent {
787 typedef ExtendableGraphComponent Graph;
789 typedef BaseGraphComponent::Node Node;
790 typedef BaseGraphComponent::Edge Edge;
796 Edge addEdge(const Node& from, const Node& to) {
802 template <typename Graph>
803 struct ExtendableGraphComponentConcept {
805 function_requires< BaseGraphComponentConcept<Graph> >();
806 typename Graph::Node node_a, node_b;
807 node_a = graph.addNode();
808 typename Graph::Edge edge;
809 edge = graph.addEdge(node_a, node_b);
814 class ErasableGraphComponent : virtual public BaseGraphComponent {
817 typedef ErasableGraphComponent Graph;
819 typedef BaseGraphComponent::Node Node;
820 typedef BaseGraphComponent::Edge Edge;
822 void erase(const Node&) {}
823 void erase(const Edge&) {}
827 template <typename Graph>
828 struct ErasableGraphComponentConcept {
830 function_requires< BaseGraphComponentConcept<Graph> >();
831 typename Graph::Node node;
833 typename Graph::Edge edge;
840 class ClearableGraphComponent : virtual public BaseGraphComponent {
843 typedef ClearableGraphComponent Graph;
845 typedef BaseGraphComponent::Node Node;
846 typedef BaseGraphComponent::Edge Edge;
852 template <typename Graph>
853 struct ClearableGraphComponentConcept {
855 function_requires< BaseGraphComponentConcept<Graph> >();