COIN-OR::LEMON - Graph Library

Changes in / [83:3654324ec035:84:8161012eaa61] in lemon-main


Ignore:
Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/graph_extender.h

    r57 r78  
    2121
    2222#include <lemon/bits/invalid.h>
     23#include <lemon/bits/utility.h>
    2324
    2425#include <lemon/bits/map_extender.h>
     
    6465    }
    6566
    66     Node oppositeNode(const Node &n, const Arc &e) const {
    67       if (n == Parent::source(e))
    68         return Parent::target(e);
    69       else if(n==Parent::target(e))
    70         return Parent::source(e);
     67    Node oppositeNode(const Node &node, const Arc &arc) const {
     68      if (node == Parent::source(arc))
     69        return Parent::target(arc);
     70      else if(node == Parent::target(arc))
     71        return Parent::source(arc);
    7172      else
    7273        return INVALID;
     
    9596
    9697    class NodeIt : public Node {
    97       const Digraph* digraph;
     98      const Digraph* _digraph;
    9899    public:
    99100
     
    102103      NodeIt(Invalid i) : Node(i) { }
    103104
    104       explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
    105         _digraph.first(static_cast<Node&>(*this));
    106       }
    107 
    108       NodeIt(const Digraph& _digraph, const Node& node)
    109         : Node(node), digraph(&_digraph) {}
     105      explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
     106        _digraph->first(static_cast<Node&>(*this));
     107      }
     108
     109      NodeIt(const Digraph& digraph, const Node& node)
     110        : Node(node), _digraph(&digraph) {}
    110111
    111112      NodeIt& operator++() {
    112         digraph->next(*this);
     113        _digraph->next(*this);
    113114        return *this;
    114115      }
     
    118119
    119120    class ArcIt : public Arc {
    120       const Digraph* digraph;
     121      const Digraph* _digraph;
    121122    public:
    122123
     
    125126      ArcIt(Invalid i) : Arc(i) { }
    126127
    127       explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
    128         _digraph.first(static_cast<Arc&>(*this));
    129       }
    130 
    131       ArcIt(const Digraph& _digraph, const Arc& e) :
    132         Arc(e), digraph(&_digraph) { }
     128      explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
     129        _digraph->first(static_cast<Arc&>(*this));
     130      }
     131
     132      ArcIt(const Digraph& digraph, const Arc& arc) :
     133        Arc(arc), _digraph(&digraph) { }
    133134
    134135      ArcIt& operator++() {
    135         digraph->next(*this);
     136        _digraph->next(*this);
    136137        return *this;
    137138      }
     
    141142
    142143    class OutArcIt : public Arc {
    143       const Digraph* digraph;
     144      const Digraph* _digraph;
    144145    public:
    145146
     
    148149      OutArcIt(Invalid i) : Arc(i) { }
    149150
    150       OutArcIt(const Digraph& _digraph, const Node& node)
    151         : digraph(&_digraph) {
    152         _digraph.firstOut(*this, node);
    153       }
    154 
    155       OutArcIt(const Digraph& _digraph, const Arc& arc)
    156         : Arc(arc), digraph(&_digraph) {}
     151      OutArcIt(const Digraph& digraph, const Node& node)
     152        : _digraph(&digraph) {
     153        _digraph->firstOut(*this, node);
     154      }
     155
     156      OutArcIt(const Digraph& digraph, const Arc& arc)
     157        : Arc(arc), _digraph(&digraph) {}
    157158
    158159      OutArcIt& operator++() {
    159         digraph->nextOut(*this);
     160        _digraph->nextOut(*this);
    160161        return *this;
    161162      }
     
    165166
    166167    class InArcIt : public Arc {
    167       const Digraph* digraph;
     168      const Digraph* _digraph;
    168169    public:
    169170
     
    172173      InArcIt(Invalid i) : Arc(i) { }
    173174
    174       InArcIt(const Digraph& _digraph, const Node& node)
    175         : digraph(&_digraph) {
    176         _digraph.firstIn(*this, node);
    177       }
    178 
    179       InArcIt(const Digraph& _digraph, const Arc& arc) :
    180         Arc(arc), digraph(&_digraph) {}
     175      InArcIt(const Digraph& digraph, const Node& node)
     176        : _digraph(&digraph) {
     177        _digraph->firstIn(*this, node);
     178      }
     179
     180      InArcIt(const Digraph& digraph, const Arc& arc) :
     181        Arc(arc), _digraph(&digraph) {}
    181182
    182183      InArcIt& operator++() {
    183         digraph->nextIn(*this);
     184        _digraph->nextIn(*this);
    184185        return *this;
    185186      }
     
    190191    ///
    191192    /// Returns the base node (i.e. the source in this case) of the iterator
    192     Node baseNode(const OutArcIt &e) const {
    193       return Parent::source(e);
     193    Node baseNode(const OutArcIt &arc) const {
     194      return Parent::source(arc);
    194195    }
    195196    /// \brief Running node of the iterator
     
    197198    /// Returns the running node (i.e. the target in this case) of the
    198199    /// iterator
    199     Node runningNode(const OutArcIt &e) const {
    200       return Parent::target(e);
     200    Node runningNode(const OutArcIt &arc) const {
     201      return Parent::target(arc);
    201202    }
    202203
     
    204205    ///
    205206    /// Returns the base node (i.e. the target in this case) of the iterator
    206     Node baseNode(const InArcIt &e) const {
    207       return Parent::target(e);
     207    Node baseNode(const InArcIt &arc) const {
     208      return Parent::target(arc);
    208209    }
    209210    /// \brief Running node of the iterator
     
    211212    /// Returns the running node (i.e. the source in this case) of the
    212213    /// iterator
    213     Node runningNode(const InArcIt &e) const {
    214       return Parent::source(e);
     214    Node runningNode(const InArcIt &arc) const {
     215      return Parent::source(arc);
    215216    }
    216217
     
    324325  };
    325326
    326   /// \ingroup graphbits
     327  /// \ingroup _graphbits
    327328  ///
    328329  /// \brief Extender for the Graphs
     
    332333   
    333334    typedef Base Parent;
    334     typedef GraphExtender Digraph;
     335    typedef GraphExtender Graph;
     336
     337    typedef True UndirectedTag;
    335338
    336339    typedef typename Parent::Node Node;
     
    373376    }
    374377
    375     Arc oppositeArc(const Arc &e) const {
    376       return Parent::direct(e, !Parent::direction(e));
     378    Arc oppositeArc(const Arc &arc) const {
     379      return Parent::direct(arc, !Parent::direction(arc));
    377380    }
    378381
    379382    using Parent::direct;
    380     Arc direct(const Edge &ue, const Node &s) const {
    381       return Parent::direct(ue, Parent::source(ue) == s);
     383    Arc direct(const Edge &edge, const Node &node) const {
     384      return Parent::direct(edge, Parent::source(edge) == node);
    382385    }
    383386
     
    412415
    413416    class NodeIt : public Node {
    414       const Digraph* digraph;
     417      const Graph* _graph;
    415418    public:
    416419
     
    419422      NodeIt(Invalid i) : Node(i) { }
    420423
    421       explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
    422         _digraph.first(static_cast<Node&>(*this));
    423       }
    424 
    425       NodeIt(const Digraph& _digraph, const Node& node)
    426         : Node(node), digraph(&_digraph) {}
     424      explicit NodeIt(const Graph& graph) : _graph(&graph) {
     425        _graph->first(static_cast<Node&>(*this));
     426      }
     427
     428      NodeIt(const Graph& graph, const Node& node)
     429        : Node(node), _graph(&graph) {}
    427430
    428431      NodeIt& operator++() {
    429         digraph->next(*this);
     432        _graph->next(*this);
    430433        return *this;
    431434      }
     
    435438
    436439    class ArcIt : public Arc {
    437       const Digraph* digraph;
     440      const Graph* _graph;
    438441    public:
    439442
     
    442445      ArcIt(Invalid i) : Arc(i) { }
    443446
    444       explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
    445         _digraph.first(static_cast<Arc&>(*this));
    446       }
    447 
    448       ArcIt(const Digraph& _digraph, const Arc& e) :
    449         Arc(e), digraph(&_digraph) { }
     447      explicit ArcIt(const Graph& graph) : _graph(&graph) {
     448        _graph->first(static_cast<Arc&>(*this));
     449      }
     450
     451      ArcIt(const Graph& graph, const Arc& arc) :
     452        Arc(arc), _graph(&graph) { }
    450453
    451454      ArcIt& operator++() {
    452         digraph->next(*this);
     455        _graph->next(*this);
    453456        return *this;
    454457      }
     
    458461
    459462    class OutArcIt : public Arc {
    460       const Digraph* digraph;
     463      const Graph* _graph;
    461464    public:
    462465
     
    465468      OutArcIt(Invalid i) : Arc(i) { }
    466469
    467       OutArcIt(const Digraph& _digraph, const Node& node)
    468         : digraph(&_digraph) {
    469         _digraph.firstOut(*this, node);
    470       }
    471 
    472       OutArcIt(const Digraph& _digraph, const Arc& arc)
    473         : Arc(arc), digraph(&_digraph) {}
     470      OutArcIt(const Graph& graph, const Node& node)
     471        : _graph(&graph) {
     472        _graph->firstOut(*this, node);
     473      }
     474
     475      OutArcIt(const Graph& graph, const Arc& arc)
     476        : Arc(arc), _graph(&graph) {}
    474477
    475478      OutArcIt& operator++() {
    476         digraph->nextOut(*this);
     479        _graph->nextOut(*this);
    477480        return *this;
    478481      }
     
    482485
    483486    class InArcIt : public Arc {
    484       const Digraph* digraph;
     487      const Graph* _graph;
    485488    public:
    486489
     
    489492      InArcIt(Invalid i) : Arc(i) { }
    490493
    491       InArcIt(const Digraph& _digraph, const Node& node)
    492         : digraph(&_digraph) {
    493         _digraph.firstIn(*this, node);
    494       }
    495 
    496       InArcIt(const Digraph& _digraph, const Arc& arc) :
    497         Arc(arc), digraph(&_digraph) {}
     494      InArcIt(const Graph& graph, const Node& node)
     495        : _graph(&graph) {
     496        _graph->firstIn(*this, node);
     497      }
     498
     499      InArcIt(const Graph& graph, const Arc& arc) :
     500        Arc(arc), _graph(&graph) {}
    498501
    499502      InArcIt& operator++() {
    500         digraph->nextIn(*this);
     503        _graph->nextIn(*this);
    501504        return *this;
    502505      }
     
    506509
    507510    class EdgeIt : public Parent::Edge {
    508       const Digraph* digraph;
     511      const Graph* _graph;
    509512    public:
    510513
     
    513516      EdgeIt(Invalid i) : Edge(i) { }
    514517
    515       explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) {
    516         _digraph.first(static_cast<Edge&>(*this));
    517       }
    518 
    519       EdgeIt(const Digraph& _digraph, const Edge& e) :
    520         Edge(e), digraph(&_digraph) { }
     518      explicit EdgeIt(const Graph& graph) : _graph(&graph) {
     519        _graph->first(static_cast<Edge&>(*this));
     520      }
     521
     522      EdgeIt(const Graph& graph, const Edge& edge) :
     523        Edge(edge), _graph(&graph) { }
    521524
    522525      EdgeIt& operator++() {
    523         digraph->next(*this);
    524         return *this;
    525       }
    526 
    527     };
    528 
    529     class IncArcIt : public Parent::Edge {
     526        _graph->next(*this);
     527        return *this;
     528      }
     529
     530    };
     531
     532    class IncEdgeIt : public Parent::Edge {
    530533      friend class GraphExtender;
    531       const Digraph* digraph;
    532       bool direction;
    533     public:
    534 
    535       IncArcIt() { }
    536 
    537       IncArcIt(Invalid i) : Edge(i), direction(false) { }
    538 
    539       IncArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {
    540         _digraph.firstInc(*this, direction, n);
    541       }
    542 
    543       IncArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)
    544         : digraph(&_digraph), Edge(ue) {
    545         direction = (_digraph.source(ue) == n);
    546       }
    547 
    548       IncArcIt& operator++() {
    549         digraph->nextInc(*this, direction);
     534      const Graph* _graph;
     535      bool _direction;
     536    public:
     537
     538      IncEdgeIt() { }
     539
     540      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
     541
     542      IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
     543        _graph->firstInc(*this, _direction, node);
     544      }
     545
     546      IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
     547        : _graph(&graph), Edge(edge) {
     548        _direction = (_graph->source(edge) == node);
     549      }
     550
     551      IncEdgeIt& operator++() {
     552        _graph->nextInc(*this, _direction);
    550553        return *this;
    551554      }
     
    555558    ///
    556559    /// Returns the base node (ie. the source in this case) of the iterator
    557     Node baseNode(const OutArcIt &e) const {
    558       return Parent::source(static_cast<const Arc&>(e));
     560    Node baseNode(const OutArcIt &arc) const {
     561      return Parent::source(static_cast<const Arc&>(arc));
    559562    }
    560563    /// \brief Running node of the iterator
     
    562565    /// Returns the running node (ie. the target in this case) of the
    563566    /// iterator
    564     Node runningNode(const OutArcIt &e) const {
    565       return Parent::target(static_cast<const Arc&>(e));
     567    Node runningNode(const OutArcIt &arc) const {
     568      return Parent::target(static_cast<const Arc&>(arc));
    566569    }
    567570
     
    569572    ///
    570573    /// Returns the base node (ie. the target in this case) of the iterator
    571     Node baseNode(const InArcIt &e) const {
    572       return Parent::target(static_cast<const Arc&>(e));
     574    Node baseNode(const InArcIt &arc) const {
     575      return Parent::target(static_cast<const Arc&>(arc));
    573576    }
    574577    /// \brief Running node of the iterator
     
    576579    /// Returns the running node (ie. the source in this case) of the
    577580    /// iterator
    578     Node runningNode(const InArcIt &e) const {
    579       return Parent::source(static_cast<const Arc&>(e));
     581    Node runningNode(const InArcIt &arc) const {
     582      return Parent::source(static_cast<const Arc&>(arc));
    580583    }
    581584
     
    583586    ///
    584587    /// Returns the base node of the iterator
    585     Node baseNode(const IncArcIt &e) const {
    586       return e.direction ? source(e) : target(e);
     588    Node baseNode(const IncEdgeIt &edge) const {
     589      return edge._direction ? source(edge) : target(edge);
    587590    }
    588591    /// Running node of the iterator
    589592    ///
    590593    /// Returns the running node of the iterator
    591     Node runningNode(const IncArcIt &e) const {
    592       return e.direction ? target(e) : source(e);
     594    Node runningNode(const IncEdgeIt &edge) const {
     595      return edge._direction ? target(edge) : source(edge);
    593596    }
    594597
     
    597600    template <typename _Value>
    598601    class NodeMap
    599       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
    600     public:
    601       typedef GraphExtender Digraph;
    602       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    603 
    604       NodeMap(const Digraph& digraph)
    605         : Parent(digraph) {}
    606       NodeMap(const Digraph& digraph, const _Value& value)
    607         : Parent(digraph, value) {}
     602      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
     603    public:
     604      typedef GraphExtender Graph;
     605      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
     606
     607      NodeMap(const Graph& graph)
     608        : Parent(graph) {}
     609      NodeMap(const Graph& graph, const _Value& value)
     610        : Parent(graph, value) {}
    608611
    609612      NodeMap& operator=(const NodeMap& cmap) {
     
    621624    template <typename _Value>
    622625    class ArcMap
    623       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    624     public:
    625       typedef GraphExtender Digraph;
    626       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    627 
    628       ArcMap(const Digraph& digraph)
    629         : Parent(digraph) {}
    630       ArcMap(const Digraph& digraph, const _Value& value)
    631         : Parent(digraph, value) {}
     626      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
     627    public:
     628      typedef GraphExtender Graph;
     629      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
     630
     631      ArcMap(const Graph& graph)
     632        : Parent(graph) {}
     633      ArcMap(const Graph& graph, const _Value& value)
     634        : Parent(graph, value) {}
    632635
    633636      ArcMap& operator=(const ArcMap& cmap) {
     
    645648    template <typename _Value>
    646649    class EdgeMap
    647       : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
    648     public:
    649       typedef GraphExtender Digraph;
    650       typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
    651 
    652       EdgeMap(const Digraph& digraph)
    653         : Parent(digraph) {}
    654 
    655       EdgeMap(const Digraph& digraph, const _Value& value)
    656         : Parent(digraph, value) {}
     650      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     651    public:
     652      typedef GraphExtender Graph;
     653      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     654
     655      EdgeMap(const Graph& graph)
     656        : Parent(graph) {}
     657
     658      EdgeMap(const Graph& graph, const _Value& value)
     659        : Parent(graph, value) {}
    657660
    658661      EdgeMap& operator=(const EdgeMap& cmap) {
     
    693696    }
    694697
    695     template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>
    696     void build(const Digraph& digraph, NodeRefMap& nodeRef,
     698    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
     699    void build(const Graph& graph, NodeRefMap& nodeRef,
    697700               EdgeRefMap& edgeRef) {
    698       Parent::build(digraph, nodeRef, edgeRef);
     701      Parent::build(graph, nodeRef, edgeRef);
    699702      notifier(Node()).build();
    700703      notifier(Edge()).build();
     
    721724
    722725    void erase(const Edge& edge) {
    723       std::vector<Arc> ev;
    724       ev.push_back(Parent::direct(edge, true));
    725       ev.push_back(Parent::direct(edge, false));     
    726       notifier(Arc()).erase(ev);
     726      std::vector<Arc> av;
     727      av.push_back(Parent::direct(edge, true));
     728      av.push_back(Parent::direct(edge, false));     
     729      notifier(Arc()).erase(av);
    727730      notifier(Edge()).erase(edge);
    728731      Parent::erase(edge);
  • lemon/concepts/graph.h

    r61 r78  
    6464    /// the EdgeMap to map values for the edges. The InArcIt and
    6565    /// OutArcIt iterates on the same edges but with opposite
    66     /// direction. The IncArcIt iterates also on the same edges
     66    /// direction. The IncEdgeIt iterates also on the same edges
    6767    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    6868    /// to Edge. 
     
    271271      ///\code
    272272      /// int count=0;
    273       /// for(Graph::IncArcIt e(g, n); e!=INVALID; ++e) ++count;
     273      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    274274      ///\endcode
    275       class IncArcIt : public Edge {
    276       public:
    277         /// Default constructor
    278 
    279         /// @warning The default constructor sets the iterator
    280         /// to an undefined value.
    281         IncArcIt() { }
    282         /// Copy constructor.
    283 
    284         /// Copy constructor.
    285         ///
    286         IncArcIt(const IncArcIt& e) : Edge(e) { }
    287         /// Initialize the iterator to be invalid.
    288 
    289         /// Initialize the iterator to be invalid.
    290         ///
    291         IncArcIt(Invalid) { }
     275      class IncEdgeIt : public Edge {
     276      public:
     277        /// Default constructor
     278
     279        /// @warning The default constructor sets the iterator
     280        /// to an undefined value.
     281        IncEdgeIt() { }
     282        /// Copy constructor.
     283
     284        /// Copy constructor.
     285        ///
     286        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
     287        /// Initialize the iterator to be invalid.
     288
     289        /// Initialize the iterator to be invalid.
     290        ///
     291        IncEdgeIt(Invalid) { }
    292292        /// This constructor sets the iterator to first incident arc.
    293293   
    294294        /// This constructor set the iterator to the first incident arc of
    295295        /// the node.
    296         IncArcIt(const Graph&, const Node&) { }
    297         /// Edge -> IncArcIt conversion
     296        IncEdgeIt(const Graph&, const Node&) { }
     297        /// Edge -> IncEdgeIt conversion
    298298
    299299        /// Sets the iterator to the value of the trivial iterator \c e.
    300300        /// This feature necessitates that each time we
    301301        /// iterate the arc-set, the iteration order is the same.
    302         IncArcIt(const Graph&, const Edge&) { }
     302        IncEdgeIt(const Graph&, const Edge&) { }
    303303        /// Next incident arc
    304304
    305305        /// Assign the iterator to the next incident arc
    306306        /// of the corresponding node.
    307         IncArcIt& operator++() { return *this; }
     307        IncEdgeIt& operator++() { return *this; }
    308308      };
    309309
     
    721721      ///
    722722      /// Returns the base node of the iterator
    723       Node baseNode(IncArcIt) const {
     723      Node baseNode(IncEdgeIt) const {
    724724        return INVALID;
    725725      }
     
    728728      ///
    729729      /// Returns the running node of the iterator
    730       Node runningNode(IncArcIt) const {
     730      Node runningNode(IncEdgeIt) const {
    731731        return INVALID;
    732732      }
  • lemon/concepts/graph_components.h

    r57 r78  
    829829      /// This iterator goes trough the incident arcs of a certain
    830830      /// node of a graph.
    831       typedef GraphIncIt<Graph, Edge, Node, 'u'> IncArcIt;
     831      typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt;
    832832      /// \brief The base node of the iterator.
    833833      ///
    834834      /// Gives back the base node of the iterator.
    835       Node baseNode(const IncArcIt&) const { return INVALID; }
     835      Node baseNode(const IncEdgeIt&) const { return INVALID; }
    836836
    837837      /// \brief The running node of the iterator.
    838838      ///
    839839      /// Gives back the running node of the iterator.
    840       Node runningNode(const IncArcIt&) const { return INVALID; }
     840      Node runningNode(const IncEdgeIt&) const { return INVALID; }
    841841
    842842      /// @}
     
    866866              typename _Graph::EdgeIt >();
    867867            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
    868               typename _Graph::Node, 'u'>, typename _Graph::IncArcIt>();
     868              typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
    869869           
    870870            typename _Graph::Node n;
    871             typename _Graph::IncArcIt ueit(INVALID);
     871            typename _Graph::IncEdgeIt ueit(INVALID);
    872872            n = graph.baseNode(ueit);
    873873            n = graph.runningNode(ueit);
Note: See TracChangeset for help on using the changeset viewer.