ugraph.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_UGRAPH_H
00025 #define LEMON_CONCEPT_UGRAPH_H
00026 
00027 #include <lemon/concept/graph_component.h>
00028 #include <lemon/concept/graph.h>
00029 #include <lemon/utility.h>
00030 
00031 namespace lemon {
00032   namespace concept {
00033 
00034 //     /// Skeleton class which describes an edge with direction in \ref
00035 //     /// UGraph "undirected graph".
00036     template <typename UGraph>
00037     class UGraphEdge : public UGraph::UEdge {
00038       typedef typename UGraph::UEdge UEdge;
00039       typedef typename UGraph::Node Node;
00040     public:
00041 
00043       UGraphEdge() {}
00044 
00046       UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
00047 
00049       UGraphEdge(Invalid) {}
00050 
00056       UGraphEdge(const UGraph &g,
00057                      UEdge u_edge, Node n) {
00058         ignore_unused_variable_warning(u_edge);
00059         ignore_unused_variable_warning(g);
00060         ignore_unused_variable_warning(n);
00061       }
00062 
00064       UGraphEdge& operator=(UGraphEdge) { return *this; }
00065 
00067       bool operator==(UGraphEdge) const { return true; }
00069       bool operator!=(UGraphEdge) const { return false; }
00070 
00072       bool operator<(UGraphEdge) const { return false; }
00073 
00074       template <typename Edge>
00075       struct Constraints {
00076         void constraints() {
00077           const_constraints();
00078         }
00079         void const_constraints() const {
00081           UEdge ue = e;
00082           ue = e;
00083 
00084           Edge e_with_source(graph,ue,n);
00085           ignore_unused_variable_warning(e_with_source);
00086         }
00087         Edge e;
00088         UEdge ue;
00089         UGraph graph;
00090         Node n;
00091       };
00092     };
00093     
00094 
00095     struct BaseIterableUGraphConcept {
00096 
00097       template <typename Graph>
00098       struct Constraints {
00099 
00100         typedef typename Graph::UEdge UEdge;
00101         typedef typename Graph::Edge Edge;
00102         typedef typename Graph::Node Node;
00103 
00104         void constraints() {
00105           checkConcept<BaseIterableGraphComponent, Graph>();
00106           checkConcept<GraphItem<>, UEdge>();
00107           //checkConcept<UGraphEdge<Graph>, Edge>();
00108 
00109           graph.first(ue);
00110           graph.next(ue);
00111 
00112           const_constraints();
00113         }
00114         void const_constraints() {
00115           Node n;
00116           n = graph.target(ue);
00117           n = graph.source(ue);
00118           n = graph.oppositeNode(n0, ue);
00119 
00120           bool b;
00121           b = graph.direction(e);
00122           Edge e = graph.direct(UEdge(), true);
00123           e = graph.direct(UEdge(), n);
00124  
00125           ignore_unused_variable_warning(b);
00126         }
00127 
00128         Graph graph;
00129         Edge e;
00130         Node n0;
00131         UEdge ue;
00132       };
00133 
00134     };
00135 
00136 
00137     struct IterableUGraphConcept {
00138 
00139       template <typename Graph>
00140       struct Constraints {
00141         void constraints() {
00144           //checkConcept< BaseIterableUGraphConcept, Graph > ();
00145 
00146           checkConcept<IterableGraphComponent, Graph> ();
00147 
00148           typedef typename Graph::UEdge UEdge;
00149           typedef typename Graph::UEdgeIt UEdgeIt;
00150           typedef typename Graph::IncEdgeIt IncEdgeIt;
00151 
00152           checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
00153           checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
00154         }
00155       };
00156 
00157     };
00158 
00159     struct MappableUGraphConcept {
00160 
00161       template <typename Graph>
00162       struct Constraints {
00163 
00164         struct Dummy {
00165           int value;
00166           Dummy() : value(0) {}
00167           Dummy(int _v) : value(_v) {}
00168         };
00169 
00170         void constraints() {
00171           checkConcept<MappableGraphComponent, Graph>();
00172 
00173           typedef typename Graph::template UEdgeMap<int> IntMap;
00174           checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
00175             IntMap >();
00176 
00177           typedef typename Graph::template UEdgeMap<bool> BoolMap;
00178           checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
00179             BoolMap >();
00180 
00181           typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
00182           checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
00183             DummyMap >();
00184         }
00185       };
00186 
00187     };
00188 
00189     struct ExtendableUGraphConcept {
00190 
00191       template <typename Graph>
00192       struct Constraints {
00193         void constraints() {
00194           node_a = graph.addNode();
00195           uedge = graph.addEdge(node_a, node_b);
00196         }
00197         typename Graph::Node node_a, node_b;
00198         typename Graph::UEdge uedge;
00199         Graph graph;
00200       };
00201 
00202     };
00203 
00204     struct ErasableUGraphConcept {
00205 
00206       template <typename Graph>
00207       struct Constraints {
00208         void constraints() {
00209           graph.erase(n);
00210           graph.erase(e);
00211         }
00212         Graph graph;
00213         typename Graph::Node n;
00214         typename Graph::UEdge e;
00215       };
00216 
00217     };
00218 
00221 
00222 
00224 
00241 
00242     class UGraph {
00243     public:
00245 
00248       typedef True UTag;
00249 
00257       class Node {
00258       public:
00260 
00263         Node() { }
00265 
00268         Node(const Node&) { }
00269 
00271 
00274         Node(Invalid) { }
00276 
00279         bool operator==(Node) const { return true; }
00280 
00282         
00285         bool operator!=(Node) const { return true; }
00286 
00288         
00297         bool operator<(Node) const { return false; }
00298 
00299       };
00300     
00302 
00310       class NodeIt : public Node {
00311       public:
00313 
00316         NodeIt() { }
00318         
00321         NodeIt(const NodeIt& n) : Node(n) { }
00323 
00326         NodeIt(Invalid) { }
00328 
00331         NodeIt(const UGraph&) { }
00333 
00338         NodeIt(const UGraph&, const Node&) { }
00340 
00343         NodeIt& operator++() { return *this; }
00344       };
00345     
00346     
00348 
00351       class UEdge {
00352       public:
00354 
00357         UEdge() { }
00359 
00362         UEdge(const UEdge&) { }
00364 
00367         UEdge(Invalid) { }
00369 
00372         bool operator==(UEdge) const { return true; }
00374 
00377         bool operator!=(UEdge) const { return true; }
00378 
00380         
00389         bool operator<(UEdge) const { return false; }
00390       };
00391 
00393 
00401       class UEdgeIt : public UEdge {
00402       public:
00404 
00407         UEdgeIt() { }
00409 
00412         UEdgeIt(const UEdgeIt& e) : UEdge(e) { }
00414 
00417         UEdgeIt(Invalid) { }
00419     
00421         UEdgeIt(const UGraph&) { }
00423 
00428         UEdgeIt(const UGraph&, const UEdge&) { } 
00430         
00432         UEdgeIt& operator++() { return *this; }
00433       };
00434 
00449       class IncEdgeIt : public UEdge {
00450       public:
00452 
00455         IncEdgeIt() { }
00457 
00460         IncEdgeIt(const IncEdgeIt& e) : UEdge(e) { }
00462 
00465         IncEdgeIt(Invalid) { }
00467     
00470         IncEdgeIt(const UGraph&, const Node&) { }
00472 
00476         IncEdgeIt(const UGraph&, const UEdge&) { }
00478 
00481         IncEdgeIt& operator++() { return *this; }
00482       };
00483 
00485 
00488       class Edge : public UEdge {
00489       public:
00491 
00494         Edge() { }
00496 
00499         Edge(const Edge& e) : UEdge(e) { }
00501 
00504         Edge(Invalid) { }
00506 
00509         bool operator==(Edge) const { return true; }
00511 
00514         bool operator!=(Edge) const { return true; }
00515 
00517         
00526         bool operator<(Edge) const { return false; }
00527         
00528       }; 
00530 
00538       class EdgeIt : public Edge {
00539       public:
00541 
00544         EdgeIt() { }
00546 
00549         EdgeIt(const EdgeIt& e) : Edge(e) { }
00551 
00554         EdgeIt(Invalid) { }
00556     
00559         EdgeIt(const UGraph &g) { ignore_unused_variable_warning(g); }
00561 
00565         EdgeIt(const UGraph&, const Edge&) { } 
00567         
00569         EdgeIt& operator++() { return *this; }
00570       };
00571    
00573 
00583     
00584       class OutEdgeIt : public Edge {
00585       public:
00587 
00590         OutEdgeIt() { }
00592 
00595         OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }
00597 
00600         OutEdgeIt(Invalid) { }
00602     
00607         OutEdgeIt(const UGraph& n, const Node& g) {
00608           ignore_unused_variable_warning(n);
00609           ignore_unused_variable_warning(g);
00610         }
00612 
00616         OutEdgeIt(const UGraph&, const Edge&) { }
00618         
00621         OutEdgeIt& operator++() { return *this; }
00622       };
00623 
00625 
00635 
00636       class InEdgeIt : public Edge {
00637       public:
00639 
00642         InEdgeIt() { }
00644 
00647         InEdgeIt(const InEdgeIt& e) : Edge(e) { }
00649 
00652         InEdgeIt(Invalid) { }
00654     
00659         InEdgeIt(const UGraph& g, const Node& n) { 
00660           ignore_unused_variable_warning(n);
00661           ignore_unused_variable_warning(g);
00662         }
00664 
00668         InEdgeIt(const UGraph&, const Edge&) { }
00670 
00673         InEdgeIt& operator++() { return *this; }
00674       };
00675 
00683       template<class T> 
00684       class NodeMap : public ReadWriteMap< Node, T >
00685       {
00686       public:
00687 
00689         NodeMap(const UGraph&) { }
00691         NodeMap(const UGraph&, T) { }
00692 
00694         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
00696         NodeMap& operator=(const NodeMap&) { return *this; }
00697         // \todo fix this concept
00698       };
00699 
00707       template<class T> 
00708       class EdgeMap : public ReadWriteMap<Edge,T>
00709       {
00710       public:
00711 
00713         EdgeMap(const UGraph&) { }
00715         EdgeMap(const UGraph&, T) { }
00717         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
00719         EdgeMap& operator=(const EdgeMap&) { return *this; }
00720         // \todo fix this concept    
00721       };
00722 
00724 
00730       template<class T> 
00731       class UEdgeMap : public ReadWriteMap<UEdge,T>
00732       {
00733       public:
00734 
00736         UEdgeMap(const UGraph&) { }
00738         UEdgeMap(const UGraph&, T) { }
00740         UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
00742         UEdgeMap &operator=(const UEdgeMap&) { return *this; }
00743         // \todo fix this concept    
00744       };
00745 
00750       Edge direct(const UEdge&, const Node&) const {
00751         return INVALID;
00752       }
00753 
00759       Edge direct(const UEdge&, bool) const {
00760         return INVALID;
00761       }
00762 
00767       bool direction(Edge) const { return true; }
00768 
00772       Edge oppositeEdge(Edge) const { return INVALID; }
00773 
00777       Node oppositeNode(Node, UEdge) const { return INVALID; }
00778 
00790       Node source(UEdge) const { return INVALID; }
00791 
00793       Node target(UEdge) const { return INVALID; }
00794 
00796       Node source(Edge) const { return INVALID; }
00797 
00799       Node target(Edge) const { return INVALID; }
00800 
00801 //       /// \brief First node of the graph
00802 //       ///
00803 //       /// \note This method is part of so called \ref
00804 //       /// developpers_interface "Developpers' interface", so it shouldn't
00805 //       /// be used in an end-user program.
00806       void first(Node&) const {}
00807 //       /// \brief Next node of the graph
00808 //       ///
00809 //       /// \note This method is part of so called \ref
00810 //       /// developpers_interface "Developpers' interface", so it shouldn't
00811 //       /// be used in an end-user program.
00812       void next(Node&) const {}
00813 
00814 //       /// \brief First undirected edge of the graph
00815 //       ///
00816 //       /// \note This method is part of so called \ref
00817 //       /// developpers_interface "Developpers' interface", so it shouldn't
00818 //       /// be used in an end-user program.
00819       void first(UEdge&) const {}
00820 //       /// \brief Next undirected edge of the graph
00821 //       ///
00822 //       /// \note This method is part of so called \ref
00823 //       /// developpers_interface "Developpers' interface", so it shouldn't
00824 //       /// be used in an end-user program.
00825       void next(UEdge&) const {}
00826 
00827 //       /// \brief First directed edge of the graph
00828 //       ///
00829 //       /// \note This method is part of so called \ref
00830 //       /// developpers_interface "Developpers' interface", so it shouldn't
00831 //       /// be used in an end-user program.
00832       void first(Edge&) const {}
00833 //       /// \brief Next directed edge of the graph
00834 //       ///
00835 //       /// \note This method is part of so called \ref
00836 //       /// developpers_interface "Developpers' interface", so it shouldn't
00837 //       /// be used in an end-user program.
00838       void next(Edge&) const {}
00839 
00840 //       /// \brief First outgoing edge from a given node
00841 //       ///
00842 //       /// \note This method is part of so called \ref
00843 //       /// developpers_interface "Developpers' interface", so it shouldn't
00844 //       /// be used in an end-user program.
00845       void firstOut(Edge&, Node) const {}
00846 //       /// \brief Next outgoing edge to a node
00847 //       ///
00848 //       /// \note This method is part of so called \ref
00849 //       /// developpers_interface "Developpers' interface", so it shouldn't
00850 //       /// be used in an end-user program.
00851       void nextOut(Edge&) const {}
00852 
00853 //       /// \brief First incoming edge to a given node
00854 //       ///
00855 //       /// \note This method is part of so called \ref
00856 //       /// developpers_interface "Developpers' interface", so it shouldn't
00857 //       /// be used in an end-user program.
00858       void firstIn(Edge&, Node) const {}
00859 //       /// \brief Next incoming edge to a node
00860 //       ///
00861 //       /// \note This method is part of so called \ref
00862 //       /// developpers_interface "Developpers' interface", so it shouldn't
00863 //       /// be used in an end-user program.
00864       void nextIn(Edge&) const {}
00865 
00866 
00870       Node baseNode(OutEdgeIt e) const {
00871         return source(e);
00872       }
00877       Node runningNode(OutEdgeIt e) const {
00878         return target(e);
00879       }
00880 
00884       Node baseNode(InEdgeIt e) const {
00885         return target(e);
00886       }
00891       Node runningNode(InEdgeIt e) const {
00892         return source(e);
00893       }
00894 
00898       Node baseNode(IncEdgeIt) const {
00899         return INVALID;
00900       }
00901       
00905       Node runningNode(IncEdgeIt) const {
00906         return INVALID;
00907       }
00908 
00909       template <typename Graph>
00910       struct Constraints {
00911         void constraints() {
00912           checkConcept<BaseIterableUGraphConcept, Graph>();
00913           checkConcept<IterableUGraphConcept, Graph>();
00914           checkConcept<MappableUGraphConcept, Graph>();
00915         }
00916       };
00917 
00918     };
00919 
00924     class ExtendableUGraph : public UGraph {
00925     public:
00926       
00931       Node addNode();
00932 
00937       UEdge addEdge(const Node& from, const Node& to);
00938 
00943       void clear() { }
00944 
00945       template <typename Graph>
00946       struct Constraints {
00947         void constraints() {
00948           checkConcept<BaseIterableUGraphConcept, Graph>();
00949           checkConcept<IterableUGraphConcept, Graph>();
00950           checkConcept<MappableUGraphConcept, Graph>();
00951 
00952           checkConcept<UGraph, Graph>();
00953           checkConcept<ExtendableUGraphConcept, Graph>();
00954           checkConcept<ClearableGraphComponent, Graph>();
00955         }
00956       };
00957 
00958     };
00959 
00964     class ErasableUGraph : public ExtendableUGraph {
00965     public:
00966 
00971       void erase(Node) { }
00976       void erase(UEdge) { }
00977 
00978       template <typename Graph>
00979       struct Constraints {
00980         void constraints() {
00981           checkConcept<ExtendableUGraph, Graph>();
00982           checkConcept<ErasableUGraphConcept, Graph>();
00983         }
00984       };
00985 
00986     };
00987 
00989 
00990   }
00991 
00992 }
00993 
00994 #endif

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