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

undir_graph.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * src/lemon/concept/undir_graph_component.h - Part of LEMON, a generic
00004  * C++ optimization library
00005  *
00006  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
00007  * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
00008  * EGRES).
00009  *
00010  * Permission to use, modify and distribute this software is granted
00011  * provided that this copyright notice appears in all copies. For
00012  * precise terms see the accompanying LICENSE file.
00013  *
00014  * This software is provided "AS IS" with no warranty of any kind,
00015  * express or implied, and with no claim as to its suitability for any
00016  * purpose.
00017  *
00018  */
00019 
00023 
00024 
00025 #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
00026 #define LEMON_CONCEPT_UNDIR_GRAPH_H
00027 
00028 #include <lemon/concept/graph_component.h>
00029 
00030 namespace lemon {
00031   namespace concept {
00032 
00035 
00036 
00039     template <typename UndirGraph>
00040     class UndirGraphEdge : public UndirGraph::UndirEdge {
00041       typedef typename UndirGraph::UndirEdge UndirEdge;
00042       typedef typename UndirGraph::Node Node;
00043     public:
00044 
00046       UndirGraphEdge() {}
00047 
00049       UndirGraphEdge(const UndirGraphEdge&) {}
00050 
00052       UndirGraphEdge(Invalid) {}
00053 
00059       UndirGraphEdge(const UndirGraph &g,
00060                      UndirEdge undir_edge, Node n) {
00061         ignore_unused_variable_warning(undir_edge);
00062         ignore_unused_variable_warning(g);
00063         ignore_unused_variable_warning(n);
00064       }
00065 
00067       UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
00068 
00070       bool operator==(UndirGraphEdge) const { return true; }
00072       bool operator!=(UndirGraphEdge) const { return false; }
00073 
00075       bool operator<(UndirGraphEdge) const { return false; }
00076 
00077       template <typename Edge>
00078       struct Constraints {
00079         void constraints() {
00080           const_constraints();
00081         }
00082         void const_constraints() const {
00084           UndirEdge ue = e;
00085           ue = e;
00086 
00087           Edge e_with_source(graph,ue,n);
00088           ignore_unused_variable_warning(e_with_source);
00089         }
00090         Edge e;
00091         UndirEdge ue;
00092         UndirGraph graph;
00093         Node n;
00094       };
00095     };
00096     
00097 
00098     struct BaseIterableUndirGraphConcept {
00099 
00100       template <typename Graph>
00101       struct Constraints {
00102 
00103         typedef typename Graph::UndirEdge UndirEdge;
00104         typedef typename Graph::Edge Edge;
00105         typedef typename Graph::Node Node;
00106 
00107         void constraints() {
00108           checkConcept<BaseIterableGraphComponent, Graph>();
00109           checkConcept<GraphItem<>, UndirEdge>();
00110           checkConcept<UndirGraphEdge<Graph>, Edge>();
00111 
00112           graph.first(ue);
00113           graph.next(ue);
00114 
00115           const_constraints();
00116         }
00117         void const_constraints() {
00118           Node n;
00119           n = graph.target(ue);
00120           n = graph.source(ue);
00121           n = graph.oppositeNode(n0, ue);
00122 
00123           bool b;
00124           b = graph.forward(e);
00125           ignore_unused_variable_warning(b);
00126         }
00127 
00128         Graph graph;
00129         Edge e;
00130         Node n0;
00131         UndirEdge ue;
00132       };
00133 
00134     };
00135 
00136 
00137     struct IterableUndirGraphConcept {
00138 
00139       template <typename Graph>
00140       struct Constraints {
00141         void constraints() {
00144           //checkConcept< BaseIterableUndirGraphConcept, Graph > ();
00145 
00146           checkConcept<IterableGraphComponent, Graph> ();
00147 
00148           typedef typename Graph::UndirEdge UndirEdge;
00149           typedef typename Graph::UndirEdgeIt UndirEdgeIt;
00150           typedef typename Graph::IncEdgeIt IncEdgeIt;
00151 
00152           checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
00153           checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
00154         }
00155       };
00156 
00157     };
00158 
00159     struct MappableUndirGraphConcept {
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 UndirEdgeMap<int> IntMap;
00174           checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,
00175             IntMap >();
00176 
00177           typedef typename Graph::template UndirEdgeMap<bool> BoolMap;
00178           checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,
00179             BoolMap >();
00180 
00181           typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;
00182           checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,
00183             DummyMap >();
00184         }
00185       };
00186 
00187     };
00188 
00189     struct ExtendableUndirGraphConcept {
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::UndirEdge uedge;
00199         Graph graph;
00200       };
00201 
00202     };
00203 
00204     struct ErasableUndirGraphConcept {
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::UndirEdge e;
00215       };
00216 
00217     };
00218 
00220 
00233 
00234     class UndirGraph {
00235     public:
00236 
00238       typedef GraphNode Node;
00239 
00241       typedef GraphItem<'u'> UndirEdge;
00242 
00244 #ifndef DOXYGEN
00245       typedef UndirGraphEdge<UndirGraph> Edge;
00246 #else
00247       typedef UndirGraphEdge Edge;
00248 #endif
00249 
00251 #ifndef DOXYGEN
00252       typedef GraphIterator<UndirGraph, Node> NodeIt;
00253 #else
00254       typedef GraphIterator NodeIt;
00255 #endif
00256 
00258 #ifndef DOXYGEN
00259       typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
00260 #else
00261       typedef GraphIterator UndirEdgeIt;
00262 #endif
00263 
00265 
00268 #ifndef DOXYGEN
00269       typedef GraphIterator<UndirGraph, Edge> EdgeIt;
00270 #else
00271       typedef GraphIterator EdgeIt;
00272 #endif
00273 
00274 
00276 #ifndef DOXYGEN
00277       typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
00278 #else
00279       typedef GraphIncIterator IncEdgeIt;
00280 #endif
00281 
00283 #ifndef DOXYGEN
00284       typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
00285 #else
00286       typedef GraphIncIterator InEdgeIt;
00287 #endif
00288 
00290 #ifndef DOXYGEN
00291       typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
00292 #else
00293       typedef GraphIncIterator OutEdgeIt;
00294 #endif
00295 
00297 #ifdef DOXYGEN
00298       typedef GraphMap NodeMap<T>;
00299 #endif
00300 
00302 #ifdef DOXYGEN
00303       typedef GraphMap UndirEdgeMap<T>;
00304 #endif
00305 
00307 #ifdef DOXYGEN
00308       typedef GraphMap EdgeMap<T>;
00309 #endif
00310 
00311       template <typename T>
00312       class NodeMap : public GraphMap<UndirGraph, Node, T> {
00313         typedef GraphMap<UndirGraph, Node, T> Parent;
00314       public:
00315 
00316         explicit NodeMap(const UndirGraph &g) : Parent(g) {}
00317         NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
00318       };
00319 
00320       template <typename T>
00321       class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
00322         typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
00323       public:
00324 
00325         explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
00326         UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
00327       };
00328 
00329       template <typename T>
00330       class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
00331         typedef GraphMap<UndirGraph, Edge, T> Parent;
00332       public:
00333 
00334         explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
00335         EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
00336       };
00337 
00339 
00344       bool forward(Edge) const { return true; }
00345 
00347 
00351       Node oppositeNode(Node, UndirEdge) const { return INVALID; }
00352 
00354 
00364       Node source(UndirEdge) const { return INVALID; }
00365 
00367       Node target(UndirEdge) const { return INVALID; }
00368 
00370       Node source(Edge) const { return INVALID; }
00371 
00373       Node target(Edge) const { return INVALID; }
00374 
00376 
00380       void first(Node&) const {}
00382 
00386       void next(Node&) const {}
00387 
00389 
00393       void first(UndirEdge&) const {}
00395 
00399       void next(UndirEdge&) const {}
00400 
00402 
00406       void first(Edge&) const {}
00408 
00412       void next(Edge&) const {}
00413 
00415 
00419       void firstOut(Edge&, Node) const {}
00421 
00425       void nextOut(Edge&) const {}
00426 
00428 
00432       void firstIn(Edge&, Node) const {}
00434 
00438       void nextIn(Edge&) const {}
00439 
00440 
00444       Node baseNode(OutEdgeIt e) const {
00445         return source(e);
00446       }
00451       Node runningNode(OutEdgeIt e) const {
00452         return target(e);
00453       }
00454 
00458       Node baseNode(InEdgeIt e) const {
00459         return target(e);
00460       }
00465       Node runningNode(InEdgeIt e) const {
00466         return source(e);
00467       }
00468 
00472       Node baseNode(IncEdgeIt e) const {
00473         return INVALID;
00474       }
00478       Node runningNode(IncEdgeIt e) const {
00479         return INVALID;
00480       }
00481 
00482 
00483       template <typename Graph>
00484       struct Constraints {
00485         void constraints() {
00486           checkConcept<BaseIterableUndirGraphConcept, Graph>();
00487           checkConcept<IterableUndirGraphConcept, Graph>();
00488           checkConcept<MappableUndirGraphConcept, Graph>();
00489         }
00490       };
00491 
00492     };
00493 
00494     class ExtendableUndirGraph : public UndirGraph {
00495     public:
00496 
00497       template <typename Graph>
00498       struct Constraints {
00499         void constraints() {
00500           checkConcept<BaseIterableUndirGraphConcept, Graph>();
00501           checkConcept<IterableUndirGraphConcept, Graph>();
00502           checkConcept<MappableUndirGraphConcept, Graph>();
00503 
00504           checkConcept<UndirGraph, Graph>();
00505           checkConcept<ExtendableUndirGraphConcept, Graph>();
00506           checkConcept<ClearableGraphComponent, Graph>();
00507         }
00508       };
00509 
00510     };
00511 
00512     class ErasableUndirGraph : public ExtendableUndirGraph {
00513     public:
00514 
00515       template <typename Graph>
00516       struct Constraints {
00517         void constraints() {
00518           checkConcept<ExtendableUndirGraph, Graph>();
00519           checkConcept<ErasableUndirGraphConcept, Graph>();
00520         }
00521       };
00522 
00523     };
00524 
00526 
00527   }
00528 
00529 }
00530 
00531 #endif

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