COIN-OR::LEMON - Graph Library

Changeset 2111:ea1fa1bc3f6d in lemon-0.x


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

Files:
30 edited

Legend:

Unmodified
Added
Removed
  • doc/graphs.dox

    r1638 r2111  
    22
    33\page graphs Graphs
     4
     5\todo Write a new Graphs page. I think it should be contain the Graph,
     6UGraph and BpUGraph concept. It should be describe the iterators and
     7the basic functions and the differences of the implementations.
    48
    59The primary data structures of LEMON are the graph classes. They all
     
    812as  incoming and outgoing edges of a given node.
    913
     14Each graph should meet the \ref lemon::concept::Graph "Graph" concept.
     15This concept does not make it possible to change the graph (i.e. it is
     16not possible to add or delete edges or nodes). Most of the graph
     17algorithms will run on these graphs.
    1018
    11 Each graph should meet the
    12 \ref lemon::concept::StaticGraph "StaticGraph" concept.
    13 This concept does not
    14 make it possible to change the graph (i.e. it is not possible to add
    15 or delete edges or nodes). Most of the graph algorithms will run on
    16 these graphs.
    17 
    18 The graphs meeting the
    19 \ref lemon::concept::ExtendableGraph "ExtendableGraph"
    20 concept allow node and
    21 edge addition. You can also "clear" such a graph (i.e. erase all edges and nodes ).
    2219
    2320In case of graphs meeting the full feature
     
    3734\li \ref lemon::FullGraph "FullGraph"
    3835implements a complete graph. It is a
    39 \ref lemon::concept::StaticGraph "StaticGraph", so you cannot
     36\ref lemon::concept::Graph "Graph", so you cannot
    4037change the number of nodes once it is constructed. It is extremely memory
    4138efficient: it uses constant amount of memory independently from the number of
  • 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;
  • test/bfs_test.cc

    r1956 r2111  
    3030void check_Bfs_Compile()
    3131{
    32   typedef concept::StaticGraph Graph;
     32  typedef concept::Graph Graph;
    3333
    3434  typedef Graph::Edge Edge;
     
    6767{
    6868  typedef int VType;
    69   typedef concept::StaticGraph Graph;
     69  typedef concept::Graph Graph;
    7070
    7171  typedef Graph::Edge Edge;
  • test/dfs_test.cc

    r1956 r2111  
    3030void check_Dfs_SmartGraph_Compile()
    3131{
    32   typedef concept::StaticGraph Graph;
     32  typedef concept::Graph Graph;
    3333
    3434  typedef Graph::Edge Edge;
     
    6868{
    6969  typedef int VType;
    70   typedef concept::StaticGraph Graph;
     70  typedef concept::Graph Graph;
    7171
    7272  typedef Graph::Edge Edge;
  • test/dijkstra_test.cc

    r1956 r2111  
    3232{
    3333  typedef int VType;
    34   typedef concept::StaticGraph Graph;
     34  typedef concept::Graph Graph;
    3535
    3636  typedef Graph::Edge Edge;
     
    7171{
    7272  typedef int VType;
    73   typedef concept::StaticGraph Graph;
     73  typedef concept::Graph Graph;
    7474
    7575  typedef Graph::Edge Edge;
  • test/edge_set_test.cc

    r1990 r2111  
    1818using namespace lemon::concept;
    1919
    20 typedef SmartGraph Graph;
     20typedef SmartGraph RGraph;
    2121
    2222int main() {
    2323  { // checking edge_sets
    24     checkConcept<StaticGraph, ListEdgeSet<Graph> >();
    25     checkConcept<UGraph, ListUEdgeSet<Graph> >();
    26     checkConcept<StaticGraph, SmartEdgeSet<Graph> >();
    27     checkConcept<UGraph, SmartUEdgeSet<Graph> >();
     24    checkConcept<Graph, ListEdgeSet<RGraph> >();
     25    checkConcept<UGraph, ListUEdgeSet<RGraph> >();
     26    checkConcept<Graph, SmartEdgeSet<RGraph> >();
     27    checkConcept<UGraph, SmartUEdgeSet<RGraph> >();
    2828  }
    2929
  • test/graph_adaptor_test.cc

    r1991 r2111  
    4747{
    4848  {
    49     typedef StaticGraph Graph;
    50     checkConcept<StaticGraph, GraphAdaptor<Graph> >();
     49    typedef Graph Graph;
     50    checkConcept<Graph, GraphAdaptor<Graph> >();
    5151
    52     checkConcept<StaticGraph, RevGraphAdaptor<Graph> >();
     52    checkConcept<Graph, RevGraphAdaptor<Graph> >();
    5353
    54     checkConcept<StaticGraph, SubGraphAdaptor<Graph,
     54    checkConcept<Graph, SubGraphAdaptor<Graph,
    5555      Graph::NodeMap<bool> , Graph::EdgeMap<bool> > >();
    56     checkConcept<StaticGraph, NodeSubGraphAdaptor<Graph,
     56    checkConcept<Graph, NodeSubGraphAdaptor<Graph,
    5757      Graph::NodeMap<bool> > >();
    58     checkConcept<StaticGraph, EdgeSubGraphAdaptor<Graph,
     58    checkConcept<Graph, EdgeSubGraphAdaptor<Graph,
    5959      Graph::EdgeMap<bool> > >();
    6060   
    61     checkConcept<StaticGraph, ResGraphAdaptor<Graph, int,
     61    checkConcept<Graph, ResGraphAdaptor<Graph, int,
    6262      Graph::EdgeMap<int>, Graph::EdgeMap<int> > >();
    6363
    64     checkConcept<StaticGraph, ErasingFirstGraphAdaptor<Graph,
     64    checkConcept<Graph, ErasingFirstGraphAdaptor<Graph,
    6565      Graph::NodeMap<Graph::Edge> > >();
    6666
     
    7474      UGraph::UEdgeMap<bool> > >();
    7575
    76     checkConcept<StaticGraph, DirUGraphAdaptor<UGraph,
     76    checkConcept<Graph, DirUGraphAdaptor<UGraph,
    7777      UGraph::UEdgeMap<bool> > >();
    7878  }
  • test/graph_factory_test.cc

    r1956 r2111  
    7171
    7272//Compile Graph
    73 template void lemon::concept::checkCompileStaticGraph<concept::StaticGraph>
    74 (concept::StaticGraph &);
     73template void lemon::concept::checkCompileGraph<concept::Graph>
     74(concept::Graph &);
    7575
    7676template
    77 void lemon::concept::checkCompileExtendableGraph<concept::ExtendableGraph>
    78 (concept::ExtendableGraph &);
     77void lemon::concept::checkCompileGraph<concept::Graph>
     78(concept::Graph &);
    7979
    8080template
    81 void lemon::concept::checkCompileErasableGraph<concept::ErasableGraph>
    82 (concept::ErasableGraph &);
     81void lemon::concept::checkCompileGraph<concept::Graph>
     82(concept::Graph &);
    8383
    8484//Compile SmartGraph
    8585template
    86 void lemon::concept::checkCompileExtendableGraph<SmartGraph>(SmartGraph &);
     86void lemon::concept::checkCompileGraph<SmartGraph>(SmartGraph &);
    8787template
    8888void lemon::concept::checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
     
    9494//Compile ListGraph
    9595template
    96 void lemon::concept::checkCompileExtendableGraph<ListGraph>(ListGraph &);
     96void lemon::concept::checkCompileGraph<ListGraph>(ListGraph &);
    9797template
    98 void lemon::concept::checkCompileErasableGraph<ListGraph>(ListGraph &);
     98void lemon::concept::checkCompileGraph<ListGraph>(ListGraph &);
    9999template
    100100void lemon::concept::checkCompileGraphFindEdge<ListGraph>(ListGraph &);
     
    103103//Compile SymListGraph
    104104//template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
    105 //template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
     105//template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
    106106//template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
    107107
    108108//Compile FullGraph
    109 template void lemon::concept::checkCompileStaticGraph<FullGraph>(FullGraph &);
     109template void lemon::concept::checkCompileGraph<FullGraph>(FullGraph &);
    110110template
    111111void lemon::concept::checkCompileGraphFindEdge<FullGraph>(FullGraph &);
  • test/graph_test.cc

    r1956 r2111  
    4444    checkConcept<MaxIDableGraphComponent, MaxIDableGraphComponent >();
    4545
    46     checkConcept<BaseExtendableGraphComponent, BaseExtendableGraphComponent >();
    47     checkConcept<BaseErasableGraphComponent, BaseErasableGraphComponent >();
    48 
    4946    checkConcept<IterableGraphComponent, IterableGraphComponent >();
    5047
    5148    checkConcept<MappableGraphComponent, MappableGraphComponent >();
    5249
    53     checkConcept<ExtendableGraphComponent, ExtendableGraphComponent >();
    54     checkConcept<ErasableGraphComponent, ErasableGraphComponent >();
    55     checkConcept<ClearableGraphComponent, ClearableGraphComponent >();
    5650  }
    5751  { // checking skeleton graphs
    58     checkConcept<StaticGraph, StaticGraph >();
    59     checkConcept<ExtendableGraph, ExtendableGraph >();
    60     checkConcept<ErasableGraph, ErasableGraph >();
     52    checkConcept<Graph, Graph >();
    6153  }
    6254  { // checking list graph
    63     checkConcept<ErasableGraph, ListGraph >();
     55    checkConcept<Graph, ListGraph >();
    6456
    6557    checkGraph<ListGraph>();
     
    6860  }
    6961  { // checking smart graph
    70     checkConcept<ExtendableGraph, SmartGraph >();
     62    checkConcept<Graph, SmartGraph >();
    7163
    7264    checkGraph<SmartGraph>();
     
    7567  }
    7668  { // checking full graph
    77     checkConcept<StaticGraph, FullGraph >();
     69    checkConcept<Graph, FullGraph >();
    7870  }
    7971  { // checking full graph
    80     checkConcept<StaticGraph, HyperCubeGraph >();
     72    checkConcept<Graph, HyperCubeGraph >();
    8173  }
    8274
  • test/kruskal_test.cc

    r1956 r2111  
    3333void checkCompileKruskal()
    3434{
    35   concept::WriteMap<concept::StaticGraph::Edge,bool> w;
     35  concept::WriteMap<concept::Graph::Edge,bool> w;
    3636
    37   kruskal(concept::StaticGraph(),
    38           concept::ReadMap<concept::StaticGraph::Edge,int>(),
     37  kruskal(concept::Graph(),
     38          concept::ReadMap<concept::Graph::Edge,int>(),
    3939          w);
    4040}
  • test/preflow_test.cc

    r2108 r2111  
    3232{
    3333  typedef int VType;
    34   typedef concept::StaticGraph Graph;
     34  typedef concept::Graph Graph;
    3535
    3636  typedef Graph::Node Node;
  • test/ugraph_test.cc

    r1979 r2111  
    3434void check_concepts() {
    3535  checkConcept<UGraph, ListUGraph>();
    36   checkConcept<ErasableUGraph, ListUGraph>();
    3736
    3837  checkConcept<UGraph, SmartUGraph>();
    39   checkConcept<ExtendableUGraph, SmartUGraph>();
    4038
    4139  checkConcept<UGraph, FullUGraph>();
Note: See TracChangeset for help on using the changeset viewer.