COIN-OR::LEMON - Graph Library

Changeset 2111:ea1fa1bc3f6d in lemon-0.x for lemon/concept


Ignore:
Timestamp:
06/28/06 17:06:24 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2817
Message:

Removing concepts for extendable and erasable graphs
Renaming StaticGraph? to Graph

Location:
lemon/concept
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/concept/bpugraph.h

    r1993 r2111  
    948948    };
    949949
    950     /// \brief An empty non-static undirected graph class.
    951     ///   
    952     /// This class provides everything that \ref BpUGraph does.
    953     /// Additionally it enables building graphs from scratch.
    954     class ExtendableBpUGraph : public BpUGraph {
    955     public:
    956      
    957       /// \brief Add a new ANode to the graph.
    958       ///
    959       /// Add a new ANode to the graph.
    960       /// \return the new node.
    961       Node addANode();
    962 
    963       /// \brief Add a new ANode to the graph.
    964       ///
    965       /// Add a new ANode to the graph.
    966       /// \return the new node.
    967       Node addBNode();
    968 
    969       /// \brief Add a new undirected edge to the graph.
    970       ///
    971       /// Add a new undirected edge to the graph. One of the nodes
    972       /// should be ANode and the other should be BNode.
    973       /// \pre The nodes are not in the same nodeset.
    974       /// \return the new edge.
    975       UEdge addEdge(const Node& from, const Node& to);
    976 
    977       /// \brief Resets the graph.
    978       ///
    979       /// This function deletes all undirected edges and nodes of the graph.
    980       /// It also frees the memory allocated to store them.
    981       void clear() { }
    982 
    983       template <typename Graph>
    984       struct Constraints {
    985         void constraints() {}
    986       };
    987 
    988     };
    989 
    990     /// \brief An empty erasable undirected graph class.
    991     ///
    992     /// This class is an extension of \ref ExtendableBpUGraph. It makes it
    993     /// possible to erase undirected edges or nodes.
    994     class ErasableBpUGraph : public ExtendableBpUGraph {
    995     public:
    996 
    997       /// \brief Deletes a node.
    998       ///
    999       /// Deletes a node.
    1000       ///
    1001       void erase(Node) { }
    1002       /// \brief Deletes an undirected edge.
    1003       ///
    1004       /// Deletes an undirected edge.
    1005       ///
    1006       void erase(UEdge) { }
    1007 
    1008       template <typename Graph>
    1009       struct Constraints {
    1010         void constraints() {}
    1011       };
    1012 
    1013     };
    1014950
    1015951    /// @}
  • lemon/concept/graph.h

    r2090 r2111  
    3939    // \brief Modular static graph class.
    4040    //     
    41     // It should be the same as the \c StaticGraph class.
    42     class _StaticGraph
     41    // It should be the same as the \c Graph class.
     42    class _Graph
    4343      :  virtual public BaseGraphComponent,
    4444         public IterableGraphComponent, public MappableGraphComponent {
     
    5757    };
    5858
    59     // \brief Modular extendable graph class.
    60     //     
    61     // It should be the same as the \c ExtendableGraph class.
    62     class _ExtendableGraph
    63       :  virtual public BaseGraphComponent, public _StaticGraph,
    64          public ExtendableGraphComponent, public ClearableGraphComponent {
    65     public:
    66       typedef BaseGraphComponent::Node Node;
    67       typedef BaseGraphComponent::Edge Edge;
    68 
    69       template <typename _Graph>
    70       struct Constraints {
    71         void constraints() {
    72           checkConcept<_StaticGraph, _Graph >();
    73           checkConcept<ExtendableGraphComponent, _Graph >();
    74           checkConcept<ClearableGraphComponent, _Graph >();
    75         }
    76       };
    77     };
    78 
    79     // \brief Modular erasable graph class.
    80     //     
    81     // It should be the same as the \c ErasableGraph class.
    82     class _ErasableGraph
    83       :  virtual public BaseGraphComponent, public _ExtendableGraph,
    84          public ErasableGraphComponent {
    85     public:
    86       typedef BaseGraphComponent::Node Node;
    87       typedef BaseGraphComponent::Edge Edge;
    88 
    89       template <typename _Graph>
    90       struct Constraints {
    91         void constraints() {
    92           checkConcept<_ExtendableGraph, _Graph >();
    93           checkConcept<ErasableGraphComponent, _Graph >();
    94         }
    95       };
    96     };
    97 
    9859    /// \addtogroup graph_concepts
    9960    /// @{
    10061
    101     /// An empty static graph class.
     62    /// An empty graph class.
    10263 
    10364    /// This class provides all the common features of a graph structure,
     
    11778    /// \todo A pages describing the concept of concept description would
    11879    /// be nice.
    119     class StaticGraph
    120     {
    121 //      ///Copy consructor.
    122 
    123 //       ///\todo It is not clear, what we expect from a copy constructor.
    124 //       ///E.g. How to assign the nodes/edges to each other? What about maps?
    125 //       StaticGraph(const StaticGraph& g) { }
     80    class Graph {
    12681    public:
    12782      ///\e
     
    13186      /// Defalult constructor.
    13287      ///
    133       StaticGraph() { }
     88      Graph() { }
    13489
    13590      /// The base type of node iterators,
     
    214169        /// Sets the iterator to the first node of \c g.
    215170        ///
    216         NodeIt(const StaticGraph&) { }
     171        NodeIt(const Graph&) { }
    217172        /// Node -> NodeIt conversion.
    218173
     
    221176        /// This feature necessitates that each time we
    222177        /// iterate the edge-set, the iteration order is the same.
    223         NodeIt(const StaticGraph&, const Node&) { }
     178        NodeIt(const Graph&, const Node&) { }
    224179        /// Next node.
    225180
     
    308263        /// This constructor sets the iterator to the first outgoing edge of
    309264        /// the node.
    310         OutEdgeIt(const StaticGraph&, const Node&) { }
     265        OutEdgeIt(const Graph&, const Node&) { }
    311266        /// Edge -> OutEdgeIt conversion
    312267
     
    314269        /// This feature necessitates that each time we
    315270        /// iterate the edge-set, the iteration order is the same.
    316         OutEdgeIt(const StaticGraph&, const Edge&) { }
     271        OutEdgeIt(const Graph&, const Edge&) { }
    317272        ///Next outgoing edge
    318273       
     
    355310        /// This constructor set the iterator to the first incoming edge of
    356311        /// the node.
    357         InEdgeIt(const StaticGraph&, const Node&) { }
     312        InEdgeIt(const Graph&, const Node&) { }
    358313        /// Edge -> InEdgeIt conversion
    359314
     
    361316        /// This feature necessitates that each time we
    362317        /// iterate the edge-set, the iteration order is the same.
    363         InEdgeIt(const StaticGraph&, const Edge&) { }
     318        InEdgeIt(const Graph&, const Edge&) { }
    364319        /// Next incoming edge
    365320
     
    398353        /// This constructor sets the iterator to the first edge of \c g.
    399354        ///@param g the graph
    400         EdgeIt(const StaticGraph& g) { ignore_unused_variable_warning(g); }
     355        EdgeIt(const Graph& g) { ignore_unused_variable_warning(g); }
    401356        /// Edge -> EdgeIt conversion
    402357
     
    404359        /// This feature necessitates that each time we
    405360        /// iterate the edge-set, the iteration order is the same.
    406         EdgeIt(const StaticGraph&, const Edge&) { }
     361        EdgeIt(const Graph&, const Edge&) { }
    407362        ///Next edge
    408363       
     
    421376      Node source(Edge) const { return INVALID; }
    422377
    423 //       /// Gives back the first Node in the iterating order.
    424      
    425 //       /// Gives back the first Node in the iterating order.
    426 //       ///     
    427378      void first(Node&) const {}
    428 
    429 //       /// Gives back the next Node in the iterating order.
    430      
    431 //       /// Gives back the next Node in the iterating order.
    432 //       ///     
    433379      void next(Node&) const {}
    434380
    435 //       /// Gives back the first Edge in the iterating order.
    436      
    437 //       /// Gives back the first Edge in the iterating order.
    438 //       ///     
    439381      void first(Edge&) const {}
    440 //       /// Gives back the next Edge in the iterating order.
    441      
    442 //       /// Gives back the next Edge in the iterating order.
    443 //       ///     
    444382      void next(Edge&) const {}
    445383
    446384
    447 //       /// Gives back the first of the Edges point to the given Node.
    448      
    449 //       /// Gives back the first of the Edges point to the given Node.
    450 //       ///     
    451385      void firstIn(Edge&, const Node&) const {}
    452 
    453 //       /// Gives back the next of the Edges points to the given Node.
    454 
    455 
    456 //       /// Gives back the next of the Edges points to the given Node.
    457 //       ///
    458386      void nextIn(Edge&) const {}
    459387
    460 //       /// Gives back the first of the Edges start from the given Node.
    461      
    462 //       /// Gives back the first of the Edges start from the given Node.
    463 //       ///     
    464388      void firstOut(Edge&, const Node&) const {}
    465 
    466 //       /// Gives back the next of the Edges start from the given Node.
    467      
    468 //       /// Gives back the next of the Edges start from the given Node.
    469 //       ///     
    470389      void nextOut(Edge&) const {}
    471390
     
    512431
    513432        ///\e
    514         NodeMap(const StaticGraph&) { }
     433        NodeMap(const Graph&) { }
    515434        ///\e
    516         NodeMap(const StaticGraph&, T) { }
     435        NodeMap(const Graph&, T) { }
    517436
    518437        ///Copy constructor
     
    536455
    537456        ///\e
    538         EdgeMap(const StaticGraph&) { }
     457        EdgeMap(const Graph&) { }
    539458        ///\e
    540         EdgeMap(const StaticGraph&, T) { }
     459        EdgeMap(const Graph&, T) { }
    541460        ///Copy constructor
    542461        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
     
    546465      };
    547466
    548       template <typename _Graph>
    549       struct Constraints : public _StaticGraph::Constraints<_Graph> {};
    550 
    551     };
    552 
    553     /// An empty non-static graph class.
    554    
    555     /// This class provides everything that \ref StaticGraph does.
    556     /// Additionally it enables building graphs from scratch.
    557     class ExtendableGraph : public StaticGraph
    558     {
    559     public:
    560       /// Defalult constructor.
    561 
    562       /// Defalult constructor.
    563       ///
    564       ExtendableGraph() { }
    565       ///Add a new node to the graph.
    566 
    567       /// \return the new node.
    568       ///
    569       Node addNode() { return INVALID; }
    570       ///Add a new edge to the graph.
    571 
    572       ///Add a new edge to the graph with source node \c s
    573       ///and target node \c t.
    574       ///\return the new edge.
    575       Edge addEdge(Node, Node) { return INVALID; }
    576    
    577       /// Resets the graph.
    578 
    579       /// This function deletes all edges and nodes of the graph.
    580       /// It also frees the memory allocated to store them.
    581       /// \todo It might belong to \ref ErasableGraph.
    582       void clear() { }
    583 
    584       template <typename _Graph>
    585       struct Constraints : public _ExtendableGraph::Constraints<_Graph> {};
    586 
    587     };
    588 
    589     /// An empty erasable graph class.
    590  
    591     /// This class is an extension of \ref ExtendableGraph. It makes it
    592     /// possible to erase edges or nodes.
    593     class ErasableGraph : public ExtendableGraph
    594     {
    595     public:
    596       /// Defalult constructor.
    597 
    598       /// Defalult constructor.
    599       ///
    600       ErasableGraph() { }
    601       /// Deletes a node.
    602 
    603       /// Deletes node \c n node.
    604       ///
    605       void erase(Node) { }
    606       /// Deletes an edge.
    607 
    608       /// Deletes edge \c e edge.
    609       ///
    610       void erase(Edge) { }
    611 
    612       template <typename _Graph>
    613       struct Constraints : public _ErasableGraph::Constraints<_Graph> {};
     467      template <typename RGraph>
     468      struct Constraints : public _Graph::Constraints<RGraph> {};
    614469
    615470    };
  • lemon/concept/graph_component.h

    r1999 r2111  
    459459    /// core clear functions for the graph structure.
    460460    /// The most of the base graphs should be conform to this concept.
    461     class ClearableGraphComponent : virtual public BaseGraphComponent {
     461    class BaseClearableGraphComponent : virtual public BaseGraphComponent {
    462462    public:
    463463
     
    647647    /// This class provides beside the core graph features
    648648    /// iterator based iterable interface for the graph structure.
    649     /// This concept is part of the StaticGraphConcept.
     649    /// This concept is part of the GraphConcept.
    650650    class IterableGraphComponent : virtual public BaseGraphComponent {
    651651
     
    818818    /// This class provides beside the core graph features
    819819    /// map interface for the graph structure.
    820     /// This concept is part of the StaticGraphConcept.
     820    /// This concept is part of the GraphConcept.
    821821    class MappableGraphComponent : virtual public BaseGraphComponent {
    822822    public:
     
    931931    };
    932932
    933     /// \brief An empty extendable extended graph class.
    934     ///
    935     /// This class provides beside the core graph features
    936     /// item addition interface for the graph structure.
    937     /// The difference between this class and the
    938     /// \c BaseExtendableGraphComponent is that it should
    939     /// notify the item alteration observers.
    940     class ExtendableGraphComponent : virtual public BaseGraphComponent {
    941     public:
    942 
    943       typedef ExtendableGraphComponent Graph;
    944 
    945       typedef BaseGraphComponent::Node Node;
    946       typedef BaseGraphComponent::Edge Edge;
    947 
    948       /// \brief Add a node to the graph.
    949       ///
    950       /// Add a node to the graph and notify the observers.
    951       Node addNode() {
    952         return INVALID;
     933
     934//     /// Skeleton class which describes an edge with direction in \ref
     935//     /// UGraph "undirected graph".
     936    template <typename UGraph>
     937    class UGraphEdge : public UGraph::UEdge {
     938      typedef typename UGraph::UEdge UEdge;
     939      typedef typename UGraph::Node Node;
     940    public:
     941
     942      /// \e
     943      UGraphEdge() {}
     944
     945      /// \e
     946      UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
     947
     948      /// \e
     949      UGraphEdge(Invalid) {}
     950
     951      /// \brief Directed edge from undirected edge and a source node.
     952      ///
     953      /// Constructs a directed edge from undirected edge and a source node.
     954      ///
     955      /// \note You have to specify the graph for this constructor.
     956      UGraphEdge(const UGraph &g,
     957                     UEdge u_edge, Node n) {
     958        ignore_unused_variable_warning(u_edge);
     959        ignore_unused_variable_warning(g);
     960        ignore_unused_variable_warning(n);
    953961      }
     962
     963      /// \e
     964      UGraphEdge& operator=(UGraphEdge) { return *this; }
     965
     966      /// \e
     967      bool operator==(UGraphEdge) const { return true; }
     968      /// \e
     969      bool operator!=(UGraphEdge) const { return false; }
     970
     971      /// \e
     972      bool operator<(UGraphEdge) const { return false; }
     973
     974      template <typename Edge>
     975      struct Constraints {
     976        void constraints() {
     977          const_constraints();
     978        }
     979        void const_constraints() const {
     980          /// \bug This should be is_base_and_derived ...
     981          UEdge ue = e;
     982          ue = e;
     983
     984          Edge e_with_source(graph,ue,n);
     985          ignore_unused_variable_warning(e_with_source);
     986        }
     987        Edge e;
     988        UEdge ue;
     989        UGraph graph;
     990        Node n;
     991      };
     992    };
    954993   
    955       /// \brief Add an edge to the graph.
    956       ///
    957       /// Add an edge to the graph and notify the observers.
    958       Edge addEdge(const Node&, const Node&) {
    959         return INVALID;
    960       }
    961 
    962       template <typename _Graph>
    963       struct Constraints {
    964         void constraints() {
    965           checkConcept<BaseGraphComponent, _Graph >();
    966           typename _Graph::Node node_a, node_b;
    967           node_a = graph.addNode();
    968           node_b = graph.addNode();
    969           typename _Graph::Edge edge;
    970           edge = graph.addEdge(node_a, node_b);     
    971         }
    972         _Graph& graph;
    973       };
    974     };
    975 
    976     /// \brief An empty erasable extended graph class.
    977     ///
    978     /// This class provides beside the core graph features
    979     /// item erase interface for the graph structure.
    980     /// The difference between this class and the
    981     /// \c BaseErasableGraphComponent is that it should
    982     /// notify the item alteration observers.
    983     class ErasableGraphComponent : virtual public BaseGraphComponent {
    984     public:
    985 
    986       typedef ErasableGraphComponent Graph;
    987 
    988       typedef BaseGraphComponent::Node Node;
    989       typedef BaseGraphComponent::Edge Edge;
    990 
    991       /// \brief Erase the Node and notify the node alteration observers.
    992       ///
    993       ///  Erase the Node and notify the node alteration observers.
    994       void erase(const Node&) {}   
    995 
    996       /// \brief Erase the Edge and notify the edge alteration observers.
    997       ///
    998       ///  Erase the Edge and notify the edge alteration observers.
    999       void erase(const Edge&) {}
    1000 
    1001       template <typename _Graph>
    1002       struct Constraints {
    1003         void constraints() {
    1004           checkConcept<BaseGraphComponent, _Graph >();
    1005           typename _Graph::Node node;
    1006           graph.erase(node);
    1007           typename _Graph::Edge edge;
    1008           graph.erase(edge);     
    1009         }
    1010 
    1011         _Graph& graph;
    1012       };
     994
     995    struct BaseIterableUGraphConcept {
     996
     997      template <typename Graph>
     998      struct Constraints {
     999
     1000        typedef typename Graph::UEdge UEdge;
     1001        typedef typename Graph::Edge Edge;
     1002        typedef typename Graph::Node Node;
     1003
     1004        void constraints() {
     1005          checkConcept<BaseIterableGraphComponent, Graph>();
     1006          checkConcept<GraphItem<>, UEdge>();
     1007          //checkConcept<UGraphEdge<Graph>, Edge>();
     1008
     1009          graph.first(ue);
     1010          graph.next(ue);
     1011
     1012          const_constraints();
     1013        }
     1014        void const_constraints() {
     1015          Node n;
     1016          n = graph.target(ue);
     1017          n = graph.source(ue);
     1018          n = graph.oppositeNode(n0, ue);
     1019
     1020          bool b;
     1021          b = graph.direction(e);
     1022          Edge e = graph.direct(UEdge(), true);
     1023          e = graph.direct(UEdge(), n);
     1024 
     1025          ignore_unused_variable_warning(b);
     1026        }
     1027
     1028        Graph graph;
     1029        Edge e;
     1030        Node n0;
     1031        UEdge ue;
     1032      };
     1033
     1034    };
     1035
     1036
     1037    struct IterableUGraphConcept {
     1038
     1039      template <typename Graph>
     1040      struct Constraints {
     1041        void constraints() {
     1042          /// \todo we don't need the iterable component to be base iterable
     1043          /// Don't we really???
     1044          //checkConcept< BaseIterableUGraphConcept, Graph > ();
     1045
     1046          checkConcept<IterableGraphComponent, Graph> ();
     1047
     1048          typedef typename Graph::UEdge UEdge;
     1049          typedef typename Graph::UEdgeIt UEdgeIt;
     1050          typedef typename Graph::IncEdgeIt IncEdgeIt;
     1051
     1052          checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
     1053          checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
     1054        }
     1055      };
     1056
     1057    };
     1058
     1059    struct MappableUGraphConcept {
     1060
     1061      template <typename Graph>
     1062      struct Constraints {
     1063
     1064        struct Dummy {
     1065          int value;
     1066          Dummy() : value(0) {}
     1067          Dummy(int _v) : value(_v) {}
     1068        };
     1069
     1070        void constraints() {
     1071          checkConcept<MappableGraphComponent, Graph>();
     1072
     1073          typedef typename Graph::template UEdgeMap<int> IntMap;
     1074          checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
     1075            IntMap >();
     1076
     1077          typedef typename Graph::template UEdgeMap<bool> BoolMap;
     1078          checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
     1079            BoolMap >();
     1080
     1081          typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
     1082          checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
     1083            DummyMap >();
     1084        }
     1085      };
     1086
    10131087    };
    10141088
  • lemon/concept/ugraph.h

    r2021 r2111  
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief Undirected graphs and components of.
     21///\brief The concept of the undirected graphs.
    2222
    2323
     
    3131namespace lemon {
    3232  namespace concept {
    33 
    34 //     /// Skeleton class which describes an edge with direction in \ref
    35 //     /// UGraph "undirected graph".
    36     template <typename UGraph>
    37     class UGraphEdge : public UGraph::UEdge {
    38       typedef typename UGraph::UEdge UEdge;
    39       typedef typename UGraph::Node Node;
    40     public:
    41 
    42       /// \e
    43       UGraphEdge() {}
    44 
    45       /// \e
    46       UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
    47 
    48       /// \e
    49       UGraphEdge(Invalid) {}
    50 
    51       /// \brief Directed edge from undirected edge and a source node.
    52       ///
    53       /// Constructs a directed edge from undirected edge and a source node.
    54       ///
    55       /// \note You have to specify the graph for this constructor.
    56       UGraphEdge(const UGraph &g,
    57                      UEdge u_edge, Node n) {
    58         ignore_unused_variable_warning(u_edge);
    59         ignore_unused_variable_warning(g);
    60         ignore_unused_variable_warning(n);
    61       }
    62 
    63       /// \e
    64       UGraphEdge& operator=(UGraphEdge) { return *this; }
    65 
    66       /// \e
    67       bool operator==(UGraphEdge) const { return true; }
    68       /// \e
    69       bool operator!=(UGraphEdge) const { return false; }
    70 
    71       /// \e
    72       bool operator<(UGraphEdge) const { return false; }
    73 
    74       template <typename Edge>
    75       struct Constraints {
    76         void constraints() {
    77           const_constraints();
    78         }
    79         void const_constraints() const {
    80           /// \bug This should be is_base_and_derived ...
    81           UEdge ue = e;
    82           ue = e;
    83 
    84           Edge e_with_source(graph,ue,n);
    85           ignore_unused_variable_warning(e_with_source);
    86         }
    87         Edge e;
    88         UEdge ue;
    89         UGraph graph;
    90         Node n;
    91       };
    92     };
    93    
    94 
    95     struct BaseIterableUGraphConcept {
    96 
    97       template <typename Graph>
    98       struct Constraints {
    99 
    100         typedef typename Graph::UEdge UEdge;
    101         typedef typename Graph::Edge Edge;
    102         typedef typename Graph::Node Node;
    103 
    104         void constraints() {
    105           checkConcept<BaseIterableGraphComponent, Graph>();
    106           checkConcept<GraphItem<>, UEdge>();
    107           //checkConcept<UGraphEdge<Graph>, Edge>();
    108 
    109           graph.first(ue);
    110           graph.next(ue);
    111 
    112           const_constraints();
    113         }
    114         void const_constraints() {
    115           Node n;
    116           n = graph.target(ue);
    117           n = graph.source(ue);
    118           n = graph.oppositeNode(n0, ue);
    119 
    120           bool b;
    121           b = graph.direction(e);
    122           Edge e = graph.direct(UEdge(), true);
    123           e = graph.direct(UEdge(), n);
    124  
    125           ignore_unused_variable_warning(b);
    126         }
    127 
    128         Graph graph;
    129         Edge e;
    130         Node n0;
    131         UEdge ue;
    132       };
    133 
    134     };
    135 
    136 
    137     struct IterableUGraphConcept {
    138 
    139       template <typename Graph>
    140       struct Constraints {
    141         void constraints() {
    142           /// \todo we don't need the iterable component to be base iterable
    143           /// Don't we really???
    144           //checkConcept< BaseIterableUGraphConcept, Graph > ();
    145 
    146           checkConcept<IterableGraphComponent, Graph> ();
    147 
    148           typedef typename Graph::UEdge UEdge;
    149           typedef typename Graph::UEdgeIt UEdgeIt;
    150           typedef typename Graph::IncEdgeIt IncEdgeIt;
    151 
    152           checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
    153           checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
    154         }
    155       };
    156 
    157     };
    158 
    159     struct MappableUGraphConcept {
    160 
    161       template <typename Graph>
    162       struct Constraints {
    163 
    164         struct Dummy {
    165           int value;
    166           Dummy() : value(0) {}
    167           Dummy(int _v) : value(_v) {}
    168         };
    169 
    170         void constraints() {
    171           checkConcept<MappableGraphComponent, Graph>();
    172 
    173           typedef typename Graph::template UEdgeMap<int> IntMap;
    174           checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
    175             IntMap >();
    176 
    177           typedef typename Graph::template UEdgeMap<bool> BoolMap;
    178           checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
    179             BoolMap >();
    180 
    181           typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
    182           checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
    183             DummyMap >();
    184         }
    185       };
    186 
    187     };
    188 
    189     struct ExtendableUGraphConcept {
    190 
    191       template <typename Graph>
    192       struct Constraints {
    193         void constraints() {
    194           node_a = graph.addNode();
    195           uedge = graph.addEdge(node_a, node_b);
    196         }
    197         typename Graph::Node node_a, node_b;
    198         typename Graph::UEdge uedge;
    199         Graph graph;
    200       };
    201 
    202     };
    203 
    204     struct ErasableUGraphConcept {
    205 
    206       template <typename Graph>
    207       struct Constraints {
    208         void constraints() {
    209           graph.erase(n);
    210           graph.erase(e);
    211         }
    212         Graph graph;
    213         typename Graph::Node n;
    214         typename Graph::UEdge e;
    215       };
    216 
    217     };
    21833
    21934    /// \addtogroup graph_concepts
     
    23247    ///
    23348    /// In LEMON undirected graphs also fulfill the concept of directed
    234     /// graphs (\ref lemon::concept::StaticGraph "Graph Concept"). For
    235     /// explanation of this and more see also the page \ref ugraphs,
    236     /// a tutorial about undirected graphs.
     49    /// graphs (\ref lemon::concept::Graph "Graph Concept"). For
     50    /// explanation of this and more see also the page \ref graphs,
     51    /// a tutorial about graphs.
    23752    ///
    23853    /// You can assume that all undirected graph can be handled
    239     /// as a static directed graph. This way it is fully conform
    240     /// to the StaticGraph concept.
     54    /// as a directed graph. This way it is fully conform
     55    /// to the Graph concept.
    24156
    24257    class UGraph {
     
    800615      Node target(Edge) const { return INVALID; }
    801616
    802 //       /// \brief First node of the graph
    803 //       ///
    804 //       /// \note This method is part of so called \ref
    805 //       /// developpers_interface "Developpers' interface", so it shouldn't
    806 //       /// be used in an end-user program.
    807617      void first(Node&) const {}
    808 //       /// \brief Next node of the graph
    809 //       ///
    810 //       /// \note This method is part of so called \ref
    811 //       /// developpers_interface "Developpers' interface", so it shouldn't
    812 //       /// be used in an end-user program.
    813618      void next(Node&) const {}
    814619
    815 //       /// \brief First undirected edge of the graph
    816 //       ///
    817 //       /// \note This method is part of so called \ref
    818 //       /// developpers_interface "Developpers' interface", so it shouldn't
    819 //       /// be used in an end-user program.
    820620      void first(UEdge&) const {}
    821 //       /// \brief Next undirected edge of the graph
    822 //       ///
    823 //       /// \note This method is part of so called \ref
    824 //       /// developpers_interface "Developpers' interface", so it shouldn't
    825 //       /// be used in an end-user program.
    826621      void next(UEdge&) const {}
    827622
    828 //       /// \brief First directed edge of the graph
    829 //       ///
    830 //       /// \note This method is part of so called \ref
    831 //       /// developpers_interface "Developpers' interface", so it shouldn't
    832 //       /// be used in an end-user program.
    833623      void first(Edge&) const {}
    834 //       /// \brief Next directed edge of the graph
    835 //       ///
    836 //       /// \note This method is part of so called \ref
    837 //       /// developpers_interface "Developpers' interface", so it shouldn't
    838 //       /// be used in an end-user program.
    839624      void next(Edge&) const {}
    840625
    841 //       /// \brief First outgoing edge from a given node
    842 //       ///
    843 //       /// \note This method is part of so called \ref
    844 //       /// developpers_interface "Developpers' interface", so it shouldn't
    845 //       /// be used in an end-user program.
    846626      void firstOut(Edge&, Node) const {}
    847 //       /// \brief Next outgoing edge to a node
    848 //       ///
    849 //       /// \note This method is part of so called \ref
    850 //       /// developpers_interface "Developpers' interface", so it shouldn't
    851 //       /// be used in an end-user program.
    852627      void nextOut(Edge&) const {}
    853628
    854 //       /// \brief First incoming edge to a given node
    855 //       ///
    856 //       /// \note This method is part of so called \ref
    857 //       /// developpers_interface "Developpers' interface", so it shouldn't
    858 //       /// be used in an end-user program.
    859629      void firstIn(Edge&, Node) const {}
    860 //       /// \brief Next incoming edge to a node
    861 //       ///
    862 //       /// \note This method is part of so called \ref
    863 //       /// developpers_interface "Developpers' interface", so it shouldn't
    864 //       /// be used in an end-user program.
    865630      void nextIn(Edge&) const {}
    866631
    867632
    868633      void firstInc(UEdge &, bool &, const Node &) const {}
    869 
    870634      void nextInc(UEdge &, bool &) const {}
    871635
     
    923687    };
    924688
    925     /// \brief An empty non-static undirected graph class.
    926     ///   
    927     /// This class provides everything that \ref UGraph does.
    928     /// Additionally it enables building graphs from scratch.
    929     class ExtendableUGraph : public UGraph {
    930     public:
    931      
    932       /// \brief Add a new node to the graph.
    933       ///
    934       /// Add a new node to the graph.
    935       /// \return the new node.
    936       Node addNode();
    937 
    938       /// \brief Add a new undirected edge to the graph.
    939       ///
    940       /// Add a new undirected edge to the graph.
    941       /// \return the new edge.
    942       UEdge addEdge(const Node& from, const Node& to);
    943 
    944       /// \brief Resets the graph.
    945       ///
    946       /// This function deletes all undirected edges and nodes of the graph.
    947       /// It also frees the memory allocated to store them.
    948       void clear() { }
    949 
    950       template <typename Graph>
    951       struct Constraints {
    952         void constraints() {
    953           checkConcept<BaseIterableUGraphConcept, Graph>();
    954           checkConcept<IterableUGraphConcept, Graph>();
    955           checkConcept<MappableUGraphConcept, Graph>();
    956 
    957           checkConcept<UGraph, Graph>();
    958           checkConcept<ExtendableUGraphConcept, Graph>();
    959           checkConcept<ClearableGraphComponent, Graph>();
    960         }
    961       };
    962 
    963     };
    964 
    965     /// \brief An empty erasable undirected graph class.
    966     ///
    967     /// This class is an extension of \ref ExtendableUGraph. It makes it
    968     /// possible to erase undirected edges or nodes.
    969     class ErasableUGraph : public ExtendableUGraph {
    970     public:
    971 
    972       /// \brief Deletes a node.
    973       ///
    974       /// Deletes a node.
    975       ///
    976       void erase(Node) { }
    977       /// \brief Deletes an undirected edge.
    978       ///
    979       /// Deletes an undirected edge.
    980       ///
    981       void erase(UEdge) { }
    982 
    983       template <typename Graph>
    984       struct Constraints {
    985         void constraints() {
    986           checkConcept<ExtendableUGraph, Graph>();
    987           checkConcept<ErasableUGraphConcept, Graph>();
    988         }
    989       };
    990 
    991     };
    992 
    993689    /// @}
    994690
Note: See TracChangeset for help on using the changeset viewer.