Updated because of the recent changes in simann.h.
2 * src/lemon/skeletons/graph.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
17 #ifndef LEMON_SKELETON_GRAPH_H
18 #define LEMON_SKELETON_GRAPH_H
22 ///\brief Declaration of Graph.
24 #include <lemon/invalid.h>
25 #include <lemon/skeletons/maps.h>
26 #include <lemon/concept_check.h>
27 #include <lemon/skeletons/graph_component.h>
32 /// \addtogroup skeletons
35 // /// An empty static graph class.
37 // /// This class provides all the common features of a graph structure,
38 // /// however completely without implementations and real data structures
39 // /// behind the interface.
40 // /// All graph algorithms should compile with this class, but it will not
41 // /// run properly, of course.
43 // /// It can be used for checking the interface compatibility,
44 // /// or it can serve as a skeleton of a new graph structure.
46 // /// Also, you will find here the full documentation of a certain graph
47 // /// feature, the documentation of a real graph imlementation
48 // /// like @ref ListGraph or
49 // /// @ref SmartGraph will just refer to this structure.
51 // /// \todo A pages describing the concept of concept description would
56 // /// Defalult constructor.
58 // /// Defalult constructor.
61 // ///Copy consructor.
63 // // ///\todo It is not clear, what we expect from a copy constructor.
64 // // ///E.g. How to assign the nodes/edges to each other? What about maps?
65 // // StaticGraph(const StaticGraph& g) { }
67 // /// The base type of node iterators,
68 // /// or in other words, the trivial node iterator.
70 // /// This is the base type of each node iterator,
71 // /// thus each kind of node iterator converts to this.
72 // /// More precisely each kind of node iterator should be inherited
73 // /// from the trivial node iterator.
76 // /// Default constructor
78 // /// @warning The default constructor sets the iterator
79 // /// to an undefined value.
81 // /// Copy constructor.
83 // /// Copy constructor.
85 // Node(const Node&) { }
87 // /// Invalid constructor \& conversion.
89 // /// This constructor initializes the iterator to be invalid.
90 // /// \sa Invalid for more details.
92 // /// Equality operator
94 // /// Two iterators are equal if and only if they point to the
95 // /// same object or both are invalid.
96 // bool operator==(Node) const { return true; }
98 // /// Inequality operator
100 // /// \sa operator==(Node n)
102 // bool operator!=(Node) const { return true; }
104 // ///Comparison operator.
106 // ///This is a strict ordering between the nodes.
108 // ///This ordering can be different from the order in which NodeIt
109 // ///goes through the nodes.
110 // ///\todo Possibly we don't need it.
111 // bool operator<(Node) const { return true; }
114 // /// This iterator goes through each node.
116 // /// This iterator goes through each node.
117 // /// Its usage is quite simple, for example you can count the number
118 // /// of nodes in graph \c g of type \c Graph like this:
121 // /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
123 // class NodeIt : public Node {
125 // /// Default constructor
127 // /// @warning The default constructor sets the iterator
128 // /// to an undefined value.
130 // /// Copy constructor.
132 // /// Copy constructor.
134 // NodeIt(const NodeIt&) { }
135 // /// Invalid constructor \& conversion.
137 // /// Initialize the iterator to be invalid.
138 // /// \sa Invalid for more details.
139 // NodeIt(Invalid) { }
140 // /// Sets the iterator to the first node.
142 // /// Sets the iterator to the first node of \c g.
144 // NodeIt(const StaticGraph& g) { }
145 // /// Node -> NodeIt conversion.
147 // /// Sets the iterator to the node of \c g pointed by the trivial
149 // /// This feature necessitates that each time we
150 // /// iterate the edge-set, the iteration order is the same.
151 // NodeIt(const StaticGraph& g, const Node& n) { }
154 // /// Assign the iterator to the next node.
156 // NodeIt& operator++() { return *this; }
160 // /// The base type of the edge iterators.
162 // /// The base type of the edge iterators.
166 // /// Default constructor
168 // /// @warning The default constructor sets the iterator
169 // /// to an undefined value.
171 // /// Copy constructor.
173 // /// Copy constructor.
175 // Edge(const Edge&) { }
176 // /// Initialize the iterator to be invalid.
178 // /// Initialize the iterator to be invalid.
181 // /// Equality operator
183 // /// Two iterators are equal if and only if they point to the
184 // /// same object or both are invalid.
185 // bool operator==(Edge) const { return true; }
186 // /// Inequality operator
188 // /// \sa operator==(Node n)
190 // bool operator!=(Edge) const { return true; }
191 // ///Comparison operator.
193 // ///This is a strict ordering between the nodes.
195 // ///This ordering can be different from the order in which NodeIt
196 // ///goes through the nodes.
197 // ///\todo Possibly we don't need it.
198 // bool operator<(Edge) const { return true; }
201 // /// This iterator goes trough the outgoing edges of a node.
203 // /// This iterator goes trough the \e outgoing edges of a certain node
205 // /// Its usage is quite simple, for example you can count the number
206 // /// of outgoing edges of a node \c n
207 // /// in graph \c g of type \c Graph as follows.
210 // /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
213 // class OutEdgeIt : public Edge {
215 // /// Default constructor
217 // /// @warning The default constructor sets the iterator
218 // /// to an undefined value.
220 // /// Copy constructor.
222 // /// Copy constructor.
224 // OutEdgeIt(const OutEdgeIt&) { }
225 // /// Initialize the iterator to be invalid.
227 // /// Initialize the iterator to be invalid.
229 // OutEdgeIt(Invalid) { }
230 // /// This constructor sets the iterator to first outgoing edge.
232 // /// This constructor set the iterator to the first outgoing edge of
234 // ///@param n the node
235 // ///@param g the graph
236 // OutEdgeIt(const StaticGraph& g, const Node& n) { }
237 // /// Edge -> OutEdgeIt conversion
239 // /// Sets the iterator to the value of the trivial iterator \c e.
240 // /// This feature necessitates that each time we
241 // /// iterate the edge-set, the iteration order is the same.
242 // OutEdgeIt(const StaticGraph& g, const Edge& e) { }
243 // ///Next outgoing edge
245 // /// Assign the iterator to the next
246 // /// outgoing edge of the corresponding node.
247 // OutEdgeIt& operator++() { return *this; }
250 // /// This iterator goes trough the incoming edges of a node.
252 // /// This iterator goes trough the \e incoming edges of a certain node
254 // /// Its usage is quite simple, for example you can count the number
255 // /// of outgoing edges of a node \c n
256 // /// in graph \c g of type \c Graph as follows.
259 // /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
262 // class InEdgeIt : public Edge {
264 // /// Default constructor
266 // /// @warning The default constructor sets the iterator
267 // /// to an undefined value.
269 // /// Copy constructor.
271 // /// Copy constructor.
273 // InEdgeIt(const InEdgeIt&) { }
274 // /// Initialize the iterator to be invalid.
276 // /// Initialize the iterator to be invalid.
278 // InEdgeIt(Invalid) { }
279 // /// This constructor sets the iterator to first incoming edge.
281 // /// This constructor set the iterator to the first incoming edge of
283 // ///@param n the node
284 // ///@param g the graph
285 // InEdgeIt(const StaticGraph& g, const Node& n) { }
286 // /// Edge -> InEdgeIt conversion
288 // /// Sets the iterator to the value of the trivial iterator \c e.
289 // /// This feature necessitates that each time we
290 // /// iterate the edge-set, the iteration order is the same.
291 // InEdgeIt(const StaticGraph& g, const Edge& n) { }
292 // /// Next incoming edge
294 // /// Assign the iterator to the next inedge of the corresponding node.
296 // InEdgeIt& operator++() { return *this; }
298 // /// This iterator goes through each edge.
300 // /// This iterator goes through each edge of a graph.
301 // /// Its usage is quite simple, for example you can count the number
302 // /// of edges in a graph \c g of type \c Graph as follows:
305 // /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
307 // class EdgeIt : public Edge {
309 // /// Default constructor
311 // /// @warning The default constructor sets the iterator
312 // /// to an undefined value.
314 // /// Copy constructor.
316 // /// Copy constructor.
318 // EdgeIt(const EdgeIt&) { }
319 // /// Initialize the iterator to be invalid.
321 // /// Initialize the iterator to be invalid.
323 // EdgeIt(Invalid) { }
324 // /// This constructor sets the iterator to first edge.
326 // /// This constructor set the iterator to the first edge of
328 // ///@param g the graph
329 // EdgeIt(const StaticGraph& g) { }
330 // /// Edge -> EdgeIt conversion
332 // /// Sets the iterator to the value of the trivial iterator \c e.
333 // /// This feature necessitates that each time we
334 // /// iterate the edge-set, the iteration order is the same.
335 // EdgeIt(const StaticGraph&, const Edge&) { }
338 // /// Assign the iterator to the next
339 // /// edge of the corresponding node.
340 // EdgeIt& operator++() { return *this; }
343 // /// First node of the graph.
345 // /// \retval i the first node.
346 // /// \return the first node.
348 // NodeIt& first(NodeIt& i) const { return i; }
350 // /// The first incoming edge.
352 // /// The first incoming edge.
354 // InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
355 // /// The first outgoing edge.
357 // /// The first outgoing edge.
359 // OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
360 // /// The first edge of the Graph.
362 // /// The first edge of the Graph.
364 // EdgeIt& first(EdgeIt& i) const { return i; }
366 // ///Gives back the head node of an edge.
368 // ///Gives back the head node of an edge.
370 // Node head(Edge) const { return INVALID; }
371 // ///Gives back the tail node of an edge.
373 // ///Gives back the tail node of an edge.
375 // Node tail(Edge) const { return INVALID; }
377 // ///Gives back the \e id of a node.
379 // ///\warning Not all graph structures provide this feature.
381 // ///\todo Should each graph provide \c id?
382 // int id(const Node&) const { return 0; }
383 // ///Gives back the \e id of an edge.
385 // ///\warning Not all graph structures provide this feature.
387 // ///\todo Should each graph provide \c id?
388 // int id(const Edge&) const { return 0; }
392 // ///\todo Should it be in the concept?
394 // int nodeNum() const { return 0; }
397 // ///\todo Should it be in the concept?
399 // int edgeNum() const { return 0; }
402 // ///Reference map of the nodes to type \c T.
404 // /// \ingroup skeletons
405 // ///Reference map of the nodes to type \c T.
407 // /// \warning Making maps that can handle bool type (NodeMap<bool>)
408 // /// needs some extra attention!
409 // template<class T> class NodeMap : public ReferenceMap< Node, T >
414 // NodeMap(const StaticGraph&) { }
416 // NodeMap(const StaticGraph&, T) { }
418 // ///Copy constructor
419 // template<typename TT> NodeMap(const NodeMap<TT>&) { }
420 // ///Assignment operator
421 // template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
425 // ///Reference map of the edges to type \c T.
427 // /// \ingroup skeletons
428 // ///Reference map of the edges to type \c T.
430 // /// \warning Making maps that can handle bool type (EdgeMap<bool>)
431 // /// needs some extra attention!
432 // template<class T> class EdgeMap
433 // : public ReferenceMap<Edge,T>
438 // EdgeMap(const StaticGraph&) { }
440 // EdgeMap(const StaticGraph&, T) { }
442 // ///Copy constructor
443 // template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
444 // ///Assignment operator
445 // template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
450 // struct DummyType {
453 // DummyType(int p) : value(p) {}
454 // DummyType& operator=(int p) { value = p; return *this;}
457 // ///\brief Checks whether \c G meets the
458 // ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept
459 // template<class Graph> void checkCompileStaticGraph(Graph &G)
461 // typedef typename Graph::Node Node;
462 // typedef typename Graph::NodeIt NodeIt;
463 // typedef typename Graph::Edge Edge;
464 // typedef typename Graph::EdgeIt EdgeIt;
465 // typedef typename Graph::InEdgeIt InEdgeIt;
466 // typedef typename Graph::OutEdgeIt OutEdgeIt;
469 // Node i; Node j(i); Node k(INVALID);
472 // b=(i==INVALID); b=(i!=INVALID);
473 // b=(i==j); b=(i!=j); b=(i<j);
476 // NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
481 // b=(i==INVALID); b=(i!=INVALID);
484 // b=(i==j); b=(i!=j); b=(i<j);
485 // //Node ->NodeIt conversion
489 // Edge i; Edge j(i); Edge k(INVALID);
492 // b=(i==INVALID); b=(i!=INVALID);
493 // b=(i==j); b=(i!=j); b=(i<j);
496 // EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
501 // b=(i==INVALID); b=(i!=INVALID);
504 // b=(i==j); b=(i!=j); b=(i<j);
505 // //Edge ->EdgeIt conversion
510 // InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
515 // b=(i==INVALID); b=(i!=INVALID);
518 // b=(i==j); b=(i!=j); b=(i<j);
519 // //Edge ->InEdgeIt conversion
524 // OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
529 // b=(i==INVALID); b=(i!=INVALID);
532 // b=(i==j); b=(i!=j); b=(i<j);
533 // //Edge ->OutEdgeIt conversion
534 // OutEdgeIt ei(G,e);
545 // { Node n; int i=G.id(n); i=i; }
546 // { Edge e; int i=G.id(e); i=i; }
550 // typename Graph::template NodeMap<int> m(G);
552 // typename Graph::template NodeMap<int> const &cm = m;
553 // //Inicialize with default value
554 // typename Graph::template NodeMap<int> mdef(G,12);
556 // typename Graph::template NodeMap<int> mm(cm);
557 // //Copy from another type
558 // typename Graph::template NodeMap<double> dm(cm);
559 // //Copy to more complex type
560 // typename Graph::template NodeMap<DummyType> em(cm);
562 // v=m[k]; m[k]=v; m.set(k,v);
566 // dm=cm; //Copy from another type
567 // em=cm; //Copy to more complex type
569 // //Check the typedef's
570 // typename Graph::template NodeMap<int>::ValueType val;
572 // typename Graph::template NodeMap<int>::KeyType key;
573 // key = typename Graph::NodeIt(G);
578 // typename Graph::template NodeMap<bool> m(G);
579 // typename Graph::template NodeMap<bool> const &cm = m; //Const map
580 // //Inicialize with default value
581 // typename Graph::template NodeMap<bool> mdef(G,12);
582 // typename Graph::template NodeMap<bool> mm(cm); //Copy
583 // typename Graph::template NodeMap<int> dm(cm); //Copy from another type
585 // v=m[k]; m[k]=v; m.set(k,v);
589 // dm=cm; //Copy from another type
590 // m=dm; //Copy to another type
593 // //Check the typedef's
594 // typename Graph::template NodeMap<bool>::ValueType val;
596 // typename Graph::template NodeMap<bool>::KeyType key;
597 // key= typename Graph::NodeIt(G);
603 // typename Graph::template EdgeMap<int> m(G);
604 // typename Graph::template EdgeMap<int> const &cm = m; //Const map
605 // //Inicialize with default value
606 // typename Graph::template EdgeMap<int> mdef(G,12);
607 // typename Graph::template EdgeMap<int> mm(cm); //Copy
608 // typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
610 // v=m[k]; m[k]=v; m.set(k,v);
614 // dm=cm; //Copy from another type
616 // //Check the typedef's
617 // typename Graph::template EdgeMap<int>::ValueType val;
619 // typename Graph::template EdgeMap<int>::KeyType key;
620 // key= typename Graph::EdgeIt(G);
625 // typename Graph::template EdgeMap<bool> m(G);
626 // typename Graph::template EdgeMap<bool> const &cm = m; //Const map
627 // //Inicialize with default value
628 // typename Graph::template EdgeMap<bool> mdef(G,12);
629 // typename Graph::template EdgeMap<bool> mm(cm); //Copy
630 // typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
632 // v=m[k]; m[k]=v; m.set(k,v);
636 // dm=cm; //Copy from another type
637 // m=dm; //Copy to another type
639 // //Check the typedef's
640 // typename Graph::template EdgeMap<bool>::ValueType val;
642 // typename Graph::template EdgeMap<bool>::KeyType key;
643 // key= typename Graph::EdgeIt(G);
648 // /// An empty non-static graph class.
650 // /// This class provides everything that \ref StaticGraph
651 // /// with additional functionality which enables to build a
652 // /// graph from scratch.
653 // class ExtendableGraph : public StaticGraph
656 // /// Defalult constructor.
658 // /// Defalult constructor.
660 // ExtendableGraph() { }
661 // ///Add a new node to the graph.
663 // /// \return the new node.
665 // Node addNode() { return INVALID; }
666 // ///Add a new edge to the graph.
668 // ///Add a new edge to the graph with tail node \c t
669 // ///and head node \c h.
670 // ///\return the new edge.
671 // Edge addEdge(Node h, Node t) { return INVALID; }
673 // /// Resets the graph.
675 // /// This function deletes all edges and nodes of the graph.
676 // /// It also frees the memory allocated to store them.
677 // /// \todo It might belong to \ref ErasableGraph.
682 // ///\brief Checks whether \c G meets the
683 // ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept
684 // template<class Graph> void checkCompileExtendableGraph(Graph &G)
686 // checkCompileStaticGraph(G);
688 // typedef typename Graph::Node Node;
689 // typedef typename Graph::NodeIt NodeIt;
690 // typedef typename Graph::Edge Edge;
691 // typedef typename Graph::EdgeIt EdgeIt;
692 // typedef typename Graph::InEdgeIt InEdgeIt;
693 // typedef typename Graph::OutEdgeIt OutEdgeIt;
705 // /// An empty erasable graph class.
707 // /// This class is an extension of \ref ExtendableGraph. It also makes it
708 // /// possible to erase edges or nodes.
709 // class ErasableGraph : public ExtendableGraph
712 // /// Defalult constructor.
714 // /// Defalult constructor.
716 // ErasableGraph() { }
717 // /// Deletes a node.
719 // /// Deletes node \c n node.
721 // void erase(Node n) { }
722 // /// Deletes an edge.
724 // /// Deletes edge \c e edge.
726 // void erase(Edge e) { }
729 // template<class Graph> void checkCompileGraphEraseEdge(Graph &G)
731 // typename Graph::Edge e;
735 // template<class Graph> void checkCompileGraphEraseNode(Graph &G)
737 // typename Graph::Node n;
741 // ///\brief Checks whether \c G meets the
742 // ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept
743 // template<class Graph> void checkCompileErasableGraph(Graph &G)
745 // checkCompileExtendableGraph(G);
746 // checkCompileGraphEraseNode(G);
747 // checkCompileGraphEraseEdge(G);
750 // ///Checks whether a graph has findEdge() member function.
752 // ///\todo findEdge() might be a global function.
754 // template<class Graph> void checkCompileGraphFindEdge(Graph &G)
756 // typedef typename Graph::NodeIt Node;
757 // typedef typename Graph::NodeIt NodeIt;
759 // G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
760 // G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));
765 /************* New GraphBase stuff **************/
768 /// \bug The nodes and edges are not allowed to inherit from the
771 class BaseGraphItem {
774 BaseGraphItem(Invalid) {}
776 // We explicitely list these:
777 BaseGraphItem(BaseGraphItem const&) {}
778 BaseGraphItem& operator=(BaseGraphItem const&) { return *this; }
780 bool operator==(BaseGraphItem) const { return false; }
781 bool operator!=(BaseGraphItem) const { return false; }
783 // Technical requirement. Do we really need this?
784 bool operator<(BaseGraphItem) const { return false; }
788 /// A minimal GraphBase concept
790 /// This class describes a minimal concept which can be extended to a
791 /// full-featured graph with \ref GraphFactory.
798 /// \bug Nodes and Edges are comparable each other
800 class Node : public BaseGraphItem {};
801 class Edge : public BaseGraphItem {};
804 void firstNode(Node &n) const { }
805 void firstEdge(Edge &e) const { }
807 void firstOutEdge(Edge &e, Node) const { }
808 void firstInEdge(Edge &e, Node) const { }
810 void nextNode(Node &n) const { }
811 void nextEdge(Edge &e) const { }
814 // Question: isn't it reasonable if this methods have a Node
815 // parameter? Like this:
816 // Edge& nextOut(Edge &e, Node) const { return e; }
817 void nextOutEdge(Edge &e) const { }
818 void nextInEdge(Edge &e) const { }
820 Node head(Edge) const { return Node(); }
821 Node tail(Edge) const { return Node(); }
824 // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
830 // We need a special slimer concept which does not provide maps (it
831 // wouldn't be strictly slimer, cause for map-factory id() & friends
835 class NodeMap : public GraphMap<Node, T, GraphBase> {};
838 class EdgeMap : public GraphMap<Edge, T, GraphBase> {};
843 /**************** Concept checking classes ****************/
845 template<typename BGI>
846 struct BaseGraphItemConcept {
854 if ( i2 != i3 && i3 < i2 )
863 : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent {
865 typedef BaseGraphComponent::Node Node;
866 typedef BaseGraphComponent::Edge Edge;
869 template <typename Graph>
870 struct StaticGraphConcept {
872 function_requires<BaseGraphComponentConcept<Graph> >();
873 function_requires<IterableGraphComponentConcept<Graph> >();
874 function_requires<MappableGraphComponentConcept<Graph> >();
879 class ExtendableGraph
880 : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
882 typedef BaseGraphComponent::Node Node;
883 typedef BaseGraphComponent::Edge Edge;
886 template <typename Graph>
887 struct ExtendableGraphConcept {
889 function_requires<StaticGraphConcept<Graph> >();
890 function_requires<ExtendableGraphComponentConcept<Graph> >();
891 function_requires<ClearableGraphComponentConcept<Graph> >();
897 : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent {
899 typedef BaseGraphComponent::Node Node;
900 typedef BaseGraphComponent::Edge Edge;
903 template <typename Graph>
904 struct ErasableGraphConcept {
906 function_requires<ExtendableGraphConcept<Graph> >();
907 function_requires<ErasableGraphComponentConcept<Graph> >();
913 } //namespace skeleton
918 #endif // LEMON_SKELETON_GRAPH_H