graph.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 
00019 #ifndef LEMON_CONCEPT_GRAPH_H
00020 #define LEMON_CONCEPT_GRAPH_H
00021 
00025 
00026 #include <lemon/invalid.h>
00027 #include <lemon/utility.h>
00028 #include <lemon/concept/maps.h>
00029 #include <lemon/concept_check.h>
00030 #include <lemon/concept/graph_component.h>
00031 
00032 namespace lemon {
00033   namespace concept {
00034 
00035     
00036     /**************** The full-featured graph concepts ****************/
00037 
00038 
00039     // \brief Modular static graph class.
00040     //     
00041     // It should be the same as the \c StaticGraph class.
00042     class _StaticGraph 
00043       :  virtual public BaseGraphComponent,
00044          public IterableGraphComponent, public MappableGraphComponent {
00045     public:
00046 
00047       typedef False UTag;
00048       
00049       typedef BaseGraphComponent::Node Node;
00050       typedef BaseGraphComponent::Edge Edge;
00051 
00052       template <typename _Graph>
00053       struct Constraints {
00054         void constraints() {
00055           checkConcept<IterableGraphComponent, _Graph>();
00056           checkConcept<MappableGraphComponent, _Graph>();
00057         }
00058       };
00059     };
00060 
00061     // \brief Modular extendable graph class.
00062     //     
00063     // It should be the same as the \c ExtendableGraph class.
00064     class _ExtendableGraph 
00065       :  virtual public BaseGraphComponent, public _StaticGraph,
00066          public ExtendableGraphComponent, public ClearableGraphComponent {
00067     public:
00068       typedef BaseGraphComponent::Node Node;
00069       typedef BaseGraphComponent::Edge Edge;
00070 
00071       template <typename _Graph>
00072       struct Constraints {
00073         void constraints() {
00074           checkConcept<_StaticGraph, _Graph >();
00075           checkConcept<ExtendableGraphComponent, _Graph >();
00076           checkConcept<ClearableGraphComponent, _Graph >();
00077         }
00078       };
00079     };
00080 
00081     // \brief Modular erasable graph class.
00082     //     
00083     // It should be the same as the \c ErasableGraph class.
00084     class _ErasableGraph 
00085       :  virtual public BaseGraphComponent, public _ExtendableGraph,
00086          public ErasableGraphComponent {
00087     public:
00088       typedef BaseGraphComponent::Node Node;
00089       typedef BaseGraphComponent::Edge Edge;
00090 
00091       template <typename _Graph>
00092       struct Constraints {
00093         void constraints() {
00094           checkConcept<_ExtendableGraph, _Graph >();
00095           checkConcept<ErasableGraphComponent, _Graph >();
00096         }
00097       };
00098     };
00099 
00102 
00104   
00121     class StaticGraph
00122     {
00123     public:
00125 
00128       typedef False UTag;
00129 
00131 
00134       StaticGraph() { }
00136 
00137 //       ///\todo It is not clear, what we expect from a copy constructor.
00138 //       ///E.g. How to assign the nodes/edges to each other? What about maps?
00139 //       StaticGraph(const StaticGraph& g) { }
00140 
00143 
00148       class Node {
00149       public:
00151 
00154         Node() { }
00156 
00159         Node(const Node&) { }
00160 
00162 
00165         Node(Invalid) { }
00167 
00170         bool operator==(Node) const { return true; }
00171 
00173         
00176         bool operator!=(Node) const { return true; }
00177 
00179         
00188         bool operator<(Node) const { return false; }
00189 
00190       };
00191     
00193 
00201       class NodeIt : public Node {
00202       public:
00204 
00207         NodeIt() { }
00209         
00212         NodeIt(const NodeIt& n) : Node(n) { }
00214 
00217         NodeIt(Invalid) { }
00219 
00222         NodeIt(const StaticGraph&) { }
00224 
00229         NodeIt(const StaticGraph&, const Node&) { }
00231 
00234         NodeIt& operator++() { return *this; }
00235       };
00236     
00237     
00239 
00242       class Edge {
00243       public:
00245 
00248         Edge() { }
00250 
00253         Edge(const Edge&) { }
00255 
00258         Edge(Invalid) { }
00260 
00263         bool operator==(Edge) const { return true; }
00265 
00268         bool operator!=(Edge) const { return true; }
00269 
00271         
00280         bool operator<(Edge) const { return false; }
00281       };
00282     
00284 
00294     
00295       class OutEdgeIt : public Edge {
00296       public:
00298 
00301         OutEdgeIt() { }
00303 
00306         OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }
00308 
00311         OutEdgeIt(Invalid) { }
00313     
00316         OutEdgeIt(const StaticGraph&, const Node&) { }
00318 
00322         OutEdgeIt(const StaticGraph&, const Edge&) { }
00324         
00327         OutEdgeIt& operator++() { return *this; }
00328       };
00329 
00331 
00341 
00342       class InEdgeIt : public Edge {
00343       public:
00345 
00348         InEdgeIt() { }
00350 
00353         InEdgeIt(const InEdgeIt& e) : Edge(e) { }
00355 
00358         InEdgeIt(Invalid) { }
00360     
00363         InEdgeIt(const StaticGraph&, const Node&) { }
00365 
00369         InEdgeIt(const StaticGraph&, const Edge&) { }
00371 
00374         InEdgeIt& operator++() { return *this; }
00375       };
00377 
00385       class EdgeIt : public Edge {
00386       public:
00388 
00391         EdgeIt() { }
00393 
00396         EdgeIt(const EdgeIt& e) : Edge(e) { }
00398 
00401         EdgeIt(Invalid) { }
00403     
00406         EdgeIt(const StaticGraph& g) { ignore_unused_variable_warning(g); }
00408 
00412         EdgeIt(const StaticGraph&, const Edge&) { } 
00414         
00416         EdgeIt& operator++() { return *this; }
00417       };
00419 
00422       Node target(Edge) const { return INVALID; }
00424 
00427       Node source(Edge) const { return INVALID; }
00428 
00429 //       /// Gives back the first Node in the iterating order.
00430       
00431 //       /// Gives back the first Node in the iterating order.
00432 //       ///     
00433       void first(Node&) const {}
00434 
00435 //       /// Gives back the next Node in the iterating order.
00436       
00437 //       /// Gives back the next Node in the iterating order.
00438 //       ///     
00439       void next(Node&) const {}
00440 
00441 //       /// Gives back the first Edge in the iterating order.
00442       
00443 //       /// Gives back the first Edge in the iterating order.
00444 //       ///     
00445       void first(Edge&) const {}
00446 //       /// Gives back the next Edge in the iterating order.
00447       
00448 //       /// Gives back the next Edge in the iterating order.
00449 //       ///     
00450       void next(Edge&) const {}
00451 
00452 
00453 //       /// Gives back the first of the Edges point to the given Node.
00454       
00455 //       /// Gives back the first of the Edges point to the given Node.
00456 //       ///     
00457       void firstIn(Edge&, const Node&) const {}
00458 
00459 //       /// Gives back the next of the Edges points to the given Node.
00460 
00461 
00462 //       /// Gives back the next of the Edges points to the given Node.
00463 //       ///
00464       void nextIn(Edge&) const {}
00465 
00466 //       /// Gives back the first of the Edges start from the given Node.
00467       
00468 //       /// Gives back the first of the Edges start from the given Node.
00469 //       ///     
00470       void firstOut(Edge&, const Node&) const {}
00471 
00472 //       /// Gives back the next of the Edges start from the given Node.
00473       
00474 //       /// Gives back the next of the Edges start from the given Node.
00475 //       ///     
00476       void nextOut(Edge&) const {}
00477 
00482       Node baseNode(const InEdgeIt&) const { return INVALID; }
00483 
00488       Node runningNode(const InEdgeIt&) const { return INVALID; }
00489 
00494       Node baseNode(const OutEdgeIt&) const { return INVALID; }
00495 
00500       Node runningNode(const OutEdgeIt&) const { return INVALID; }
00501 
00505       Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
00506 
00514       template<class T> 
00515       class NodeMap : public ReadWriteMap< Node, T >
00516       {
00517       public:
00518 
00520         NodeMap(const StaticGraph&) { }
00522         NodeMap(const StaticGraph&, T) { }
00523 
00525         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
00527         NodeMap& operator=(const NodeMap&) { return *this; }
00528         // \todo fix this concept
00529       };
00530 
00538       template<class T> 
00539       class EdgeMap : public ReadWriteMap<Edge,T>
00540       {
00541       public:
00542 
00544         EdgeMap(const StaticGraph&) { }
00546         EdgeMap(const StaticGraph&, T) { }
00548         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
00550         EdgeMap& operator=(const EdgeMap&) { return *this; }
00551         // \todo fix this concept    
00552       };
00553 
00554       template <typename _Graph>
00555       struct Constraints : public _StaticGraph::Constraints<_Graph> {};
00556 
00557     };
00558 
00560     
00563     class ExtendableGraph : public StaticGraph
00564     {
00565     public:
00567 
00570       ExtendableGraph() { }
00572 
00575       Node addNode() { return INVALID; }
00577 
00581       Edge addEdge(Node, Node) { return INVALID; }
00582     
00584 
00588       void clear() { }
00589 
00590       template <typename _Graph>
00591       struct Constraints : public _ExtendableGraph::Constraints<_Graph> {};
00592 
00593     };
00594 
00596   
00599     class ErasableGraph : public ExtendableGraph
00600     {
00601     public:
00603 
00606       ErasableGraph() { }
00608 
00611       void erase(Node) { }
00613 
00616       void erase(Edge) { }
00617 
00618       template <typename _Graph>
00619       struct Constraints : public _ErasableGraph::Constraints<_Graph> {};
00620 
00621     };
00622     
00623     // @}
00624   } //namespace concept  
00625 } //namespace lemon
00626 
00627 
00628 
00629 #endif // LEMON_CONCEPT_GRAPH_H

Generated on Fri Feb 3 18:35:56 2006 for LEMON by  doxygen 1.4.6