COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

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


Ignore:
Timestamp:
06/28/06 17:06:24 (18 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
Files:
19 edited

Legend:

Unmodified
Added
Removed

  • lemon/bellman_ford.h

    r2074 r2111  
    165165  /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
    166166  /// \param _LengthMap This read-only EdgeMap determines the lengths of the
    167   /// edges. The default map type is \ref concept::StaticGraph::EdgeMap
     167  /// edges. The default map type is \ref concept::Graph::EdgeMap
    168168  /// "Graph::EdgeMap<int>".  The value of _LengthMap is not used directly
    169169  /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. 

  • 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

  • lemon/dag_shortest_path.h

    r1999 r2111  
    275275  /// DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits.
    276276  /// \param _LengthMap This read-only EdgeMap determines the lengths of the
    277   /// edges. The default map type is \ref concept::StaticGraph::EdgeMap
     277  /// edges. The default map type is \ref concept::Graph::EdgeMap
    278278  /// "Graph::EdgeMap<int>".  The value of _LengthMap is not used directly
    279279  /// by DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits. 

  • lemon/dijkstra.h

    r2010 r2111  
    158158  ///relatively time consuming process to compute the edge length if
    159159  ///it is necessary. The default map type is \ref
    160   ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
     160  ///concept::Graph::EdgeMap "Graph::EdgeMap<int>".  The value
    161161  ///of LM is not used directly by Dijkstra, it is only passed to \ref
    162162  ///DijkstraDefaultTraits.  \param TR Traits class to set

  • lemon/edge_set.h

    r2076 r2111  
    239239  ///
    240240  /// \param _Graph The type of the graph which shares its node set with
    241   /// this class. Its interface must conform to the \ref concept::StaticGraph
    242   /// "StaticGraph" concept.
     241  /// this class. Its interface must conform to the \ref concept::Graph
     242  /// "Graph" concept.
    243243  ///
    244244  /// In the edge extension and removing it conforms to the
    245   /// \ref concept::ErasableGraph "ErasableGraph" concept.
     245  /// \ref concept::Graph "Graph" concept.
    246246  template <typename _Graph>
    247247  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
    … …  
    331331  ///
    332332  /// \param _Graph The type of the graph which shares its node set with
    333   /// this class. Its interface must conform to the \ref concept::StaticGraph
    334   /// "StaticGraph" concept.
     333  /// this class. Its interface must conform to the \ref concept::Graph
     334  /// "Graph" concept.
    335335  ///
    336336  /// In the edge extension and removing it conforms to the
    337   /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
     337  /// \ref concept::UGraph "UGraph" concept.
    338338  template <typename _Graph>
    339339  class ListUEdgeSet
    … …  
    568568  ///
    569569  /// \param _Graph The type of the graph which shares its node set with
    570   /// this class. Its interface must conform to the \ref concept::StaticGraph
    571   /// "StaticGraph" concept.
     570  /// this class. Its interface must conform to the \ref concept::Graph
     571  /// "Graph" concept.
    572572  ///
    573573  /// In the edge extension and removing it conforms to the
    574   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
     574  /// \ref concept::Graph "Graph" concept.
    575575  template <typename _Graph>
    576576  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
    … …  
    663663  ///
    664664  /// \param _Graph The type of the graph which shares its node set with
    665   /// this class. Its interface must conform to the \ref concept::StaticGraph
    666   /// "StaticGraph" concept.
     665  /// this class. Its interface must conform to the \ref concept::Graph
     666  /// "Graph" concept.
    667667  ///
    668668  /// In the edge extension and removing it conforms to the
    669   /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
     669  /// \ref concept::UGraph "UGraph" concept.
    670670  template <typename _Graph>
    671671  class SmartUEdgeSet

  • lemon/floyd_warshall.h

    r2042 r2111  
    172172  /// relatively time consuming process to compute the edge length if
    173173  /// it is necessary. The default map type is \ref
    174   /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
     174  /// concept::Graph::EdgeMap "Graph::EdgeMap<int>".  The value
    175175  /// of _LengthMap is not used directly by FloydWarshall, it is only passed
    176176  /// to \ref FloydWarshallDefaultTraits.  \param _Traits Traits class to set

  • lemon/full_graph.h

    r2076 r2111  
    215215  /// edges or nodes.
    216216  /// Thus it conforms to
    217   /// the \ref concept::StaticGraph "StaticGraph" concept
    218   /// \sa concept::StaticGraph.
     217  /// the \ref concept::Graph "Graph" concept
     218  /// \sa concept::Graph.
    219219  ///
    220220  /// \sa FullGraphBase

  • lemon/graph_adaptor.h

    r2084 r2111  
    24252425  ///
    24262426  /// This graph adaptor is fully conform to the
    2427   /// \ref concept::StaticGraph "StaticGraph" concept and
     2427  /// \ref concept::Graph "Graph" concept and
    24282428  /// contains some additional member functions and types. The
    24292429  /// documentation of some member functions may be found just in the

  • lemon/hypercube_graph.h

    r1998 r2111  
    250250  /// is 26.
    251251  ///
    252   /// The graph type is fully conform to the \ref concept::StaticGraph
     252  /// The graph type is fully conform to the \ref concept::Graph
    253253  /// concept but it does not conform to the \ref concept::UGraph.
    254254  ///

  • lemon/johnson.h

    r2042 r2111  
    207207  /// relatively time consuming process to compute the edge length if
    208208  /// it is necessary. The default map type is \ref
    209   /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
     209  /// concept::Graph::EdgeMap "Graph::EdgeMap<int>".  The value
    210210  /// of _LengthMap is not used directly by Johnson, it is only passed
    211211  /// to \ref JohnsonDefaultTraits.  \param _Traits Traits class to set

  • lemon/kruskal.h

    r2084 r2111  
    4545  ///
    4646  /// \param g The graph the algorithm runs on.
    47   /// It can be either \ref concept::StaticGraph "directed" or
     47  /// It can be either \ref concept::Graph "directed" or
    4848  /// \ref concept::UGraph "undirected".
    4949  /// If the graph is directed, the algorithm consider it to be

  • lemon/list_graph.h

    r2107 r2111  
    275275
    276276  protected:
    277     void _changeTarget(Edge e, Node n)
     277    void changeTarget(Edge e, Node n)
    278278    {
    279279      if(edges[e.id].next_in != -1)
    … …  
    290290      nodes[n.id].first_in = e.id;
    291291    }
    292     void _changeSource(Edge e, Node n)
     292    void changeSource(Edge e, Node n)
    293293    {
    294294      if(edges[e.id].next_out != -1)
    … …  
    317317  ///This is a simple and fast erasable graph implementation.
    318318  ///
    319   ///It conforms to the
    320   ///\ref concept::ErasableGraph "ErasableGraph" concept and
    321   ///it also provides several additional useful extra functionalities.
    322   ///\sa concept::ErasableGraph.
     319  ///It conforms to the \ref concept::Graph "Graph" concept and it
     320  ///also provides several additional useful extra functionalities.
     321  ///The most of the member functions and nested classes are
     322  ///documented only in the concept class.
     323  ///\sa concept::Graph.
    323324
    324325  class ListGraph : public ExtendedListGraphBase {
    … …  
    326327
    327328    typedef ExtendedListGraphBase Parent;
     329
     330    ///Add a new node to the graph.
     331   
     332    /// \return the new node.
     333    ///
     334    Node addNode() { return Parent::addNode(); }
     335
     336    ///Add a new edge to the graph.
     337   
     338    ///Add a new edge to the graph with source node \c s
     339    ///and target node \c t.
     340    ///\return the new edge.
     341    Edge addEdge(const Node& s, const Node& t) {
     342      return Parent::addEdge(s, t);
     343    }
    328344
    329345    /// Changes the target of \c e to \c n
    … …  
    335351    ///valid. However <tt>InEdge</tt>s are invalidated.
    336352    void changeTarget(Edge e, Node n) {
    337       _changeTarget(e,n);
     353      Parent::changeTarget(e,n);
    338354    }
    339355    /// Changes the source of \c e to \c n
    … …  
    345361    ///valid. However <tt>OutEdge</tt>s are invalidated.
    346362    void changeSource(Edge e, Node n) {
    347       _changeSource(e,n);
     363      Parent::changeSource(e,n);
    348364    }
    349365
    … …  
    355371    void reverseEdge(Edge e) {
    356372      Node t=target(e);
    357       _changeTarget(e,source(e));
    358       _changeSource(e,t);
    359     }
    360 
    361     ///Using this it is possible to avoid the superfluous memory
    362     ///allocation.
     373      changeTarget(e,source(e));
     374      changeSource(e,t);
     375    }
     376
     377    /// \brief Using this it is possible to avoid the superfluous memory
     378    /// allocation.
    363379
    364380    ///Using this it is possible to avoid the superfluous memory
    … …  
    368384    void reserveNode(int n) { nodes.reserve(n); };
    369385
    370     ///Using this it is possible to avoid the superfluous memory
    371     ///allocation.
     386    /// \brief Using this it is possible to avoid the superfluous memory
     387    /// allocation.
    372388
    373389    ///Using this it is possible to avoid the superfluous memory
    … …  
    599615  public:
    600616    typedef ExtendedListUGraphBase Parent;
     617    /// \brief Add a new node to the graph.
     618    ///
     619    /// \return the new node.
     620    ///
     621    Node addNode() { return Parent::addNode(); }
     622
     623    /// \brief Add a new edge to the graph.
     624    ///
     625    /// Add a new edge to the graph with source node \c s
     626    /// and target node \c t.
     627    /// \return the new undirected edge.
     628    UEdge addEdge(const Node& s, const Node& t) {
     629      return Parent::addEdge(s, t);
     630    }
    601631    /// \brief Changes the target of \c e to \c n
    602632    ///
    … …  
    607637    /// valid. However <tt>InEdge</tt>'s are invalidated.
    608638    void changeTarget(UEdge e, Node n) {
    609       _changeTarget(e,n);
     639      Parent::changeTarget(e,n);
    610640    }
    611641    /// Changes the source of \c e to \c n
    … …  
    617647    ///valid. However <tt>OutEdge</tt>'s are invalidated.
    618648    void changeSource(UEdge e, Node n) {
    619       _changeSource(e,n);
     649      Parent::changeSource(e,n);
    620650    }
    621651    /// \brief Contract two nodes.

  • lemon/min_cost_arborescence.h

    r2042 r2111  
    111111  /// relatively time consuming process to compute the edge cost if
    112112  /// it is necessary. The default map type is \ref
    113   /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
     113  /// concept::Graph::EdgeMap "Graph::EdgeMap<int>".  The value
    114114  /// of _CostMap is not used directly by MinCostArborescence,
    115115  /// it is only passed to \ref MinCostArborescenceDefaultTraits. 

  • lemon/min_cut.h

    r2094 r2111  
    180180  /// relatively time consuming process to compute the edge capacity if
    181181  /// it is necessary. The default map type is \ref
    182   /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
     182  /// concept::Graph::EdgeMap "Graph::EdgeMap<int>".  The value
    183183  /// of CapacityMap is not used directly by search algorithm, it is only
    184184  /// passed to \ref MaxCardinalitySearchDefaultTraits. 
    … …  
    702702    typedef _Graph Graph;
    703703
    704     /// The AuxGraph type which is an ErasableGraph
     704    /// The AuxGraph type which is an Graph
    705705    typedef ListUGraph AuxGraph;
    706706

  • lemon/smart_graph.h

    r2076 r2111  
    240240  ///node and edge deletions</b>.
    241241  ///It conforms to
    242   ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
    243   ///\sa concept::ExtendableGraph.
     242  ///the \ref concept::Graph "Graph" concept.
     243  ///\sa concept::Graph.
    244244  ///
    245245  ///\author Alpar Juttner

  • lemon/topology.h

    r2082 r2111  
    245245  template <typename Graph>
    246246  bool stronglyConnected(const Graph& graph) {
    247     checkConcept<concept::StaticGraph, Graph>();
     247    checkConcept<concept::Graph, Graph>();
    248248
    249249    typedef typename Graph::Node Node;
    … …  
    303303  template <typename Graph>
    304304  int countStronglyConnectedComponents(const Graph& graph) {
    305     checkConcept<concept::StaticGraph, Graph>();
     305    checkConcept<concept::Graph, Graph>();
    306306
    307307    using namespace _topology_bits;
    … …  
    372372  template <typename Graph, typename NodeMap>
    373373  int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
    374     checkConcept<concept::StaticGraph, Graph>();
     374    checkConcept<concept::Graph, Graph>();
    375375    typedef typename Graph::Node Node;
    376376    typedef typename Graph::NodeIt NodeIt;
    … …  
    435435  template <typename Graph, typename EdgeMap>
    436436  int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
    437     checkConcept<concept::StaticGraph, Graph>();
     437    checkConcept<concept::Graph, Graph>();
    438438    typedef typename Graph::Node Node;
    439439    typedef typename Graph::Edge Edge;
    … …  
    12061206    using namespace _topology_bits;
    12071207
    1208     checkConcept<concept::StaticGraph, Graph>();
     1208    checkConcept<concept::Graph, Graph>();
    12091209    checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();
    12101210
    … …  
    12481248    using namespace _topology_bits;
    12491249
    1250     checkConcept<concept::StaticGraph, Graph>();
     1250    checkConcept<concept::Graph, Graph>();
    12511251    checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
    12521252
    … …  
    12911291  bool dag(const Graph& graph) {
    12921292
    1293     checkConcept<concept::StaticGraph, Graph>();
     1293    checkConcept<concept::Graph, Graph>();
    12941294
    12951295    typedef typename Graph::Node Node;
Note: See TracChangeset for help on using the changeset viewer.