Advances in UndirGraph.
* IterableExtender is complete
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 should instantiate it
38 /// with character 'n' and for Edge with 'e'.
40 template<char _selector>
43 /// Default constructor.
45 /// @warning The default constructor sets the item
46 /// to an undefined value.
52 GraphItem(GraphItem const&) {}
53 /// Invalid constructor \& conversion.
55 /// This constructor initializes the item to be invalid.
56 /// \sa Invalid for more details.
58 /// Assign operator for nodes.
60 /// The nodes are assignable.
62 GraphItem& operator=(GraphItem const&) { return *this; }
63 /// Equality operator.
65 /// Two iterators are equal if and only if they represents the
66 /// same node in the graph or both are invalid.
67 bool operator==(GraphItem) const { return false; }
68 /// Inequality operator.
70 /// \sa operator==(const Node& n)
72 bool operator!=(GraphItem) const { return false; }
74 // Technical requirement. Do we really need this?
75 // bool operator<(GraphItem) const { return false; }
78 template<typename _GraphItem>
83 _GraphItem i3 = INVALID;
88 // b = (ia == ib) && (ia != ib) && (ia < ib);
89 b = (ia == ib) && (ia != ib);
90 b = (ia == INVALID) && (ib != INVALID);
98 /// An empty base graph class.
100 /// This class provides the minimal set of features needed for a graph
101 /// structure. All graph concepts have to be conform to this base
104 /// \bug This is not true. The minimal graph concept is the
105 /// BaseIterableGraphComponent.
107 class BaseGraphComponent {
110 typedef BaseGraphComponent Graph;
112 /// Node class of the graph.
114 /// This class represents the Nodes of the graph.
116 typedef GraphItem<'n'> Node;
118 /// Edge class of the graph.
120 /// This class represents the Edges of the graph.
122 typedef GraphItem<'e'> Edge;
124 ///Gives back the target node of an edge.
126 ///Gives back the target node of an edge.
128 Node target(const Edge&) const { return INVALID;}
130 ///Gives back the source node of an edge.
132 ///Gives back the source node of an edge.
134 Node source(const Edge&) const { return INVALID;}
137 template <typename _Graph>
139 typedef typename _Graph::Node Node;
140 typedef typename _Graph::Edge Edge;
143 checkConcept<GraphItem<'n'>, Node>();
144 checkConcept<GraphItem<'e'>, Edge>();
157 /// An empty iterable base graph class.
159 /// This class provides beside the core graph features
160 /// core iterable interface for the graph structure.
161 /// Most of the base graphs should be conform to this concept.
163 class BaseIterableGraphComponent : virtual public BaseGraphComponent {
166 typedef BaseGraphComponent::Node Node;
167 typedef BaseGraphComponent::Edge Edge;
169 /// Gives back the first Node in the iterating order.
171 /// Gives back the first Node in the iterating order.
173 void first(Node&) const {}
175 /// Gives back the next Node in the iterating order.
177 /// Gives back the next Node in the iterating order.
179 void next(Node&) const {}
181 /// Gives back the first Edge in the iterating order.
183 /// Gives back the first Edge in the iterating order.
185 void first(Edge&) const {}
186 /// Gives back the next Edge in the iterating order.
188 /// Gives back the next Edge in the iterating order.
190 void next(Edge&) const {}
193 /// Gives back the first of the Edges point to the given Node.
195 /// Gives back the first of the Edges point to the given Node.
197 void firstIn(Edge&, const Node&) const {}
199 /// Gives back the next of the Edges points to the given Node.
202 /// Gives back the next of the Edges points to the given Node.
204 void nextIn(Edge&) const {}
206 /// Gives back the first of the Edges start from the given Node.
208 /// Gives back the first of the Edges start from the given Node.
210 void firstOut(Edge&, const Node&) const {}
212 /// Gives back the next of the Edges start from the given Node.
214 /// Gives back the next of the Edges start from the given Node.
216 void nextOut(Edge&) const {}
219 template <typename _Graph>
223 checkConcept< BaseGraphComponent, _Graph >();
224 typename _Graph::Node node;
225 typename _Graph::Edge edge;
235 graph.firstIn(edge, node);
239 graph.firstOut(edge, node);
248 /// An empty idable base graph class.
250 /// This class provides beside the core graph features
251 /// core id functions for the graph structure.
252 /// The most of the base graphs should be conform to this concept.
253 /// The id's are unique and immutable.
254 class IDableGraphComponent : virtual public BaseGraphComponent {
257 typedef BaseGraphComponent::Node Node;
258 typedef BaseGraphComponent::Edge Edge;
260 /// Gives back an unique integer id for the Node.
262 /// Gives back an unique integer id for the Node.
264 int id(const Node&) const { return -1;}
266 /// Gives back an unique integer id for the Edge.
268 /// Gives back an unique integer id for the Edge.
270 int id(const Edge&) const { return -1;}
272 template <typename _Graph>
276 checkConcept< BaseGraphComponent, _Graph >();
277 typename _Graph::Node node;
278 int nid = graph.id(node);
279 nid = graph.id(node);
280 typename _Graph::Edge edge;
281 int eid = graph.id(edge);
282 eid = graph.id(edge);
290 /// An empty max-idable base graph class.
292 /// This class provides beside the core graph features
293 /// core max 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.
296 class MaxIDableGraphComponent : virtual public BaseGraphComponent {
299 /// Gives back an integer greater or equal to the maximum Node id.
301 /// Gives back an integer greater or equal to the maximum Node id.
303 int maxId(Node = INVALID) const { return -1;}
305 /// Gives back an integer greater or equal to the maximum Edge id.
307 /// Gives back an integer greater or equal to the maximum Edge id.
309 int maxId(Edge = INVALID) const { return -1;}
311 template <typename _Graph>
315 checkConcept<BaseGraphComponent, _Graph>();
316 int nid = graph.maxId(typename _Graph::Node());
317 ignore_unused_variable_warning(nid);
318 int eid = graph.maxId(typename _Graph::Edge());
319 ignore_unused_variable_warning(eid);
326 /// An empty extendable base graph class.
328 /// This class provides beside the core graph features
329 /// core graph extend interface for the graph structure.
330 /// The most of the base graphs should be conform to this concept.
331 class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
334 typedef BaseGraphComponent::Node Node;
335 typedef BaseGraphComponent::Edge Edge;
337 /// Adds a new Node to the graph.
339 /// Adds a new Node to the graph.
345 /// Adds a new Edge connects the two Nodes to the graph.
347 /// Adds a new Edge connects the two Nodes to the graph.
349 Edge addEdge(const Node& from, const Node& to) {
353 template <typename _Graph>
356 checkConcept<BaseGraphComponent, _Graph >();
357 typename _Graph::Node node_a, node_b;
358 node_a = graph.addNode();
359 typename _Graph::Edge edge;
360 edge = graph.addEdge(node_a, node_b);
367 /// An empty erasable base graph class.
369 /// This class provides beside the core graph features
370 /// core erase functions for the graph structure.
371 /// The most of the base graphs should be conform to this concept.
372 class BaseErasableGraphComponent : virtual public BaseGraphComponent {
375 typedef BaseGraphComponent::Node Node;
376 typedef BaseGraphComponent::Edge Edge;
378 /// Erase a Node from the graph.
380 /// Erase a Node from the graph. This function should not
381 /// erase edges connecting to the Node.
382 void erase(const Node&) {}
384 /// Erase an Edge from the graph.
386 /// Erase an Edge from the graph.
388 void erase(const Edge&) {}
390 template <typename _Graph>
393 checkConcept<BaseGraphComponent, _Graph>();
394 typename _Graph::Node node;
396 typename _Graph::Edge edge;
404 /// An empty clearable base graph class.
406 /// This class provides beside the core graph features
407 /// core clear functions for the graph structure.
408 /// The most of the base graphs should be conform to this concept.
409 class BaseClearableGraphComponent : virtual public BaseGraphComponent {
412 /// Erase all the Nodes and Edges from the graph.
414 /// Erase all the Nodes and Edges from the graph.
418 template <typename _Graph>
421 checkConcept< BaseGraphComponent, _Graph>();
430 /// Skeleton class for graph NodeIt and EdgeIt
432 /// Skeleton class for graph NodeIt and EdgeIt.
434 template <typename _Graph, typename _Item>
435 class GraphIterator : public _Item {
437 /// \todo Don't we need the Item type as typedef?
439 /// Default constructor.
441 /// @warning The default constructor sets the iterator
442 /// to an undefined value.
444 /// Copy constructor.
446 /// Copy constructor.
448 GraphIterator(GraphIterator const&) {}
449 /// Sets the iterator to the first item.
451 /// Sets the iterator to the first item of \c the graph.
453 explicit GraphIterator(const _Graph&) {}
454 /// Invalid constructor \& conversion.
456 /// This constructor initializes the item to be invalid.
457 /// \sa Invalid for more details.
458 GraphIterator(Invalid) {}
459 /// Assign operator for items.
461 /// The items are assignable.
463 GraphIterator& operator=(GraphIterator const&) { return *this; }
466 /// Assign the iterator to the next item.
468 GraphIterator& operator++() { return *this; }
469 // Node operator*() const { return INVALID; }
470 /// Equality operator
472 /// Two iterators are equal if and only if they point to the
473 /// same object or both are invalid.
474 bool operator==(const GraphIterator&) const { return true;}
475 /// Inequality operator
477 /// \sa operator==(Node n)
479 bool operator!=(const GraphIterator&) const { return true;}
481 template<typename _GraphIterator>
484 // checkConcept< Item, _GraphIterator >();
485 _GraphIterator it1(g);
487 /// \todo Do we need NodeIt(Node) kind of constructor?
488 // _GraphIterator it2(bj);
494 /// \bug This should be: is_base_and_derived<BaseItem, _GraphIterator>
502 /// Skeleton class for graph InEdgeIt and OutEdgeIt
504 /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
505 /// base class, the _selector is a additional template parameter. For
506 /// InEdgeIt you should instantiate it with character 'i' and for
507 /// OutEdgeIt with 'o'.
508 /// \todo Is this a good name for this concept?
509 template <typename Graph,
510 typename Edge = typename Graph::Edge,
511 char _selector = '0'>
512 class GraphIncIterator : public Edge {
514 /// Default constructor.
516 /// @warning The default constructor sets the iterator
517 /// to an undefined value.
518 GraphIncIterator() {}
519 /// Copy constructor.
521 /// Copy constructor.
523 GraphIncIterator(GraphIncIterator const&) {}
524 /// Sets the iterator to the first edge incoming into or outgoing from the node.
526 /// Sets the iterator to the first edge incoming into or outgoing from the node.
528 explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {}
529 /// Invalid constructor \& conversion.
531 /// This constructor initializes the item to be invalid.
532 /// \sa Invalid for more details.
533 GraphIncIterator(Invalid) {}
534 /// Assign operator for nodes.
536 /// The nodes are assignable.
538 GraphIncIterator& operator=(GraphIncIterator const&) { return *this; }
541 /// Assign the iterator to the next node.
543 GraphIncIterator& operator++() { return *this; }
545 // Node operator*() const { return INVALID; }
547 /// Equality operator
549 /// Two iterators are equal if and only if they point to the
550 /// same object or both are invalid.
551 bool operator==(const GraphIncIterator&) const { return true;}
553 /// Inequality operator
555 /// \sa operator==(Node n)
557 bool operator!=(const GraphIncIterator&) const { return true;}
559 template <typename _GraphIncIterator>
561 typedef typename Graph::Node Node;
563 checkConcept<GraphItem<'e'>, _GraphIncIterator>();
564 _GraphIncIterator it1(graph, node);
565 /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
566 // _GraphIncIterator it2(edge);
567 _GraphIncIterator it2;
583 /// An empty iterable base graph class.
585 /// This class provides beside the core graph features
586 /// iterator based iterable interface for the graph structure.
587 /// This concept is part of the StaticGraphConcept.
588 class IterableGraphComponent : virtual public BaseGraphComponent {
592 typedef IterableGraphComponent Graph;
594 typedef BaseGraphComponent::Node Node;
595 typedef BaseGraphComponent::Edge Edge;
597 /// This iterator goes through each node.
599 /// This iterator goes through each node.
601 typedef GraphIterator<Graph, Node> NodeIt;
602 /// This iterator goes through each node.
604 /// This iterator goes through each node.
606 typedef GraphIterator<Graph, Edge> EdgeIt;
607 /// This iterator goes trough the incoming edges of a node.
609 /// This iterator goes trough the \e inccoming edges of a certain node
611 typedef GraphIncIterator<Graph, Edge, 'i'> InEdgeIt;
612 /// This iterator goes trough the outgoing edges of a node.
614 /// This iterator goes trough the \e outgoing edges of a certain node
616 typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt;
619 template <typename _Graph>
622 checkConcept< BaseGraphComponent, _Graph>();
624 checkConcept<GraphIterator<_Graph, typename _Graph::Edge>, typename _Graph::EdgeIt >();
625 checkConcept<GraphIterator<_Graph, typename _Graph::Node>, typename _Graph::NodeIt >();
626 checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt >();
627 checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >();
632 template <typename Graph, typename Item, typename _Value>
633 class GraphMap : public ReadWriteMap<Item, _Value> {
637 explicit GraphMap(const Graph&) {}
638 GraphMap(const Graph&, const _Value&) {}
639 GraphMap(const GraphMap&) {}
641 GraphMap& operator=(const GraphMap&) { return *this;}
643 template<typename _Map>
646 checkConcept<ReadWriteMap<Item, _Value>, _Map >();
647 // Construction with a graph parameter
649 // Constructor with a graph and a default value parameter
651 // Copy constructor. Do we need it?
653 // Copy operator. Do we need it?
656 ignore_unused_variable_warning(a2);
661 const typename GraphMap::Value &t;
666 /// An empty mappable base graph class.
668 /// This class provides beside the core graph features
669 /// map interface for the graph structure.
670 /// This concept is part of the StaticGraphConcept.
671 class MappableGraphComponent : virtual public BaseGraphComponent {
674 typedef MappableGraphComponent Graph;
676 typedef BaseGraphComponent::Node Node;
677 typedef BaseGraphComponent::Edge Edge;
679 /// ReadWrite map of the nodes.
681 /// ReadWrite map of the nodes.
683 template <typename _Value>
684 class NodeMap : public GraphMap<Graph, Node, _Value> {
688 // \todo call the right parent class constructor
689 explicit NodeMap(const Graph&) {}
690 NodeMap(const Graph&, const _Value&) {}
691 NodeMap(const NodeMap&) {}
693 NodeMap& operator=(const NodeMap&) { return *this;}
697 /// ReadWrite map of the edges.
699 /// ReadWrite map of the edges.
701 template <typename _Value>
702 class EdgeMap : public GraphMap<Graph, Edge, _Value> {
706 // \todo call the right parent class constructor
707 explicit EdgeMap(const Graph&) {}
708 EdgeMap(const Graph&, const _Value&) {}
709 EdgeMap(const EdgeMap&) {}
711 EdgeMap& operator=(const EdgeMap&) { return *this;}
715 template <typename _Graph>
721 Type(int _v) : value(_v) {}
725 checkConcept<BaseGraphComponent, _Graph>();
727 typedef typename _Graph::template NodeMap<int> IntNodeMap;
728 checkConcept<GraphMap<_Graph, typename _Graph::Node, int>, IntNodeMap >();
730 typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
731 checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>, BoolNodeMap >();
733 typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
734 checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>, TypeNodeMap >();
738 typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
739 checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>, IntEdgeMap >();
741 typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
742 checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>, BoolEdgeMap >();
744 typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
745 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>, TypeEdgeMap >();
754 class ExtendableGraphComponent : virtual public BaseGraphComponent {
757 typedef ExtendableGraphComponent Graph;
759 typedef BaseGraphComponent::Node Node;
760 typedef BaseGraphComponent::Edge Edge;
766 Edge addEdge(const Node& from, const Node& to) {
770 template <typename _Graph>
773 checkConcept<BaseGraphComponent, _Graph >();
774 typename _Graph::Node node_a, node_b;
775 node_a = graph.addNode();
776 typename _Graph::Edge edge;
777 edge = graph.addEdge(node_a, node_b);
782 class ErasableGraphComponent : virtual public BaseGraphComponent {
785 typedef ErasableGraphComponent Graph;
787 typedef BaseGraphComponent::Node Node;
788 typedef BaseGraphComponent::Edge Edge;
790 void erase(const Node&) {}
791 void erase(const Edge&) {}
793 template <typename _Graph>
796 checkConcept<BaseGraphComponent, _Graph >();
797 typename _Graph::Node node;
799 typename _Graph::Edge edge;
807 class ClearableGraphComponent : virtual public BaseGraphComponent {
810 typedef ClearableGraphComponent Graph;
812 typedef BaseGraphComponent::Node Node;
813 typedef BaseGraphComponent::Edge Edge;
818 template <typename _Graph>
819 struct ClearableGraphComponentConcept {
821 checkConcept< BaseGraphComponent, _Graph >();