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

graph.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/concept/graph.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 
00017 #ifndef LEMON_CONCEPT_GRAPH_H
00018 #define LEMON_CONCEPT_GRAPH_H
00019 
00023 
00024 #include <lemon/invalid.h>
00025 #include <lemon/concept/maps.h>
00026 #include <lemon/concept_check.h>
00027 #include <lemon/concept/graph_component.h>
00028 
00029 namespace lemon {
00030   namespace concept {
00031 
00032     
00035 
00036     /**************** The full-featured graph concepts ****************/
00037 
00038 
00042     class _StaticGraph 
00043       :  virtual public BaseGraphComponent,
00044          public IterableGraphComponent, public MappableGraphComponent {
00045     public:
00046       typedef BaseGraphComponent::Node Node;
00047       typedef BaseGraphComponent::Edge Edge;
00048 
00049       template <typename _Graph>
00050       struct Constraints {
00051         void constraints() {
00052           checkConcept<IterableGraphComponent, _Graph>();
00053           checkConcept<MappableGraphComponent, _Graph>();
00054         }
00055       };
00056     };
00057 
00061     class _ExtendableGraph 
00062       :  virtual public BaseGraphComponent, public _StaticGraph,
00063          public ExtendableGraphComponent, public ClearableGraphComponent {
00064     public:
00065       typedef BaseGraphComponent::Node Node;
00066       typedef BaseGraphComponent::Edge Edge;
00067 
00068       template <typename _Graph>
00069       struct Constraints {
00070         void constraints() {
00071           checkConcept<_StaticGraph, _Graph >();
00072           checkConcept<ExtendableGraphComponent, _Graph >();
00073           checkConcept<ClearableGraphComponent, _Graph >();
00074         }
00075       };
00076     };
00077 
00081     class _ErasableGraph 
00082       :  virtual public BaseGraphComponent, public _ExtendableGraph,
00083          public ErasableGraphComponent {
00084     public:
00085       typedef BaseGraphComponent::Node Node;
00086       typedef BaseGraphComponent::Edge Edge;
00087 
00088       template <typename _Graph>
00089       struct Constraints {
00090         void constraints() {
00091           checkConcept<_ExtendableGraph, _Graph >();
00092           checkConcept<ErasableGraphComponent, _Graph >();
00093         }
00094       };
00095     };
00096 
00098   
00115     class StaticGraph
00116     {
00117     public:
00119 
00122       StaticGraph() { }
00124 
00125 //       ///\todo It is not clear, what we expect from a copy constructor.
00126 //       ///E.g. How to assign the nodes/edges to each other? What about maps?
00127 //       StaticGraph(const StaticGraph& g) { }
00128 
00131 
00136       class Node {
00137       public:
00139 
00142         Node() { }
00144 
00147         Node(const Node&) { }
00148 
00150 
00153         Node(Invalid) { }
00155 
00158         bool operator==(Node) const { return true; }
00159 
00161         
00164         bool operator!=(Node) const { return true; }
00165 
00166       };
00167     
00169 
00177       class NodeIt : public Node {
00178       public:
00180 
00183         NodeIt() { }
00185         
00188         NodeIt(const NodeIt&) { }
00190 
00193         NodeIt(Invalid) { }
00195 
00198         NodeIt(const StaticGraph& g) { }
00200 
00205         NodeIt(const StaticGraph& g, const Node& n) { }
00207 
00210         NodeIt& operator++() { return *this; }
00211       };
00212     
00213     
00215 
00218       class Edge {
00219       public:
00221 
00224         Edge() { }
00226 
00229         Edge(const Edge&) { }
00231 
00234         Edge(Invalid) { }
00236 
00239         bool operator==(Edge) const { return true; }
00241 
00244         bool operator!=(Edge) const { return true; }
00245       };
00246     
00248 
00258     
00259       class OutEdgeIt : public Edge {
00260       public:
00262 
00265         OutEdgeIt() { }
00267 
00270         OutEdgeIt(const OutEdgeIt&) { }
00272 
00275         OutEdgeIt(Invalid) { }
00277     
00282         OutEdgeIt(const StaticGraph& g, const Node& n) { }
00284 
00288         OutEdgeIt(const StaticGraph& g, const Edge& e) { }
00290         
00293         OutEdgeIt& operator++() { return *this; }
00294       };
00295 
00297 
00307 
00308       class InEdgeIt : public Edge {
00309       public:
00311 
00314         InEdgeIt() { }
00316 
00319         InEdgeIt(const InEdgeIt&) { }
00321 
00324         InEdgeIt(Invalid) { }
00326     
00331         InEdgeIt(const StaticGraph& g, const Node& n) { }
00333 
00337         InEdgeIt(const StaticGraph& g, const Edge& n) { }
00339 
00342         InEdgeIt& operator++() { return *this; }
00343       };
00345 
00353       class EdgeIt : public Edge {
00354       public:
00356 
00359         EdgeIt() { }
00361 
00364         EdgeIt(const EdgeIt&) { }
00366 
00369         EdgeIt(Invalid) { }
00371     
00375         EdgeIt(const StaticGraph& g) { }
00377 
00381         EdgeIt(const StaticGraph&, const Edge&) { } 
00383         
00386         EdgeIt& operator++() { return *this; }
00387       };
00389 
00392       Node target(Edge) const { return INVALID; }
00394 
00397       Node source(Edge) const { return INVALID; }
00399 
00405       template<class T> 
00406       class NodeMap : public ReadWriteMap< Node, T >
00407       {
00408       public:
00409 
00411         NodeMap(const StaticGraph&) { }
00413         NodeMap(const StaticGraph&, T) { }
00414 
00416         NodeMap(const NodeMap&) { }
00418         NodeMap& operator=(const NodeMap&) { return *this; }
00419         // \todo fix this concept
00420       };
00421 
00423 
00429       template<class T> 
00430       class EdgeMap : public ReadWriteMap<Edge,T>
00431       {
00432       public:
00433 
00435         EdgeMap(const StaticGraph&) { }
00437         EdgeMap(const StaticGraph&, T) { }
00439         EdgeMap(const EdgeMap&) { }
00441         EdgeMap& operator=(const EdgeMap&) { return *this; }
00442         // \todo fix this concept    
00443       };
00444 
00445       template <typename _Graph>
00446       struct Constraints : public _StaticGraph::Constraints<_Graph> {};
00447 
00448     };
00449 
00451     
00455     class ExtendableGraph : public StaticGraph
00456     {
00457     public:
00459 
00462       ExtendableGraph() { }
00464 
00467       Node addNode() { return INVALID; }
00469 
00473       Edge addEdge(Node s, Node t) { return INVALID; }
00474     
00476 
00480       void clear() { }
00481 
00482       template <typename _Graph>
00483       struct Constraints : public _ExtendableGraph::Constraints<_Graph> {};
00484 
00485     };
00486 
00488   
00491     class ErasableGraph : public ExtendableGraph
00492     {
00493     public:
00495 
00498       ErasableGraph() { }
00500 
00503       void erase(Node n) { }
00505 
00508       void erase(Edge e) { }
00509 
00510       template <typename _Graph>
00511       struct Constraints : public _ErasableGraph::Constraints<_Graph> {};
00512 
00513     };
00514 
00515     
00516     /************* New GraphBase stuff **************/
00517 
00518 
00519 //     /// A minimal GraphBase concept
00520 
00521 //     /// This class describes a minimal concept which can be extended to a
00522 //     /// full-featured graph with \ref GraphFactory.
00523 //     class GraphBase {
00524 //     public:
00525 
00526 //       GraphBase() {}
00527 
00528 //       /// \bug Should we demand that Node and Edge be subclasses of the
00529 //       /// Graph class???
00530 
00531 //       typedef GraphItem<'n'> Node;
00532 //       typedef GraphItem<'e'> Edge;
00533 
00534 // //       class Node : public BaseGraphItem<'n'> {};
00535 // //       class Edge : public BaseGraphItem<'e'> {};
00536 
00537 //       // Graph operation
00538 //       void firstNode(Node &n) const { }
00539 //       void firstEdge(Edge &e) const { }
00540 
00541 //       void firstOutEdge(Edge &e, Node) const { }
00542 //       void firstInEdge(Edge &e, Node) const { }
00543 
00544 //       void nextNode(Node &n) const { }
00545 //       void nextEdge(Edge &e) const { }
00546 
00547 
00548 //       // Question: isn't it reasonable if this methods have a Node
00549 //       // parameter? Like this:
00550 //       // Edge& nextOut(Edge &e, Node) const { return e; }
00551 //       void nextOutEdge(Edge &e) const { }
00552 //       void nextInEdge(Edge &e) const { }
00553 
00554 //       Node target(Edge) const { return Node(); }
00555 //       Node source(Edge) const { return Node(); }
00556       
00557 
00558 //       // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
00559 //       // concept?
00560 
00561 
00562 //       // Maps.
00563 //       //
00564 //       // We need a special slimer concept which does not provide maps (it
00565 //       // wouldn't be strictly slimer, cause for map-factory id() & friends
00566 //       // a required...)
00567 
00568 //       template<typename T>
00569 //       class NodeMap : public GraphMap<GraphBase, Node, T> {};
00570 
00571 //       template<typename T>
00572 //       class EdgeMap : public GraphMap<GraphBase, Node, T> {};
00573 //     };
00574 
00575     // @}
00576   } //namespace concept  
00577 } //namespace lemon
00578 
00579 
00580 
00581 #endif // LEMON_CONCEPT_GRAPH_H

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