Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

graph_component.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/concept/graph_component.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
00014  *
00015  */
00016 
00020 
00021 
00022 #ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H
00023 #define LEMON_CONCEPT_GRAPH_COMPONENT_H
00024 
00025 #include <lemon/invalid.h>
00026 #include <lemon/concept/maps.h>
00027 
00028 #include <lemon/alteration_notifier.h>
00029 
00030 namespace lemon {
00031   namespace concept {
00032 
00035 
00036     /****************   Graph iterator concepts   ****************/
00037 
00039 
00048 
00049 #ifndef DOXYGEN
00050     template <char _selector = '0'>
00051 #endif
00052     class GraphItem {
00053     public:
00055       
00059       GraphItem() {}
00061       
00064       GraphItem(GraphItem const&) {}
00066 
00069       GraphItem(Invalid) {}
00071 
00074       GraphItem& operator=(GraphItem const&) { return *this; }
00076       
00079       bool operator==(GraphItem) const { return false; }
00081         
00084       bool operator!=(GraphItem) const { return false; }
00085 
00087 
00096       bool operator<(GraphItem) const { return false; }
00097 
00098       template<typename _GraphItem>
00099       struct Constraints {
00100         void constraints() {
00101           _GraphItem i1;
00102           _GraphItem i2 = i1;
00103           _GraphItem i3 = INVALID;
00104           
00105           i1 = i2 = i3;
00106 
00107           bool b;
00108           //      b = (ia == ib) && (ia != ib) && (ia < ib);
00109           b = (ia == ib) && (ia != ib);
00110           b = (ia == INVALID) && (ib != INVALID);
00111           //      b = (ia < ib);
00112         }
00113 
00114         const _GraphItem &ia;
00115         const _GraphItem &ib;
00116       };
00117     };
00118 
00120 
00123     typedef GraphItem<'n'> GraphNode;
00124 
00126 
00129     typedef GraphItem<'e'> GraphEdge;
00130 
00131 
00132     /**************** Basic features of graphs ****************/
00133 
00135   
00142 
00143     class BaseGraphComponent {
00144     public:
00145 
00146       typedef BaseGraphComponent Graph;
00147       
00149 
00152       typedef GraphItem<'n'> Node;
00153 
00155 
00158       typedef GraphItem<'e'> Edge;
00159 
00161 
00164       Node target(const Edge&) const { return INVALID;}
00165 
00167 
00170       Node source(const Edge&) const { return INVALID;}
00171 
00172 
00173       template <typename _Graph>
00174       struct Constraints {
00175         typedef typename _Graph::Node Node;
00176         typedef typename _Graph::Edge Edge;
00177       
00178         void constraints() {
00179           checkConcept<GraphItem<'n'>, Node>();
00180           checkConcept<GraphItem<'e'>, Edge>();
00181           {
00182             Node n;
00183             Edge e;
00184             n = graph.source(e);
00185             n = graph.target(e);
00186           }      
00187         }
00188       
00189         const _Graph& graph;
00190       };
00191     };
00192 
00194   
00198 
00199     class BaseIterableGraphComponent : virtual public BaseGraphComponent {
00200     public:
00201 
00202       typedef BaseGraphComponent::Node Node;
00203       typedef BaseGraphComponent::Edge Edge;
00204 
00206       
00209       void first(Node&) const {}
00210 
00212       
00215       void next(Node&) const {}
00216 
00218       
00221       void first(Edge&) const {}
00223       
00226       void next(Edge&) const {}
00227 
00228 
00230       
00233       void firstIn(Edge&, const Node&) const {}
00234 
00236 
00237 
00240       void nextIn(Edge&) const {}
00241 
00243       
00246       void firstOut(Edge&, const Node&) const {}
00247 
00249       
00252       void nextOut(Edge&) const {}
00253 
00254 
00255       template <typename _Graph>
00256       struct Constraints {
00257       
00258         void constraints() {
00259           checkConcept< BaseGraphComponent, _Graph >();
00260           typename _Graph::Node node;      
00261           typename _Graph::Edge edge;
00262           {
00263             graph.first(node);
00264             graph.next(node);
00265           }
00266           {
00267             graph.first(edge);
00268             graph.next(edge);
00269           }
00270           {
00271             graph.firstIn(edge, node);
00272             graph.nextIn(edge);
00273           }
00274           {
00275             graph.firstOut(edge, node);
00276             graph.nextOut(edge);
00277           }
00278         }
00279 
00280         const _Graph& graph;
00281       };
00282     };
00283 
00285   
00290     class IDableGraphComponent : virtual public BaseGraphComponent {
00291     public:
00292 
00293       typedef BaseGraphComponent::Node Node;
00294       typedef BaseGraphComponent::Edge Edge;
00295 
00297 
00300       int id(const Node&) const { return -1;}
00301 
00307       Node fromId(int id, Node) const { return INVALID;}
00308 
00313       int id(const Edge&) const { return -1;}
00314 
00320       Edge fromId(int id, Edge) const { return INVALID;}
00321 
00322       template <typename _Graph>
00323       struct Constraints {
00324 
00325         void constraints() {
00326           checkConcept< BaseGraphComponent, _Graph >();
00327           typename _Graph::Node node;
00328           int nid = graph.id(node);
00329           nid = graph.id(node);
00330           node = graph.fromId(nid, Node());
00331           typename _Graph::Edge edge;
00332           int eid = graph.id(edge);
00333           eid = graph.id(edge);
00334           edge = graph.fromId(eid, Edge());
00335         }
00336 
00337         const _Graph& graph;
00338       };
00339     };
00340 
00341 
00343   
00348     class MaxIDableGraphComponent : virtual public BaseGraphComponent {
00349     public:
00350 
00352 
00355       int maxId(Node = INVALID) const { return -1;}
00356 
00358 
00361       int maxId(Edge = INVALID) const { return -1;}
00362 
00363       template <typename _Graph>
00364       struct Constraints {
00365 
00366         void constraints() {
00367           checkConcept<BaseGraphComponent, _Graph>();
00368           int nid = graph.maxId(typename _Graph::Node());
00369           ignore_unused_variable_warning(nid);
00370           int eid = graph.maxId(typename _Graph::Edge());
00371           ignore_unused_variable_warning(eid);
00372         }
00373       
00374         const _Graph& graph;
00375       };
00376     };
00377 
00379   
00383     class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
00384     public:
00385 
00386       typedef BaseGraphComponent::Node Node;
00387       typedef BaseGraphComponent::Edge Edge;
00388 
00390 
00393       Node addNode() {
00394         return INVALID;
00395       }
00396     
00398 
00401       Edge addEdge(const Node& from, const Node& to) {
00402         return INVALID;
00403       }
00404 
00405       template <typename _Graph>
00406       struct Constraints {
00407         void constraints() {
00408           checkConcept<BaseGraphComponent, _Graph >();
00409           typename _Graph::Node node_a, node_b;
00410           node_a = 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&) {}
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     };
00680     
00681     template <typename _Graph> 
00682     struct Constraints {
00683       void constraints() {
00684         checkConcept< BaseGraphComponent, _Graph>();
00685 
00686         checkConcept<GraphIterator<_Graph, typename _Graph::Edge>,
00687           typename _Graph::EdgeIt >();
00688         checkConcept<GraphIterator<_Graph, typename _Graph::Node>,
00689           typename _Graph::NodeIt >();
00690         checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt >();
00691         checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >();
00692       }
00693     };
00694 
00696   
00702     class AlterableGraphComponent : virtual public BaseGraphComponent {
00703     public:
00704 
00706       typedef AlterationNotifier<Edge> EdgeNotifier;
00708       typedef AlterationNotifier<Node> NodeNotifier;
00709       
00713       EdgeNotifier getNotifier(Edge) const {
00714         return EdgeNotifier();
00715       }
00716       
00720       NodeNotifier getNotifier(Node) const {
00721         return NodeNotifier();
00722       }
00723       
00724     };
00725 
00726 
00728 
00732     template <typename Graph, typename Item, typename _Value>
00733     class GraphMap : public ReadWriteMap<Item, _Value> {
00734     protected:      
00735       GraphMap() {}
00736     public:
00740       explicit GraphMap(const Graph&) {}
00744       GraphMap(const Graph&, const _Value&) {}
00748       GraphMap(const GraphMap&) {}
00749       
00753       GraphMap& operator=(const GraphMap&) { return *this;}
00754 
00755       template<typename _Map>
00756       struct Constraints {
00757         void constraints() {
00758           checkConcept<ReadWriteMap<Item, _Value>, _Map >();
00759           // Construction with a graph parameter
00760           _Map a(g);
00761           // Constructor with a graph and a default value parameter
00762           _Map a2(g,t);
00763           // Copy constructor. Do we need it?
00764           _Map b=c;
00765           // Copy operator. Do we need it?
00766           a=b;
00767 
00768           ignore_unused_variable_warning(a2);
00769         }
00770 
00771         const _Map &c;
00772         const Graph &g;
00773         const typename GraphMap::Value &t;
00774       };
00775 
00776     };
00777 
00779   
00783     class MappableGraphComponent : virtual public BaseGraphComponent {
00784     public:
00785 
00786       typedef MappableGraphComponent Graph;
00787 
00788       typedef BaseGraphComponent::Node Node;
00789       typedef BaseGraphComponent::Edge Edge;
00790 
00792     
00795       template <typename _Value>
00796       class NodeMap : public GraphMap<Graph, Node, _Value> {
00797       private:
00798         NodeMap();
00799       public:
00804         explicit NodeMap(const Graph&) {}
00808         NodeMap(const Graph&, const _Value&) {}
00812         NodeMap(const NodeMap&) {}
00813 
00817         NodeMap& operator=(const NodeMap&) { return *this;}
00818 
00819       };
00820 
00822     
00825       template <typename _Value>
00826       class EdgeMap : public GraphMap<Graph, Edge, _Value> {
00827       private:
00828         EdgeMap();
00829       public:
00834         explicit EdgeMap(const Graph&) {}
00838         EdgeMap(const Graph&, const _Value&) {}
00842         EdgeMap(const EdgeMap&) {}
00843 
00847         EdgeMap& operator=(const EdgeMap&) { return *this;}
00848 
00849       };
00850 
00851       template <typename _Graph>
00852       struct Constraints {
00853 
00854         struct Type {
00855           int value;
00856           Type() : value(0) {}
00857           Type(int _v) : value(_v) {}
00858         };
00859 
00860         void constraints() {
00861           checkConcept<BaseGraphComponent, _Graph>();
00862           { // int map test
00863             typedef typename _Graph::template NodeMap<int> IntNodeMap;
00864             checkConcept<GraphMap<_Graph, typename _Graph::Node, int>, 
00865               IntNodeMap >();
00866           } { // bool map test
00867             typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
00868             checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
00869               BoolNodeMap >();
00870           } { // Type map test
00871             typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
00872             checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>,
00873               TypeNodeMap >();
00874           } 
00875 
00876           { // int map test
00877             typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
00878             checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
00879               IntEdgeMap >();
00880           } { // bool map test
00881             typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
00882             checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
00883               BoolEdgeMap >();
00884           } { // Type map test
00885             typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
00886             checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>, 
00887               TypeEdgeMap >();
00888           } 
00889         }
00890 
00891         _Graph& graph;
00892       };
00893     };
00894 
00902     class ExtendableGraphComponent : virtual public BaseGraphComponent {
00903     public:
00904 
00905       typedef ExtendableGraphComponent Graph;
00906 
00907       typedef BaseGraphComponent::Node Node;
00908       typedef BaseGraphComponent::Edge Edge;
00909 
00913       Node addNode() {
00914         return INVALID;
00915       }
00916     
00920       Edge addEdge(const Node& from, const Node& to) {
00921         return INVALID;
00922       }
00923 
00924       template <typename _Graph>
00925       struct Constraints {
00926         void constraints() {
00927           checkConcept<BaseGraphComponent, _Graph >();
00928           typename _Graph::Node node_a, node_b;
00929           node_a = graph.addNode();
00930           typename _Graph::Edge edge;
00931           edge = graph.addEdge(node_a, node_b);      
00932         }
00933         _Graph& graph;
00934       };
00935     };
00936 
00944     class ErasableGraphComponent : virtual public BaseGraphComponent {
00945     public:
00946 
00947       typedef ErasableGraphComponent Graph;
00948 
00949       typedef BaseGraphComponent::Node Node;
00950       typedef BaseGraphComponent::Edge Edge;
00951 
00955       void erase(const Node&) {}    
00956 
00960       void erase(const Edge&) {}
00961 
00962       template <typename _Graph>
00963       struct Constraints {
00964         void constraints() {
00965           checkConcept<BaseGraphComponent, _Graph >();
00966           typename _Graph::Node node;
00967           graph.erase(node);
00968           typename _Graph::Edge edge;
00969           graph.erase(edge);      
00970         }
00971 
00972         _Graph& graph;
00973       };
00974     };
00975 
00977 
00978   }
00979 
00980 }
00981 
00982 #endif

Generated on Mon Feb 21 15:02:20 2005 for LEMON by  doxygen 1.4.1