COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/graph_extender.h

    r78 r57  
    2121
    2222#include <lemon/bits/invalid.h>
    23 #include <lemon/bits/utility.h>
    2423
    2524#include <lemon/bits/map_extender.h>
     
    6564    }
    6665
    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);
     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);
    7271      else
    7372        return INVALID;
     
    9695
    9796    class NodeIt : public Node {
    98       const Digraph* _digraph;
     97      const Digraph* digraph;
    9998    public:
    10099
     
    103102      NodeIt(Invalid i) : Node(i) { }
    104103
    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) {}
     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) {}
    111110
    112111      NodeIt& operator++() {
    113         _digraph->next(*this);
     112        digraph->next(*this);
    114113        return *this;
    115114      }
     
    119118
    120119    class ArcIt : public Arc {
    121       const Digraph* _digraph;
     120      const Digraph* digraph;
    122121    public:
    123122
     
    126125      ArcIt(Invalid i) : Arc(i) { }
    127126
    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) { }
     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) { }
    134133
    135134      ArcIt& operator++() {
    136         _digraph->next(*this);
     135        digraph->next(*this);
    137136        return *this;
    138137      }
     
    142141
    143142    class OutArcIt : public Arc {
    144       const Digraph* _digraph;
     143      const Digraph* digraph;
    145144    public:
    146145
     
    149148      OutArcIt(Invalid i) : Arc(i) { }
    150149
    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) {}
     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) {}
    158157
    159158      OutArcIt& operator++() {
    160         _digraph->nextOut(*this);
     159        digraph->nextOut(*this);
    161160        return *this;
    162161      }
     
    166165
    167166    class InArcIt : public Arc {
    168       const Digraph* _digraph;
     167      const Digraph* digraph;
    169168    public:
    170169
     
    173172      InArcIt(Invalid i) : Arc(i) { }
    174173
    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) {}
     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) {}
    182181
    183182      InArcIt& operator++() {
    184         _digraph->nextIn(*this);
     183        digraph->nextIn(*this);
    185184        return *this;
    186185      }
     
    191190    ///
    192191    /// Returns the base node (i.e. the source in this case) of the iterator
    193     Node baseNode(const OutArcIt &arc) const {
    194       return Parent::source(arc);
     192    Node baseNode(const OutArcIt &e) const {
     193      return Parent::source(e);
    195194    }
    196195    /// \brief Running node of the iterator
     
    198197    /// Returns the running node (i.e. the target in this case) of the
    199198    /// iterator
    200     Node runningNode(const OutArcIt &arc) const {
    201       return Parent::target(arc);
     199    Node runningNode(const OutArcIt &e) const {
     200      return Parent::target(e);
    202201    }
    203202
     
    205204    ///
    206205    /// Returns the base node (i.e. the target in this case) of the iterator
    207     Node baseNode(const InArcIt &arc) const {
    208       return Parent::target(arc);
     206    Node baseNode(const InArcIt &e) const {
     207      return Parent::target(e);
    209208    }
    210209    /// \brief Running node of the iterator
     
    212211    /// Returns the running node (i.e. the source in this case) of the
    213212    /// iterator
    214     Node runningNode(const InArcIt &arc) const {
    215       return Parent::source(arc);
     213    Node runningNode(const InArcIt &e) const {
     214      return Parent::source(e);
    216215    }
    217216
     
    325324  };
    326325
    327   /// \ingroup _graphbits
     326  /// \ingroup graphbits
    328327  ///
    329328  /// \brief Extender for the Graphs
     
    333332   
    334333    typedef Base Parent;
    335     typedef GraphExtender Graph;
    336 
    337     typedef True UndirectedTag;
     334    typedef GraphExtender Digraph;
    338335
    339336    typedef typename Parent::Node Node;
     
    376373    }
    377374
    378     Arc oppositeArc(const Arc &arc) const {
    379       return Parent::direct(arc, !Parent::direction(arc));
     375    Arc oppositeArc(const Arc &e) const {
     376      return Parent::direct(e, !Parent::direction(e));
    380377    }
    381378
    382379    using Parent::direct;
    383     Arc direct(const Edge &edge, const Node &node) const {
    384       return Parent::direct(edge, Parent::source(edge) == node);
     380    Arc direct(const Edge &ue, const Node &s) const {
     381      return Parent::direct(ue, Parent::source(ue) == s);
    385382    }
    386383
     
    415412
    416413    class NodeIt : public Node {
    417       const Graph* _graph;
     414      const Digraph* digraph;
    418415    public:
    419416
     
    422419      NodeIt(Invalid i) : Node(i) { }
    423420
    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) {}
     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) {}
    430427
    431428      NodeIt& operator++() {
    432         _graph->next(*this);
     429        digraph->next(*this);
    433430        return *this;
    434431      }
     
    438435
    439436    class ArcIt : public Arc {
    440       const Graph* _graph;
     437      const Digraph* digraph;
    441438    public:
    442439
     
    445442      ArcIt(Invalid i) : Arc(i) { }
    446443
    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) { }
     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) { }
    453450
    454451      ArcIt& operator++() {
    455         _graph->next(*this);
     452        digraph->next(*this);
    456453        return *this;
    457454      }
     
    461458
    462459    class OutArcIt : public Arc {
    463       const Graph* _graph;
     460      const Digraph* digraph;
    464461    public:
    465462
     
    468465      OutArcIt(Invalid i) : Arc(i) { }
    469466
    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) {}
     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) {}
    477474
    478475      OutArcIt& operator++() {
    479         _graph->nextOut(*this);
     476        digraph->nextOut(*this);
    480477        return *this;
    481478      }
     
    485482
    486483    class InArcIt : public Arc {
    487       const Graph* _graph;
     484      const Digraph* digraph;
    488485    public:
    489486
     
    492489      InArcIt(Invalid i) : Arc(i) { }
    493490
    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) {}
     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) {}
    501498
    502499      InArcIt& operator++() {
    503         _graph->nextIn(*this);
     500        digraph->nextIn(*this);
    504501        return *this;
    505502      }
     
    509506
    510507    class EdgeIt : public Parent::Edge {
    511       const Graph* _graph;
     508      const Digraph* digraph;
    512509    public:
    513510
     
    516513      EdgeIt(Invalid i) : Edge(i) { }
    517514
    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) { }
     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) { }
    524521
    525522      EdgeIt& operator++() {
    526         _graph->next(*this);
    527         return *this;
    528       }
    529 
    530     };
    531 
    532     class IncEdgeIt : public Parent::Edge {
     523        digraph->next(*this);
     524        return *this;
     525      }
     526
     527    };
     528
     529    class IncArcIt : public Parent::Edge {
    533530      friend class GraphExtender;
    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);
     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);
    553550        return *this;
    554551      }
     
    558555    ///
    559556    /// Returns the base node (ie. the source in this case) of the iterator
    560     Node baseNode(const OutArcIt &arc) const {
    561       return Parent::source(static_cast<const Arc&>(arc));
     557    Node baseNode(const OutArcIt &e) const {
     558      return Parent::source(static_cast<const Arc&>(e));
    562559    }
    563560    /// \brief Running node of the iterator
     
    565562    /// Returns the running node (ie. the target in this case) of the
    566563    /// iterator
    567     Node runningNode(const OutArcIt &arc) const {
    568       return Parent::target(static_cast<const Arc&>(arc));
     564    Node runningNode(const OutArcIt &e) const {
     565      return Parent::target(static_cast<const Arc&>(e));
    569566    }
    570567
     
    572569    ///
    573570    /// Returns the base node (ie. the target in this case) of the iterator
    574     Node baseNode(const InArcIt &arc) const {
    575       return Parent::target(static_cast<const Arc&>(arc));
     571    Node baseNode(const InArcIt &e) const {
     572      return Parent::target(static_cast<const Arc&>(e));
    576573    }
    577574    /// \brief Running node of the iterator
     
    579576    /// Returns the running node (ie. the source in this case) of the
    580577    /// iterator
    581     Node runningNode(const InArcIt &arc) const {
    582       return Parent::source(static_cast<const Arc&>(arc));
     578    Node runningNode(const InArcIt &e) const {
     579      return Parent::source(static_cast<const Arc&>(e));
    583580    }
    584581
     
    586583    ///
    587584    /// Returns the base node of the iterator
    588     Node baseNode(const IncEdgeIt &edge) const {
    589       return edge._direction ? source(edge) : target(edge);
     585    Node baseNode(const IncArcIt &e) const {
     586      return e.direction ? source(e) : target(e);
    590587    }
    591588    /// Running node of the iterator
    592589    ///
    593590    /// Returns the running node of the iterator
    594     Node runningNode(const IncEdgeIt &edge) const {
    595       return edge._direction ? target(edge) : source(edge);
     591    Node runningNode(const IncArcIt &e) const {
     592      return e.direction ? target(e) : source(e);
    596593    }
    597594
     
    600597    template <typename _Value>
    601598    class NodeMap
    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) {}
     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) {}
    611608
    612609      NodeMap& operator=(const NodeMap& cmap) {
     
    624621    template <typename _Value>
    625622    class ArcMap
    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) {}
     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) {}
    635632
    636633      ArcMap& operator=(const ArcMap& cmap) {
     
    648645    template <typename _Value>
    649646    class EdgeMap
    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) {}
     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) {}
    660657
    661658      EdgeMap& operator=(const EdgeMap& cmap) {
     
    696693    }
    697694
    698     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
    699     void build(const Graph& graph, NodeRefMap& nodeRef,
     695    template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>
     696    void build(const Digraph& digraph, NodeRefMap& nodeRef,
    700697               EdgeRefMap& edgeRef) {
    701       Parent::build(graph, nodeRef, edgeRef);
     698      Parent::build(digraph, nodeRef, edgeRef);
    702699      notifier(Node()).build();
    703700      notifier(Edge()).build();
     
    724721
    725722    void erase(const Edge& edge) {
    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);
     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);
    730727      notifier(Edge()).erase(edge);
    731728      Parent::erase(edge);
Note: See TracChangeset for help on using the changeset viewer.