COIN-OR::LEMON - Graph Library

Changeset 1909:2d806130e700 in lemon-0.x for lemon/concept


Ignore:
Timestamp:
01/26/06 16:42:13 (14 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2484
Message:

Undir -> U transition

Location:
lemon/concept
Files:
2 edited
1 moved

Legend:

Unmodified
Added
Removed
  • lemon/concept/graph.h

    r1875 r1909  
    4343    public:
    4444
    45       typedef False UndirTag;
     45      typedef False UTag;
    4646     
    4747      typedef BaseGraphComponent::Node Node;
     
    124124      ///\todo undocumented
    125125      ///
    126       typedef False UndirTag;
     126      typedef False UTag;
    127127
    128128      /// Defalult constructor.
  • lemon/concept/graph_component.h

    r1875 r1909  
    3535    /// Skeleton class for graph Node and Edge types
    3636
    37     /// This class describes the interface of Node and Edge (and UndirEdge
     37    /// This class describes the interface of Node and Edge (and UEdge
    3838    /// in undirected graphs) subtypes of graph types.
    3939    ///
  • lemon/concept/ugraph.h

    r1875 r1909  
    11/* -*- C++ -*-
    22 *
    3  * lemon/concept/undir_graph_component.h - Part of LEMON, a generic
     3 * lemon/concept/ugraph_component.h - Part of LEMON, a generic
    44 * C++ optimization library
    55 *
     
    3434
    3535//     /// Skeleton class which describes an edge with direction in \ref
    36 //     /// UndirGraph "undirected graph".
    37     template <typename UndirGraph>
    38     class UndirGraphEdge : public UndirGraph::UndirEdge {
    39       typedef typename UndirGraph::UndirEdge UndirEdge;
    40       typedef typename UndirGraph::Node Node;
     36//     /// UGraph "undirected graph".
     37    template <typename UGraph>
     38    class UGraphEdge : public UGraph::UEdge {
     39      typedef typename UGraph::UEdge UEdge;
     40      typedef typename UGraph::Node Node;
    4141    public:
    4242
    4343      /// \e
    44       UndirGraphEdge() {}
     44      UGraphEdge() {}
    4545
    4646      /// \e
    47       UndirGraphEdge(const UndirGraphEdge& e) : UndirGraph::UndirEdge(e) {}
     47      UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
    4848
    4949      /// \e
    50       UndirGraphEdge(Invalid) {}
     50      UGraphEdge(Invalid) {}
    5151
    5252      /// \brief Directed edge from undirected edge and a source node.
     
    5555      ///
    5656      /// \note You have to specify the graph for this constructor.
    57       UndirGraphEdge(const UndirGraph &g,
    58                      UndirEdge undir_edge, Node n) {
    59         ignore_unused_variable_warning(undir_edge);
     57      UGraphEdge(const UGraph &g,
     58                     UEdge u_edge, Node n) {
     59        ignore_unused_variable_warning(u_edge);
    6060        ignore_unused_variable_warning(g);
    6161        ignore_unused_variable_warning(n);
     
    6363
    6464      /// \e
    65       UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
     65      UGraphEdge& operator=(UGraphEdge) { return *this; }
    6666
    6767      /// \e
    68       bool operator==(UndirGraphEdge) const { return true; }
     68      bool operator==(UGraphEdge) const { return true; }
    6969      /// \e
    70       bool operator!=(UndirGraphEdge) const { return false; }
     70      bool operator!=(UGraphEdge) const { return false; }
    7171
    7272      /// \e
    73       bool operator<(UndirGraphEdge) const { return false; }
     73      bool operator<(UGraphEdge) const { return false; }
    7474
    7575      template <typename Edge>
     
    8080        void const_constraints() const {
    8181          /// \bug This should be is_base_and_derived ...
    82           UndirEdge ue = e;
     82          UEdge ue = e;
    8383          ue = e;
    8484
     
    8787        }
    8888        Edge e;
    89         UndirEdge ue;
    90         UndirGraph graph;
     89        UEdge ue;
     90        UGraph graph;
    9191        Node n;
    9292      };
     
    9494   
    9595
    96     struct BaseIterableUndirGraphConcept {
     96    struct BaseIterableUGraphConcept {
    9797
    9898      template <typename Graph>
    9999      struct Constraints {
    100100
    101         typedef typename Graph::UndirEdge UndirEdge;
     101        typedef typename Graph::UEdge UEdge;
    102102        typedef typename Graph::Edge Edge;
    103103        typedef typename Graph::Node Node;
     
    105105        void constraints() {
    106106          checkConcept<BaseIterableGraphComponent, Graph>();
    107           checkConcept<GraphItem<>, UndirEdge>();
    108           //checkConcept<UndirGraphEdge<Graph>, Edge>();
     107          checkConcept<GraphItem<>, UEdge>();
     108          //checkConcept<UGraphEdge<Graph>, Edge>();
    109109
    110110          graph.first(ue);
     
    121121          bool b;
    122122          b = graph.direction(e);
    123           Edge e = graph.direct(UndirEdge(), true);
    124           e = graph.direct(UndirEdge(), n);
     123          Edge e = graph.direct(UEdge(), true);
     124          e = graph.direct(UEdge(), n);
    125125 
    126126          ignore_unused_variable_warning(b);
     
    130130        Edge e;
    131131        Node n0;
    132         UndirEdge ue;
     132        UEdge ue;
    133133      };
    134134
     
    136136
    137137
    138     struct IterableUndirGraphConcept {
     138    struct IterableUGraphConcept {
    139139
    140140      template <typename Graph>
     
    143143          /// \todo we don't need the iterable component to be base iterable
    144144          /// Don't we really???
    145           //checkConcept< BaseIterableUndirGraphConcept, Graph > ();
     145          //checkConcept< BaseIterableUGraphConcept, Graph > ();
    146146
    147147          checkConcept<IterableGraphComponent, Graph> ();
    148148
    149           typedef typename Graph::UndirEdge UndirEdge;
    150           typedef typename Graph::UndirEdgeIt UndirEdgeIt;
     149          typedef typename Graph::UEdge UEdge;
     150          typedef typename Graph::UEdgeIt UEdgeIt;
    151151          typedef typename Graph::IncEdgeIt IncEdgeIt;
    152152
    153           checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
    154           checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
     153          checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
     154          checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
    155155        }
    156156      };
     
    158158    };
    159159
    160     struct MappableUndirGraphConcept {
     160    struct MappableUGraphConcept {
    161161
    162162      template <typename Graph>
     
    172172          checkConcept<MappableGraphComponent, Graph>();
    173173
    174           typedef typename Graph::template UndirEdgeMap<int> IntMap;
    175           checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,
     174          typedef typename Graph::template UEdgeMap<int> IntMap;
     175          checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
    176176            IntMap >();
    177177
    178           typedef typename Graph::template UndirEdgeMap<bool> BoolMap;
    179           checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,
     178          typedef typename Graph::template UEdgeMap<bool> BoolMap;
     179          checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
    180180            BoolMap >();
    181181
    182           typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;
    183           checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,
     182          typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
     183          checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
    184184            DummyMap >();
    185185        }
     
    188188    };
    189189
    190     struct ExtendableUndirGraphConcept {
     190    struct ExtendableUGraphConcept {
    191191
    192192      template <typename Graph>
     
    197197        }
    198198        typename Graph::Node node_a, node_b;
    199         typename Graph::UndirEdge uedge;
     199        typename Graph::UEdge uedge;
    200200        Graph graph;
    201201      };
     
    203203    };
    204204
    205     struct ErasableUndirGraphConcept {
     205    struct ErasableUGraphConcept {
    206206
    207207      template <typename Graph>
     
    213213        Graph graph;
    214214        typename Graph::Node n;
    215         typename Graph::UndirEdge e;
     215        typename Graph::UEdge e;
    216216      };
    217217
     
    234234    /// In LEMON undirected graphs also fulfill the concept of directed
    235235    /// graphs (\ref lemon::concept::StaticGraph "Graph Concept"). For
    236     /// explanation of this and more see also the page \ref undir_graphs,
     236    /// explanation of this and more see also the page \ref ugraphs,
    237237    /// a tutorial about undirected graphs.
    238238    ///
     
    241241    /// to the StaticGraph concept.
    242242
    243     class UndirGraph {
     243    class UGraph {
    244244    public:
    245245      ///\e
     
    247247      ///\todo undocumented
    248248      ///
    249       typedef True UndirTag;
     249      typedef True UTag;
    250250
    251251      /// \brief The base type of node iterators,
     
    330330        /// Sets the iterator to the first node of \c g.
    331331        ///
    332         NodeIt(const UndirGraph&) { }
     332        NodeIt(const UGraph&) { }
    333333        /// Node -> NodeIt conversion.
    334334
     
    337337        /// This feature necessitates that each time we
    338338        /// iterate the edge-set, the iteration order is the same.
    339         NodeIt(const UndirGraph&, const Node&) { }
     339        NodeIt(const UGraph&, const Node&) { }
    340340        /// Next node.
    341341
     
    350350      /// The base type of the undirected edge iterators.
    351351      ///
    352       class UndirEdge {
     352      class UEdge {
    353353      public:
    354354        /// Default constructor
     
    356356        /// @warning The default constructor sets the iterator
    357357        /// to an undefined value.
    358         UndirEdge() { }
    359         /// Copy constructor.
    360 
    361         /// Copy constructor.
    362         ///
    363         UndirEdge(const UndirEdge&) { }
    364         /// Initialize the iterator to be invalid.
    365 
    366         /// Initialize the iterator to be invalid.
    367         ///
    368         UndirEdge(Invalid) { }
     358        UEdge() { }
     359        /// Copy constructor.
     360
     361        /// Copy constructor.
     362        ///
     363        UEdge(const UEdge&) { }
     364        /// Initialize the iterator to be invalid.
     365
     366        /// Initialize the iterator to be invalid.
     367        ///
     368        UEdge(Invalid) { }
    369369        /// Equality operator
    370370
    371371        /// Two iterators are equal if and only if they point to the
    372372        /// same object or both are invalid.
    373         bool operator==(UndirEdge) const { return true; }
     373        bool operator==(UEdge) const { return true; }
    374374        /// Inequality operator
    375375
    376         /// \sa operator==(UndirEdge n)
    377         ///
    378         bool operator!=(UndirEdge) const { return true; }
     376        /// \sa operator==(UEdge n)
     377        ///
     378        bool operator!=(UEdge) const { return true; }
    379379
    380380        /// Artificial ordering operator.
     
    388388        ///
    389389        /// \bug This is a technical requirement. Do we really need this?
    390         bool operator<(UndirEdge) const { return false; }
     390        bool operator<(UEdge) const { return false; }
    391391      };
    392392
     
    398398      /// \code
    399399      /// int count=0;
    400       /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count;
     400      /// for(Graph::UEdgeIt e(g); e!=INVALID; ++e) ++count;
    401401      /// \endcode
    402       class UndirEdgeIt : public UndirEdge {
     402      class UEdgeIt : public UEdge {
    403403      public:
    404404        /// Default constructor
     
    406406        /// @warning The default constructor sets the iterator
    407407        /// to an undefined value.
    408         UndirEdgeIt() { }
    409         /// Copy constructor.
    410 
    411         /// Copy constructor.
    412         ///
    413         UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }
    414         /// Initialize the iterator to be invalid.
    415 
    416         /// Initialize the iterator to be invalid.
    417         ///
    418         UndirEdgeIt(Invalid) { }
     408        UEdgeIt() { }
     409        /// Copy constructor.
     410
     411        /// Copy constructor.
     412        ///
     413        UEdgeIt(const UEdgeIt& e) : UEdge(e) { }
     414        /// Initialize the iterator to be invalid.
     415
     416        /// Initialize the iterator to be invalid.
     417        ///
     418        UEdgeIt(Invalid) { }
    419419        /// This constructor sets the iterator to the first undirected edge.
    420420   
    421421        /// This constructor sets the iterator to the first undirected edge.
    422         UndirEdgeIt(const UndirGraph&) { }
    423         /// UndirEdge -> UndirEdgeIt conversion
     422        UEdgeIt(const UGraph&) { }
     423        /// UEdge -> UEdgeIt conversion
    424424
    425425        /// Sets the iterator to the value of the trivial iterator.
     
    427427        /// iterate the undirected edge-set, the iteration order is the
    428428        /// same.
    429         UndirEdgeIt(const UndirGraph&, const UndirEdge&) { }
     429        UEdgeIt(const UGraph&, const UEdge&) { }
    430430        /// Next undirected edge
    431431       
    432432        /// Assign the iterator to the next undirected edge.
    433         UndirEdgeIt& operator++() { return *this; }
     433        UEdgeIt& operator++() { return *this; }
    434434      };
    435435
     
    448448      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    449449      /// \endcode
    450       class IncEdgeIt : public UndirEdge {
     450      class IncEdgeIt : public UEdge {
    451451      public:
    452452        /// Default constructor
     
    459459        /// Copy constructor.
    460460        ///
    461         IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { }
     461        IncEdgeIt(const IncEdgeIt& e) : UEdge(e) { }
    462462        /// Initialize the iterator to be invalid.
    463463
     
    469469        /// This constructor set the iterator to the first incident edge of
    470470        /// the node.
    471         IncEdgeIt(const UndirGraph&, const Node&) { }
    472         /// UndirEdge -> IncEdgeIt conversion
     471        IncEdgeIt(const UGraph&, const Node&) { }
     472        /// UEdge -> IncEdgeIt conversion
    473473
    474474        /// Sets the iterator to the value of the trivial iterator \c e.
    475475        /// This feature necessitates that each time we
    476476        /// iterate the edge-set, the iteration order is the same.
    477         IncEdgeIt(const UndirGraph&, const UndirEdge&) { }
     477        IncEdgeIt(const UGraph&, const UEdge&) { }
    478478        /// Next incident edge
    479479
     
    487487      /// The directed edge type. It can be converted to the
    488488      /// undirected edge.
    489       class Edge : public UndirEdge {
     489      class Edge : public UEdge {
    490490      public:
    491491        /// Default constructor
     
    498498        /// Copy constructor.
    499499        ///
    500         Edge(const Edge& e) : UndirEdge(e) { }
     500        Edge(const Edge& e) : UEdge(e) { }
    501501        /// Initialize the iterator to be invalid.
    502502
     
    558558        /// This constructor sets the iterator to the first edge of \c g.
    559559        ///@param g the graph
    560         EdgeIt(const UndirGraph &g) { ignore_unused_variable_warning(g); }
     560        EdgeIt(const UGraph &g) { ignore_unused_variable_warning(g); }
    561561        /// Edge -> EdgeIt conversion
    562562
     
    564564        /// This feature necessitates that each time we
    565565        /// iterate the edge-set, the iteration order is the same.
    566         EdgeIt(const UndirGraph&, const Edge&) { }
     566        EdgeIt(const UGraph&, const Edge&) { }
    567567        ///Next edge
    568568       
     
    606606        ///@param n the node
    607607        ///@param g the graph
    608         OutEdgeIt(const UndirGraph& n, const Node& g) {
     608        OutEdgeIt(const UGraph& n, const Node& g) {
    609609          ignore_unused_variable_warning(n);
    610610          ignore_unused_variable_warning(g);
     
    615615        /// This feature necessitates that each time we
    616616        /// iterate the edge-set, the iteration order is the same.
    617         OutEdgeIt(const UndirGraph&, const Edge&) { }
     617        OutEdgeIt(const UGraph&, const Edge&) { }
    618618        ///Next outgoing edge
    619619       
     
    658658        ///@param n the node
    659659        ///@param g the graph
    660         InEdgeIt(const UndirGraph& g, const Node& n) {
     660        InEdgeIt(const UGraph& g, const Node& n) {
    661661          ignore_unused_variable_warning(n);
    662662          ignore_unused_variable_warning(g);
     
    667667        /// This feature necessitates that each time we
    668668        /// iterate the edge-set, the iteration order is the same.
    669         InEdgeIt(const UndirGraph&, const Edge&) { }
     669        InEdgeIt(const UGraph&, const Edge&) { }
    670670        /// Next incoming edge
    671671
     
    688688
    689689        ///\e
    690         NodeMap(const UndirGraph&) { }
     690        NodeMap(const UGraph&) { }
    691691        ///\e
    692         NodeMap(const UndirGraph&, T) { }
     692        NodeMap(const UGraph&, T) { }
    693693
    694694        ///Copy constructor
     
    712712
    713713        ///\e
    714         EdgeMap(const UndirGraph&) { }
     714        EdgeMap(const UGraph&) { }
    715715        ///\e
    716         EdgeMap(const UndirGraph&, T) { }
     716        EdgeMap(const UGraph&, T) { }
    717717        ///Copy constructor
    718718        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
     
    726726      /// Reference map of the edges to type \c T.
    727727      /// \sa Reference
    728       /// \warning Making maps that can handle bool type (UndirEdgeMap<bool>)
     728      /// \warning Making maps that can handle bool type (UEdgeMap<bool>)
    729729      /// needs some extra attention!
    730730      /// \todo Wrong documentation
    731731      template<class T>
    732       class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>
     732      class UEdgeMap : public ReadWriteMap<UEdge,T>
    733733      {
    734734      public:
    735735
    736736        ///\e
    737         UndirEdgeMap(const UndirGraph&) { }
     737        UEdgeMap(const UGraph&) { }
    738738        ///\e
    739         UndirEdgeMap(const UndirGraph&, T) { }
     739        UEdgeMap(const UGraph&, T) { }
    740740        ///Copy constructor
    741         UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) {}
     741        UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
    742742        ///Assignment operator
    743         UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
     743        UEdgeMap &operator=(const UEdgeMap&) { return *this; }
    744744        // \todo fix this concept   
    745745      };
     
    749749      /// Direct the given undirected edge. The returned edge source
    750750      /// will be the given edge.
    751       Edge direct(const UndirEdge&, const Node&) const {
     751      Edge direct(const UEdge&, const Node&) const {
    752752        return INVALID;
    753753      }
     
    758758      /// will be the source of the undirected edge if the given bool
    759759      /// is true.
    760       Edge direct(const UndirEdge&, bool) const {
     760      Edge direct(const UEdge&, bool) const {
    761761        return INVALID;
    762762      }
     
    776776      ///
    777777      /// \return the opposite of the given Node on the given Edge
    778       Node oppositeNode(Node, UndirEdge) const { return INVALID; }
     778      Node oppositeNode(Node, UEdge) const { return INVALID; }
    779779
    780780      /// \brief First node of the undirected edge.
    781781      ///
    782       /// \return the first node of the given UndirEdge.
    783       ///
    784       /// Naturally undirectected edges don't have direction and thus
     782      /// \return the first node of the given UEdge.
     783      ///
     784      /// Naturally uectected edges don't have direction and thus
    785785      /// don't have source and target node. But we use these two methods
    786786      /// to query the two endnodes of the edge. The direction of the edge
     
    789789      /// of the directed versions of the edges.
    790790      /// \sa direction
    791       Node source(UndirEdge) const { return INVALID; }
     791      Node source(UEdge) const { return INVALID; }
    792792
    793793      /// \brief Second node of the undirected edge.
    794       Node target(UndirEdge) const { return INVALID; }
     794      Node target(UEdge) const { return INVALID; }
    795795
    796796      /// \brief Source node of the directed edge.
     
    818818//       /// developpers_interface "Developpers' interface", so it shouldn't
    819819//       /// be used in an end-user program.
    820       void first(UndirEdge&) const {}
     820      void first(UEdge&) const {}
    821821//       /// \brief Next undirected edge of the graph
    822822//       ///
     
    824824//       /// developpers_interface "Developpers' interface", so it shouldn't
    825825//       /// be used in an end-user program.
    826       void next(UndirEdge&) const {}
     826      void next(UEdge&) const {}
    827827
    828828//       /// \brief First directed edge of the graph
     
    911911      struct Constraints {
    912912        void constraints() {
    913           checkConcept<BaseIterableUndirGraphConcept, Graph>();
    914           checkConcept<IterableUndirGraphConcept, Graph>();
    915           checkConcept<MappableUndirGraphConcept, Graph>();
     913          checkConcept<BaseIterableUGraphConcept, Graph>();
     914          checkConcept<IterableUGraphConcept, Graph>();
     915          checkConcept<MappableUGraphConcept, Graph>();
    916916        }
    917917      };
     
    921921    /// \brief An empty non-static undirected graph class.
    922922    ///   
    923     /// This class provides everything that \ref UndirGraph does.
     923    /// This class provides everything that \ref UGraph does.
    924924    /// Additionally it enables building graphs from scratch.
    925     class ExtendableUndirGraph : public UndirGraph {
     925    class ExtendableUGraph : public UGraph {
    926926    public:
    927927     
     
    936936      /// Add a new undirected edge to the graph.
    937937      /// \return the new edge.
    938       UndirEdge addEdge(const Node& from, const Node& to);
     938      UEdge addEdge(const Node& from, const Node& to);
    939939
    940940      /// \brief Resets the graph.
     
    947947      struct Constraints {
    948948        void constraints() {
    949           checkConcept<BaseIterableUndirGraphConcept, Graph>();
    950           checkConcept<IterableUndirGraphConcept, Graph>();
    951           checkConcept<MappableUndirGraphConcept, Graph>();
    952 
    953           checkConcept<UndirGraph, Graph>();
    954           checkConcept<ExtendableUndirGraphConcept, Graph>();
     949          checkConcept<BaseIterableUGraphConcept, Graph>();
     950          checkConcept<IterableUGraphConcept, Graph>();
     951          checkConcept<MappableUGraphConcept, Graph>();
     952
     953          checkConcept<UGraph, Graph>();
     954          checkConcept<ExtendableUGraphConcept, Graph>();
    955955          checkConcept<ClearableGraphComponent, Graph>();
    956956        }
     
    961961    /// \brief An empty erasable undirected graph class.
    962962    ///
    963     /// This class is an extension of \ref ExtendableUndirGraph. It makes it
     963    /// This class is an extension of \ref ExtendableUGraph. It makes it
    964964    /// possible to erase undirected edges or nodes.
    965     class ErasableUndirGraph : public ExtendableUndirGraph {
     965    class ErasableUGraph : public ExtendableUGraph {
    966966    public:
    967967
     
    975975      /// Deletes an undirected edge.
    976976      ///
    977       void erase(UndirEdge) { }
     977      void erase(UEdge) { }
    978978
    979979      template <typename Graph>
    980980      struct Constraints {
    981981        void constraints() {
    982           checkConcept<ExtendableUndirGraph, Graph>();
    983           checkConcept<ErasableUndirGraphConcept, Graph>();
     982          checkConcept<ExtendableUGraph, Graph>();
     983          checkConcept<ErasableUGraphConcept, Graph>();
    984984        }
    985985      };
Note: See TracChangeset for help on using the changeset viewer.