graph_component.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00022 
00023 
00024 #ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H
00025 #define LEMON_CONCEPT_GRAPH_COMPONENT_H
00026 
00027 #include <lemon/invalid.h>
00028 #include <lemon/concept/maps.h>
00029 
00030 #include <lemon/bits/alteration_notifier.h>
00031 
00032 namespace lemon {
00033   namespace concept {
00034 
00035     /****************   Graph iterator concepts   ****************/
00036 
00038 
00047 
00048 #ifndef DOXYGEN
00049     template <char _selector = '0'>
00050 #endif
00051     class GraphItem {
00052     public:
00054       
00058       GraphItem() {}
00060       
00063       GraphItem(GraphItem const&) {}
00065 
00068       GraphItem(Invalid) {}
00070 
00073       GraphItem& operator=(GraphItem const&) { return *this; }
00075       
00078       bool operator==(GraphItem) const { return false; }
00080         
00083       bool operator!=(GraphItem) const { return false; }
00084 
00086 
00095       bool operator<(GraphItem) const { return false; }
00096 
00097       template<typename _GraphItem>
00098       struct Constraints {
00099         void constraints() {
00100           _GraphItem i1;
00101           _GraphItem i2 = i1;
00102           _GraphItem i3 = INVALID;
00103           
00104           i1 = i2 = i3;
00105 
00106           bool b;
00107           //      b = (ia == ib) && (ia != ib) && (ia < ib);
00108           b = (ia == ib) && (ia != ib);
00109           b = (ia == INVALID) && (ib != INVALID);
00110           //      b = (ia < ib);
00111         }
00112 
00113         const _GraphItem &ia;
00114         const _GraphItem &ib;
00115       };
00116     };
00117 
00119 
00122     typedef GraphItem<'n'> GraphNode;
00123 
00125 
00128     typedef GraphItem<'e'> GraphEdge;
00129 
00130 
00131     /**************** Basic features of graphs ****************/
00132 
00134   
00141 
00142     class BaseGraphComponent {
00143     public:
00144 
00145       typedef BaseGraphComponent Graph;
00146       
00148 
00151       typedef GraphItem<'n'> Node;
00152 
00154 
00157       typedef GraphItem<'e'> Edge;
00158 
00160 
00163       Node target(const Edge&) const { return INVALID;}
00164 
00166 
00169       Node source(const Edge&) const { return INVALID;}
00170 
00171 
00172       template <typename _Graph>
00173       struct Constraints {
00174         typedef typename _Graph::Node Node;
00175         typedef typename _Graph::Edge Edge;
00176       
00177         void constraints() {
00178           checkConcept<GraphItem<'n'>, Node>();
00179           checkConcept<GraphItem<'e'>, Edge>();
00180           {
00181             Node n;
00182             Edge e(INVALID);
00183             n = graph.source(e);
00184             n = graph.target(e);
00185           }      
00186         }
00187       
00188         const _Graph& graph;
00189       };
00190     };
00191 
00193   
00197 
00198     class BaseIterableGraphComponent : virtual public BaseGraphComponent {
00199     public:
00200 
00201       typedef BaseGraphComponent::Node Node;
00202       typedef BaseGraphComponent::Edge Edge;
00203 
00205       
00208       void first(Node&) const {}
00209 
00211       
00214       void next(Node&) const {}
00215 
00217       
00220       void first(Edge&) const {}
00222       
00225       void next(Edge&) const {}
00226 
00227 
00229       
00232       void firstIn(Edge&, const Node&) const {}
00233 
00235 
00236 
00239       void nextIn(Edge&) const {}
00240 
00242       
00245       void firstOut(Edge&, const Node&) const {}
00246 
00248       
00251       void nextOut(Edge&) const {}
00252 
00253 
00254       template <typename _Graph>
00255       struct Constraints {
00256       
00257         void constraints() {
00258           checkConcept< BaseGraphComponent, _Graph >();
00259           typename _Graph::Node node;      
00260           typename _Graph::Edge edge;
00261           {
00262             graph.first(node);
00263             graph.next(node);
00264           }
00265           {
00266             graph.first(edge);
00267             graph.next(edge);
00268           }
00269           {
00270             graph.firstIn(edge, node);
00271             graph.nextIn(edge);
00272           }
00273           {
00274             graph.firstOut(edge, node);
00275             graph.nextOut(edge);
00276           }
00277         }
00278 
00279         const _Graph& graph;
00280       };
00281     };
00282 
00284   
00289     class IDableGraphComponent : virtual public BaseGraphComponent {
00290     public:
00291 
00292       typedef BaseGraphComponent::Node Node;
00293       typedef BaseGraphComponent::Edge Edge;
00294 
00296 
00299       int id(const Node&) const { return -1;}
00300 
00306       Node fromId(int , Node) const { return INVALID;}
00307 
00312       int id(const Edge&) const { return -1;}
00313 
00319       Edge fromId(int, Edge) const { return INVALID;}
00320 
00321       template <typename _Graph>
00322       struct Constraints {
00323 
00324         void constraints() {
00325           checkConcept< BaseGraphComponent, _Graph >();
00326           typename _Graph::Node node;
00327           int nid = graph.id(node);
00328           nid = graph.id(node);
00329           node = graph.fromId(nid, Node());
00330           typename _Graph::Edge edge;
00331           int eid = graph.id(edge);
00332           eid = graph.id(edge);
00333           edge = graph.fromId(eid, Edge());
00334         }
00335 
00336         const _Graph& graph;
00337       };
00338     };
00339 
00340 
00342   
00347     class MaxIDableGraphComponent : virtual public BaseGraphComponent {
00348     public:
00349 
00351 
00354       int maxId(Node = INVALID) const { return -1;}
00355 
00357 
00360       int maxId(Edge = INVALID) const { return -1;}
00361 
00362       template <typename _Graph>
00363       struct Constraints {
00364 
00365         void constraints() {
00366           checkConcept<BaseGraphComponent, _Graph>();
00367           int nid = graph.maxId(typename _Graph::Node());
00368           ignore_unused_variable_warning(nid);
00369           int eid = graph.maxId(typename _Graph::Edge());
00370           ignore_unused_variable_warning(eid);
00371         }
00372       
00373         const _Graph& graph;
00374       };
00375     };
00376 
00378   
00382     class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
00383     public:
00384 
00385       typedef BaseGraphComponent::Node Node;
00386       typedef BaseGraphComponent::Edge Edge;
00387 
00389 
00392       Node addNode() {
00393         return INVALID;
00394       }
00395     
00397 
00400       Edge addEdge(const Node&, const Node&) {
00401         return INVALID;
00402       }
00403 
00404       template <typename _Graph>
00405       struct Constraints {
00406         void constraints() {
00407           checkConcept<BaseGraphComponent, _Graph >();
00408           typename _Graph::Node node_a, node_b;
00409           node_a = graph.addNode();
00410           node_b = graph.addNode();
00411           typename _Graph::Edge edge;
00412           edge = graph.addEdge(node_a, node_b);
00413         }
00414 
00415         _Graph& graph;
00416       };
00417     };
00418 
00420   
00424     class BaseErasableGraphComponent : virtual public BaseGraphComponent {
00425     public:
00426 
00427       typedef BaseGraphComponent::Node Node;
00428       typedef BaseGraphComponent::Edge Edge;
00429 
00431       
00434       void erase(const Node&) {}    
00435 
00437 
00440       void erase(const Edge&) {}
00441 
00442       template <typename _Graph>
00443       struct Constraints {
00444         void constraints() {
00445           checkConcept<BaseGraphComponent, _Graph>();
00446           typename _Graph::Node node;
00447           graph.erase(node);
00448           typename _Graph::Edge edge;
00449           graph.erase(edge);
00450         }
00451 
00452         _Graph& graph;
00453       };
00454     };
00455 
00457   
00461     class ClearableGraphComponent : virtual public BaseGraphComponent {
00462     public:
00463 
00465 
00468       void clear() {}    
00469 
00470       template <typename _Graph>
00471       struct Constraints {
00472         void constraints() {
00473           checkConcept<BaseGraphComponent, _Graph>();
00474           graph.clear();
00475         }
00476 
00477         _Graph graph;
00478       };
00479     };
00480 
00481 
00483 
00486     template <typename _Graph, typename _Item>
00487     class GraphIterator : public _Item {
00488     public:
00490 
00492       
00495       GraphIterator() {}
00497       
00500       GraphIterator(GraphIterator const&) {}
00502       
00505       explicit GraphIterator(const _Graph&) {}
00507 
00510       GraphIterator(Invalid) {}
00512 
00515       GraphIterator& operator=(GraphIterator const&) { return *this; }      
00517 
00520       GraphIterator& operator++() { return *this; }
00521       //        Node operator*() const { return INVALID; }
00523 
00526       bool operator==(const GraphIterator&) const { return true;}
00528         
00531       bool operator!=(const GraphIterator&) const { return true;}
00532       
00533       template<typename _GraphIterator>
00534       struct Constraints {
00535         void constraints() {
00536           //      checkConcept< Item, _GraphIterator >();
00537           _GraphIterator it1(g);
00538         
00540           //    _GraphIterator it2(bj);
00541           _GraphIterator it2;
00542 
00543           it2 = ++it1;
00544           ++it2 = it1;
00545           ++(++it1);
00547           _Item bi = it1;
00548           bi = it2;
00549         }
00550         _Graph& g;
00551       };
00552     };
00553 
00555 
00561     template <typename Graph,
00562               typename Edge = typename Graph::Edge,
00563               char _selector = '0'>
00564     class GraphIncIterator : public Edge {
00565     public:
00567       
00570       GraphIncIterator() {}
00572       
00575       GraphIncIterator(GraphIncIterator const& gi) :Edge(gi) {}
00578       
00582       explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {}
00584 
00587       GraphIncIterator(Invalid) {}
00589 
00592       GraphIncIterator& operator=(GraphIncIterator const&) { return *this; }      
00594 
00597       GraphIncIterator& operator++() { return *this; }
00598 
00599       //        Node operator*() const { return INVALID; }
00600 
00602 
00605       bool operator==(const GraphIncIterator&) const { return true;}
00606 
00608         
00611       bool operator!=(const GraphIncIterator&) const { return true;}
00612 
00613       template <typename _GraphIncIterator>
00614       struct Constraints {
00615         typedef typename Graph::Node Node;
00616         void constraints() {
00617           checkConcept<GraphItem<'e'>, _GraphIncIterator>();
00618           _GraphIncIterator it1(graph, node);
00620           //    _GraphIncIterator it2(edge);
00621           _GraphIncIterator it2;
00622 
00623           it2 = ++it1;
00624           ++it2 = it1;
00625           ++(++it1);
00626           Edge e = it1;
00627           e = it2;
00628 
00629           const_constraits();
00630         }
00631 
00632         void const_constraits() {
00633           Node n = graph.baseNode(it);
00634           n = graph.runningNode(it);
00635         }
00636 
00637         Edge edge;
00638         Node node;
00639         Graph graph;
00640         _GraphIncIterator it;
00641       };
00642     };
00643 
00644 
00646   
00650     class IterableGraphComponent : virtual public BaseGraphComponent {
00651 
00652     public:
00653     
00654       typedef IterableGraphComponent Graph;
00655 
00656       typedef BaseGraphComponent::Node Node;
00657       typedef BaseGraphComponent::Edge Edge;
00658 
00660 
00663       typedef GraphIterator<Graph, Node> NodeIt;
00665 
00668       typedef GraphIterator<Graph, Edge> EdgeIt;
00670 
00673       typedef GraphIncIterator<Graph, Edge, 'i'> InEdgeIt;
00675 
00678       typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt;
00679 
00684       Node baseNode(const InEdgeIt&) const { return INVALID; }
00685 
00690       Node runningNode(const InEdgeIt&) const { return INVALID; }
00691 
00696       Node baseNode(const OutEdgeIt&) const { return INVALID; }
00697 
00702       Node runningNode(const OutEdgeIt&) const { return INVALID; }
00703 
00708       Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
00709 
00710     
00711       template <typename _Graph> 
00712       struct Constraints {
00713         void constraints() {
00714           checkConcept< BaseGraphComponent, _Graph>();
00715           
00716           checkConcept<GraphIterator<_Graph, typename _Graph::Edge>,
00717             typename _Graph::EdgeIt >();
00718           checkConcept<GraphIterator<_Graph, typename _Graph::Node>,
00719             typename _Graph::NodeIt >();
00720           checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt>();
00721           checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt>();
00722 
00723           typename _Graph::Node n(INVALID);
00724           typename _Graph::Edge e(INVALID);
00725           n = graph.oppositeNode(n, e);
00726         }
00727         
00728         const _Graph& graph;
00729         
00730       };
00731     };
00732 
00734   
00740     class AlterableGraphComponent : virtual public BaseGraphComponent {
00741     public:
00742 
00744       typedef AlterationNotifier<Edge> EdgeNotifier;
00746       typedef AlterationNotifier<Node> NodeNotifier;
00747       
00751       EdgeNotifier getNotifier(Edge) const {
00752         return EdgeNotifier();
00753       }
00754       
00758       NodeNotifier getNotifier(Node) const {
00759         return NodeNotifier();
00760       }
00761       
00762     };
00763 
00764 
00766 
00770     template <typename Graph, typename Item, typename _Value>
00771     class GraphMap : public ReadWriteMap<Item, _Value> {
00772     protected:      
00773       GraphMap() {}
00774     public:
00778       explicit GraphMap(const Graph&) {}
00782       GraphMap(const Graph&, const _Value&) {}
00786       GraphMap(const GraphMap& gm) :ReadWriteMap<Item, _Value>(gm) {}
00787       
00791       GraphMap& operator=(const GraphMap&) { return *this;}
00792 
00793       template<typename _Map>
00794       struct Constraints {
00795         void constraints() {
00796           checkConcept<ReadWriteMap<Item, _Value>, _Map >();
00797           // Construction with a graph parameter
00798           _Map a(g);
00799           // Constructor with a graph and a default value parameter
00800           _Map a2(g,t);
00801           // Copy constructor. Do we need it?
00802           _Map b=c;
00803 
00804           ignore_unused_variable_warning(a2);
00805         }
00806 
00807         const _Map &c;
00808         const Graph &g;
00809         const typename GraphMap::Value &t;
00810       };
00811 
00812     };
00813 
00815   
00819     class MappableGraphComponent : virtual public BaseGraphComponent {
00820     public:
00821 
00822       typedef MappableGraphComponent Graph;
00823 
00824       typedef BaseGraphComponent::Node Node;
00825       typedef BaseGraphComponent::Edge Edge;
00826 
00828     
00831       template <typename _Value>
00832       class NodeMap : public GraphMap<Graph, Node, _Value> {
00833       private:
00834         NodeMap();
00835       public:
00840         explicit NodeMap(const Graph&) {}
00844         NodeMap(const Graph&, const _Value&) {}
00848         NodeMap(const NodeMap& nm) : GraphMap<Graph, Node, _Value>(nm) {}
00849 
00853         NodeMap& operator=(const NodeMap&) { return *this;}
00854 
00855       };
00856 
00858     
00861       template <typename _Value>
00862       class EdgeMap : public GraphMap<Graph, Edge, _Value> {
00863       private:
00864         EdgeMap();
00865       public:
00870         explicit EdgeMap(const Graph&) {}
00874         EdgeMap(const Graph&, const _Value&) {}
00878         EdgeMap(const EdgeMap& em) :GraphMap<Graph, Edge, _Value>(em) {}
00879 
00883         EdgeMap& operator=(const EdgeMap&) { return *this;}
00884 
00885       };
00886 
00887       template <typename _Graph>
00888       struct Constraints {
00889 
00890         struct Type {
00891           int value;
00892           Type() : value(0) {}
00893           Type(int _v) : value(_v) {}
00894         };
00895 
00896         void constraints() {
00897           checkConcept<BaseGraphComponent, _Graph>();
00898           { // int map test
00899             typedef typename _Graph::template NodeMap<int> IntNodeMap;
00900             checkConcept<GraphMap<_Graph, typename _Graph::Node, int>, 
00901               IntNodeMap >();
00902           } { // bool map test
00903             typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
00904             checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
00905               BoolNodeMap >();
00906           } { // Type map test
00907             typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
00908             checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>,
00909               TypeNodeMap >();
00910           } 
00911 
00912           { // int map test
00913             typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
00914             checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
00915               IntEdgeMap >();
00916           } { // bool map test
00917             typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
00918             checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
00919               BoolEdgeMap >();
00920           } { // Type map test
00921             typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
00922             checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>, 
00923               TypeEdgeMap >();
00924           } 
00925         }
00926 
00927         _Graph& graph;
00928       };
00929     };
00930 
00938     class ExtendableGraphComponent : virtual public BaseGraphComponent {
00939     public:
00940 
00941       typedef ExtendableGraphComponent Graph;
00942 
00943       typedef BaseGraphComponent::Node Node;
00944       typedef BaseGraphComponent::Edge Edge;
00945 
00949       Node addNode() {
00950         return INVALID;
00951       }
00952     
00956       Edge addEdge(const Node&, const Node&) {
00957         return INVALID;
00958       }
00959 
00960       template <typename _Graph>
00961       struct Constraints {
00962         void constraints() {
00963           checkConcept<BaseGraphComponent, _Graph >();
00964           typename _Graph::Node node_a, node_b;
00965           node_a = graph.addNode();
00966           node_b = graph.addNode();
00967           typename _Graph::Edge edge;
00968           edge = graph.addEdge(node_a, node_b);      
00969         }
00970         _Graph& graph;
00971       };
00972     };
00973 
00981     class ErasableGraphComponent : virtual public BaseGraphComponent {
00982     public:
00983 
00984       typedef ErasableGraphComponent Graph;
00985 
00986       typedef BaseGraphComponent::Node Node;
00987       typedef BaseGraphComponent::Edge Edge;
00988 
00992       void erase(const Node&) {}    
00993 
00997       void erase(const Edge&) {}
00998 
00999       template <typename _Graph>
01000       struct Constraints {
01001         void constraints() {
01002           checkConcept<BaseGraphComponent, _Graph >();
01003           typename _Graph::Node node;
01004           graph.erase(node);
01005           typename _Graph::Edge edge;
01006           graph.erase(edge);      
01007         }
01008 
01009         _Graph& graph;
01010       };
01011     };
01012 
01013   }
01014 
01015 }
01016 
01017 #endif

Generated on Fri Feb 3 18:36:02 2006 for LEMON by  doxygen 1.4.6