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'.
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 /// Assign operator for nodes.
166 /// The nodes are assignable.
168 Node& operator=(const Node&) { return *this;}
170 /// Equality operator.
172 /// Two iterators are equal if and only if they represents the
173 /// same node in the graph or both are invalid.
174 bool operator==(const Node&) const { return true;}
177 /// Inequality operator.
179 /// \sa operator==(const Node& n)
181 bool operator!=(const Node&) const { return true;}
183 /// Comparison operator.
185 /// This is a strict ordering between the nodes.
187 /// This ordering can be different from the iterating order of nodes.
188 /// \todo Possibly we don't need it.
189 bool operator<(const Node&) const { return true;}
192 /// Edge class of the graph.
194 /// This class represents the Edges of the graph.
199 /// Default constructor.
201 /// @warning The default constructor sets the iterator
202 /// to an undefined value.
205 /// Copy constructor.
207 /// Copy constructor.
211 /// Invalid constructor \& conversion.
213 /// This constructor initializes the iterator to be invalid.
214 /// \sa Invalid for more details.
217 /// Assign operator for edges.
219 /// The edges are assignable.
221 Edge& operator=(const Edge&) { return *this;}
223 /// Equality operator.
225 /// Two iterators are equal if and only if they represents the
226 /// same edge in the graph or both are invalid.
227 bool operator==(const Edge&) const { return true;}
230 /// Inequality operator.
232 /// \sa operator==(const Edge& n)
234 bool operator!=(const Edge&) const { return true;}
236 /// Comparison operator.
238 /// This is a strict ordering between the edges.
240 /// This ordering can be different from the iterating order of edges.
241 /// \todo Possibly we don't need it.
242 bool operator<(const Edge&) const { return true;}
245 ///Gives back the target node of an edge.
247 ///Gives back the target node of an edge.
249 Node target(const Edge&) const { return INVALID;}
251 ///Gives back the source node of an edge.
253 ///Gives back the source node of an edge.
255 Node source(const Edge&) const { return INVALID;}
259 /// Concept check structure for BaseGraph.
261 /// Concept check structure for BaseGraph.
264 template <typename Graph>
265 struct BaseGraphComponentConcept {
266 typedef typename Graph::Node Node;
267 typedef typename Graph::Edge Edge;
270 function_requires< GraphItemConcept<Node> >();
271 function_requires< GraphItemConcept<Edge> >();
283 /// An empty iterable base graph class.
285 /// This class provides beside the core graph features
286 /// core iterable interface for the graph structure.
287 /// Most of the base graphs should be conform to this concept.
289 class BaseIterableGraphComponent : virtual public BaseGraphComponent {
292 typedef BaseGraphComponent::Node Node;
293 typedef BaseGraphComponent::Edge Edge;
295 /// Gives back the first Node in the iterating order.
297 /// Gives back the first Node in the iterating order.
299 void first(Node&) const {}
301 /// Gives back the next Node in the iterating order.
303 /// Gives back the next Node in the iterating order.
305 void next(Node&) const {}
307 /// Gives back the first Edge in the iterating order.
309 /// Gives back the first Edge in the iterating order.
311 void first(Edge&) const {}
312 /// Gives back the next Edge in the iterating order.
314 /// Gives back the next Edge in the iterating order.
316 void next(Edge&) const {}
319 /// Gives back the first of the Edges point to the given Node.
321 /// Gives back the first of the Edges point to the given Node.
323 void firstIn(Edge&, const Node&) const {}
325 /// Gives back the next of the Edges points to the given Node.
328 /// Gives back the next of the Edges points to the given Node.
330 void nextIn(Edge&) const {}
332 /// Gives back the first of the Edges start from the given Node.
334 /// Gives back the first of the Edges start from the given Node.
336 void firstOut(Edge&, const Node&) const {}
338 /// Gives back the next of the Edges start from the given Node.
340 /// Gives back the next of the Edges start from the given Node.
342 void nextOut(Edge&) const {}
346 /// Concept check structure for IterableBaseGraph.
348 /// Concept check structure for IterableBaseGraph.
350 template <typename Graph>
351 struct BaseIterableGraphComponentConcept {
354 function_requires< BaseGraphComponentConcept<Graph> >();
355 typename Graph::Node node;
356 typename Graph::Edge edge;
366 graph.firstIn(edge, node);
370 graph.firstOut(edge, node);
378 /// An empty idable base graph class.
380 /// This class provides beside the core graph features
381 /// core id functions for the graph structure.
382 /// The most of the base graphs should be conform to this concept.
383 /// The id's are unique and immutable.
385 class IDableGraphComponent : virtual public BaseGraphComponent {
388 typedef BaseGraphComponent::Node Node;
389 typedef BaseGraphComponent::Edge Edge;
391 /// Gives back an unique integer id for the Node.
393 /// Gives back an unique integer id for the Node.
395 int id(const Node&) const { return -1;}
397 /// Gives back an unique integer id for the Edge.
399 /// Gives back an unique integer id for the Edge.
401 int id(const Edge&) const { return -1;}
405 /// Concept check structure for IdableBaseGraph.
407 /// Concept check structure for IdableBaseGraph.
409 template <typename Graph>
410 struct IDableGraphComponentConcept {
413 function_requires< BaseGraphComponentConcept<Graph> >();
414 typename Graph::Node node;
415 int nid = graph.id(node);
416 nid = graph.id(node);
417 typename Graph::Edge edge;
418 int eid = graph.id(edge);
419 eid = graph.id(edge);
426 /// An empty max-idable base graph class.
428 /// This class provides beside the core graph features
429 /// core max id functions for the graph structure.
430 /// The most of the base graphs should be conform to this concept.
431 /// The id's are unique and immutable.
432 class MaxIDableGraphComponent : virtual public BaseGraphComponent {
435 /// Gives back an integer greater or equal to the maximum Node id.
437 /// Gives back an integer greater or equal to the maximum Node id.
439 int maxId(Node = INVALID) const { return -1;}
441 /// Gives back an integer greater or equal to the maximum Edge id.
443 /// Gives back an integer greater or equal to the maximum Edge id.
445 int maxId(Edge = INVALID) const { return -1;}
448 /// Concept check structure for MaxIdableBaseGraph.
450 /// Concept check structure for MaxIdableBaseGraph.
452 template <typename Graph>
453 struct MaxIDableGraphComponentConcept {
456 function_requires< BaseGraphComponentConcept<Graph> >();
457 int nid = graph.maxId(typename Graph::Node());
458 ignore_unused_variable_warning(nid);
459 int eid = graph.maxId(typename Graph::Edge());
460 ignore_unused_variable_warning(eid);
466 /// An empty extendable base graph class.
468 /// This class provides beside the core graph features
469 /// core graph extend interface for the graph structure.
470 /// The most of the base graphs should be conform to this concept.
471 class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
474 typedef BaseGraphComponent::Node Node;
475 typedef BaseGraphComponent::Edge Edge;
477 /// Adds a new Node to the graph.
479 /// Adds a new Node to the graph.
485 /// Adds a new Edge connects the two Nodes to the graph.
487 /// Adds a new Edge connects the two Nodes to the graph.
489 Edge addEdge(const Node& from, const Node& to) {
495 /// Concept check structure for ExtendableBaseGraph.
497 /// Concept check structure for ExtendableBaseGraph.
499 template <typename Graph>
500 struct BaseExtendableGraphComponentConcept {
502 function_requires< BaseGraphComponentConcept<Graph> >();
503 typename Graph::Node node_a, node_b;
504 node_a = graph.addNode();
505 typename Graph::Edge edge;
506 edge = graph.addEdge(node_a, node_b);
512 /// An empty erasable base graph class.
514 /// This class provides beside the core graph features
515 /// core erase functions for the graph structure.
516 /// The most of the base graphs should be conform to this concept.
517 class BaseErasableGraphComponent : virtual public BaseGraphComponent {
520 typedef BaseGraphComponent::Node Node;
521 typedef BaseGraphComponent::Edge Edge;
523 /// Erase a Node from the graph.
525 /// Erase a Node from the graph. This function should not
526 /// erase edges connecting to the Node.
527 void erase(const Node&) {}
529 /// Erase an Edge from the graph.
531 /// Erase an Edge from the graph.
533 void erase(const Edge&) {}
537 /// Concept check structure for ErasableBaseGraph.
539 /// Concept check structure for ErasableBaseGraph.
541 template <typename Graph>
542 struct BaseErasableGraphComponentConcept {
544 function_requires< BaseGraphComponentConcept<Graph> >();
545 typename Graph::Node node;
547 typename Graph::Edge edge;
554 /// An empty clearable base graph class.
556 /// This class provides beside the core graph features
557 /// core clear functions for the graph structure.
558 /// The most of the base graphs should be conform to this concept.
559 class BaseClearableGraphComponent : virtual public BaseGraphComponent {
562 /// Erase all the Nodes and Edges from the graph.
564 /// Erase all the Nodes and Edges from the graph.
569 /// Concept check function for ErasableBaseGraph.
571 /// Concept check function for ErasableBaseGraph.
573 template <typename Graph>
574 struct BaseClearableGraphComponentConcept {
576 function_requires< BaseGraphComponentConcept<Graph> >();
584 class IterableGraphComponent :
585 virtual public BaseIterableGraphComponent {
589 typedef IterableGraphComponent Graph;
591 typedef BaseGraphComponent::Node Node;
592 typedef BaseGraphComponent::Edge Edge;
594 class NodeIt : public Node {
598 // explicit NodeIt(Node) {}
599 explicit NodeIt(const Graph&) {}
601 NodeIt& operator++() { return *this; }
602 // Node operator*() const { return INVALID; }
604 bool operator==(const NodeIt&) const { return true;}
605 bool operator!=(const NodeIt&) const { return true;}
608 class EdgeIt : public Edge {
612 // explicit EdgeIt(Edge) {}
613 explicit EdgeIt(const Graph&) {}
615 EdgeIt& operator++() { return *this; }
616 // Edge operator*() const { return INVALID; }
618 bool operator==(const EdgeIt&) const { return true;}
619 bool operator!=(const EdgeIt&) const { return true;}
622 class InEdgeIt : public Edge {
626 // explicit InEdgeIt(Edge) {}
627 explicit InEdgeIt(const Graph&, const Node&) {}
629 InEdgeIt& operator++() { return *this; }
630 // Edge operator*() const { return INVALID; }
632 bool operator==(const InEdgeIt&) const { return true;}
633 bool operator!=(const InEdgeIt&) const { return true;}
636 class OutEdgeIt : public Edge {
639 OutEdgeIt(Invalid) {}
640 // explicit OutEdgeIt(Edge) {}
641 explicit OutEdgeIt(const Graph&, const Node&) {}
643 OutEdgeIt& operator++() { return *this; }
644 // Edge operator*() const { return INVALID; }
646 bool operator==(const OutEdgeIt&) const { return true;}
647 bool operator!=(const OutEdgeIt&) const { return true;}
652 template <typename Graph>
653 struct IterableGraphComponentConcept {
655 function_requires< BaseIterableGraphComponentConcept<Graph> >();
657 typedef typename Graph::Node Node;
658 typedef typename Graph::NodeIt NodeIt;
659 typedef typename Graph::Edge Edge;
660 typedef typename Graph::EdgeIt EdgeIt;
661 typedef typename Graph::InEdgeIt InEdgeIt;
662 typedef typename Graph::OutEdgeIt OutEdgeIt;
664 function_requires< GraphIteratorConcept<NodeIt, Graph, Node> >();
665 function_requires< GraphIteratorConcept<EdgeIt, Graph, Edge> >();
666 function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >();
667 function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
672 class MappableGraphComponent : virtual public BaseGraphComponent {
675 typedef MappableGraphComponent Graph;
677 typedef BaseGraphComponent::Node Node;
678 typedef BaseGraphComponent::Edge Edge;
680 template <typename _Value>
681 class NodeMap : public ReferenceMap<Node, _Value> {
683 NodeMap(const Graph&) {}
684 NodeMap(const Graph&, const _Value&) {}
685 NodeMap(const NodeMap&) {}
687 NodeMap& operator=(const NodeMap&) { return *this;}
691 template <typename _Value>
692 class EdgeMap : public ReferenceMap<Edge, _Value> {
694 EdgeMap(const Graph&) {}
695 EdgeMap(const Graph&, const _Value&) {}
696 EdgeMap(const EdgeMap&) {}
698 EdgeMap& operator=(const EdgeMap&) { return *this;}
704 template <typename Graph>
705 struct MappableGraphComponentConcept {
710 Type(int _v) : value(_v) {}
714 function_requires< BaseGraphComponentConcept<Graph> >();
716 typedef typename Graph::template NodeMap<int> IntNodeMap;
717 function_requires<GraphMapConcept<IntNodeMap,Graph> >();
719 typedef typename Graph::template NodeMap<bool> BoolNodeMap;
720 function_requires<GraphMapConcept<BoolNodeMap,Graph> >();
722 typedef typename Graph::template NodeMap<Type> TypeNodeMap;
723 function_requires<GraphMapConcept<TypeNodeMap,Graph> >();
727 typedef typename Graph::template EdgeMap<int> IntEdgeMap;
728 function_requires<GraphMapConcept<IntEdgeMap,Graph> >();
730 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;
731 function_requires<GraphMapConcept<BoolEdgeMap,Graph> >();
733 typedef typename Graph::template EdgeMap<Type> TypeEdgeMap;
734 function_requires<GraphMapConcept<TypeEdgeMap,Graph> >();
742 class ExtendableGraphComponent : virtual public BaseGraphComponent {
745 typedef ExtendableGraphComponent Graph;
747 typedef BaseGraphComponent::Node Node;
748 typedef BaseGraphComponent::Edge Edge;
754 Edge addEdge(const Node& from, const Node& to) {
760 template <typename Graph>
761 struct ExtendableGraphComponentConcept {
763 function_requires< BaseGraphComponentConcept<Graph> >();
764 typename Graph::Node node_a, node_b;
765 node_a = graph.addNode();
766 typename Graph::Edge edge;
767 edge = graph.addEdge(node_a, node_b);
772 class ErasableGraphComponent : virtual public BaseGraphComponent {
775 typedef ErasableGraphComponent Graph;
777 typedef BaseGraphComponent::Node Node;
778 typedef BaseGraphComponent::Edge Edge;
780 void erase(const Node&) {}
781 void erase(const Edge&) {}
785 template <typename Graph>
786 struct ErasableGraphComponentConcept {
788 function_requires< BaseGraphComponentConcept<Graph> >();
789 typename Graph::Node node;
791 typename Graph::Edge edge;
798 class ClearableGraphComponent : virtual public BaseGraphComponent {
801 typedef ClearableGraphComponent Graph;
803 typedef BaseGraphComponent::Node Node;
804 typedef BaseGraphComponent::Edge Edge;
810 template <typename Graph>
811 struct ClearableGraphComponentConcept {
813 function_requires< BaseGraphComponentConcept<Graph> >();