COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/graph_extender.h @ 535:6a17a722b50e

Last change on this file since 535:6a17a722b50e was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 11 years ago

Happy New Year again

  • update the copyright headers + run the source unifier
File size: 17.2 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[57]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[57]4 *
[440]5 * Copyright (C) 2003-2009
[57]6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_BITS_GRAPH_EXTENDER_H
20#define LEMON_BITS_GRAPH_EXTENDER_H
21
[220]22#include <lemon/core.h>
[57]23
24#include <lemon/bits/map_extender.h>
25#include <lemon/bits/default_map.h>
26
27#include <lemon/concept_check.h>
28#include <lemon/concepts/maps.h>
29
[314]30//\ingroup graphbits
31//\file
[361]32//\brief Extenders for the graph types
[57]33namespace lemon {
34
[314]35  // \ingroup graphbits
36  //
[361]37  // \brief Extender for the digraph implementations
[57]38  template <typename Base>
39  class DigraphExtender : public Base {
40  public:
41
42    typedef Base Parent;
43    typedef DigraphExtender Digraph;
44
45    // Base extensions
46
47    typedef typename Parent::Node Node;
48    typedef typename Parent::Arc Arc;
49
50    int maxId(Node) const {
51      return Parent::maxNodeId();
52    }
53
54    int maxId(Arc) const {
55      return Parent::maxArcId();
56    }
57
58    Node fromId(int id, Node) const {
59      return Parent::nodeFromId(id);
60    }
61
62    Arc fromId(int id, Arc) const {
63      return Parent::arcFromId(id);
64    }
65
[78]66    Node oppositeNode(const Node &node, const Arc &arc) const {
67      if (node == Parent::source(arc))
[209]68        return Parent::target(arc);
[78]69      else if(node == Parent::target(arc))
[209]70        return Parent::source(arc);
[57]71      else
[209]72        return INVALID;
[57]73    }
74
75    // Alterable extension
76
77    typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
78    typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
79
80
81  protected:
82
83    mutable NodeNotifier node_notifier;
84    mutable ArcNotifier arc_notifier;
85
86  public:
87
88    NodeNotifier& notifier(Node) const {
89      return node_notifier;
90    }
[209]91
[57]92    ArcNotifier& notifier(Arc) const {
93      return arc_notifier;
94    }
95
[209]96    class NodeIt : public Node {
[78]97      const Digraph* _digraph;
[57]98    public:
99
100      NodeIt() {}
101
102      NodeIt(Invalid i) : Node(i) { }
103
[78]104      explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
[209]105        _digraph->first(static_cast<Node&>(*this));
[57]106      }
107
[209]108      NodeIt(const Digraph& digraph, const Node& node)
109        : Node(node), _digraph(&digraph) {}
[57]110
[209]111      NodeIt& operator++() {
112        _digraph->next(*this);
113        return *this;
[57]114      }
115
116    };
117
118
[209]119    class ArcIt : public Arc {
[78]120      const Digraph* _digraph;
[57]121    public:
122
123      ArcIt() { }
124
125      ArcIt(Invalid i) : Arc(i) { }
126
[78]127      explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
[209]128        _digraph->first(static_cast<Arc&>(*this));
[57]129      }
130
[209]131      ArcIt(const Digraph& digraph, const Arc& arc) :
132        Arc(arc), _digraph(&digraph) { }
[57]133
[209]134      ArcIt& operator++() {
135        _digraph->next(*this);
136        return *this;
[57]137      }
138
139    };
140
141
[209]142    class OutArcIt : public Arc {
[78]143      const Digraph* _digraph;
[57]144    public:
145
146      OutArcIt() { }
147
148      OutArcIt(Invalid i) : Arc(i) { }
149
[209]150      OutArcIt(const Digraph& digraph, const Node& node)
151        : _digraph(&digraph) {
152        _digraph->firstOut(*this, node);
[57]153      }
154
[209]155      OutArcIt(const Digraph& digraph, const Arc& arc)
156        : Arc(arc), _digraph(&digraph) {}
[57]157
[209]158      OutArcIt& operator++() {
159        _digraph->nextOut(*this);
160        return *this;
[57]161      }
162
163    };
164
165
[209]166    class InArcIt : public Arc {
[78]167      const Digraph* _digraph;
[57]168    public:
169
170      InArcIt() { }
171
172      InArcIt(Invalid i) : Arc(i) { }
173
[209]174      InArcIt(const Digraph& digraph, const Node& node)
175        : _digraph(&digraph) {
176        _digraph->firstIn(*this, node);
[57]177      }
178
[209]179      InArcIt(const Digraph& digraph, const Arc& arc) :
180        Arc(arc), _digraph(&digraph) {}
[57]181
[209]182      InArcIt& operator++() {
183        _digraph->nextIn(*this);
184        return *this;
[57]185      }
186
187    };
188
[314]189    // \brief Base node of the iterator
190    //
191    // Returns the base node (i.e. the source in this case) of the iterator
[78]192    Node baseNode(const OutArcIt &arc) const {
193      return Parent::source(arc);
[57]194    }
[314]195    // \brief Running node of the iterator
196    //
197    // Returns the running node (i.e. the target in this case) of the
198    // iterator
[78]199    Node runningNode(const OutArcIt &arc) const {
200      return Parent::target(arc);
[57]201    }
202
[314]203    // \brief Base node of the iterator
204    //
205    // Returns the base node (i.e. the target in this case) of the iterator
[78]206    Node baseNode(const InArcIt &arc) const {
207      return Parent::target(arc);
[57]208    }
[314]209    // \brief Running node of the iterator
210    //
211    // Returns the running node (i.e. the source in this case) of the
212    // iterator
[78]213    Node runningNode(const InArcIt &arc) const {
214      return Parent::source(arc);
[57]215    }
216
[209]217
[57]218    template <typename _Value>
[209]219    class NodeMap
[57]220      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
221    public:
222      typedef DigraphExtender Digraph;
223      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
224
[209]225      explicit NodeMap(const Digraph& digraph)
226        : Parent(digraph) {}
227      NodeMap(const Digraph& digraph, const _Value& value)
228        : Parent(digraph, value) {}
[57]229
[263]230    private:
[57]231      NodeMap& operator=(const NodeMap& cmap) {
[209]232        return operator=<NodeMap>(cmap);
[57]233      }
234
235      template <typename CMap>
236      NodeMap& operator=(const CMap& cmap) {
237        Parent::operator=(cmap);
[209]238        return *this;
[57]239      }
240
241    };
242
243    template <typename _Value>
[209]244    class ArcMap
[57]245      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
246    public:
247      typedef DigraphExtender Digraph;
248      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
249
[209]250      explicit ArcMap(const Digraph& digraph)
251        : Parent(digraph) {}
252      ArcMap(const Digraph& digraph, const _Value& value)
253        : Parent(digraph, value) {}
[57]254
[263]255    private:
[57]256      ArcMap& operator=(const ArcMap& cmap) {
[209]257        return operator=<ArcMap>(cmap);
[57]258      }
259
260      template <typename CMap>
261      ArcMap& operator=(const CMap& cmap) {
262        Parent::operator=(cmap);
[209]263        return *this;
[57]264      }
265    };
266
267
268    Node addNode() {
269      Node node = Parent::addNode();
270      notifier(Node()).add(node);
271      return node;
272    }
[209]273
[57]274    Arc addArc(const Node& from, const Node& to) {
275      Arc arc = Parent::addArc(from, to);
276      notifier(Arc()).add(arc);
277      return arc;
278    }
279
280    void clear() {
281      notifier(Arc()).clear();
282      notifier(Node()).clear();
283      Parent::clear();
284    }
285
286    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
287    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
288      Parent::build(digraph, nodeRef, arcRef);
289      notifier(Node()).build();
290      notifier(Arc()).build();
291    }
292
293    void erase(const Node& node) {
294      Arc arc;
295      Parent::firstOut(arc, node);
296      while (arc != INVALID ) {
[209]297        erase(arc);
298        Parent::firstOut(arc, node);
299      }
[57]300
301      Parent::firstIn(arc, node);
302      while (arc != INVALID ) {
[209]303        erase(arc);
304        Parent::firstIn(arc, node);
[57]305      }
306
307      notifier(Node()).erase(node);
308      Parent::erase(node);
309    }
[209]310
[57]311    void erase(const Arc& arc) {
312      notifier(Arc()).erase(arc);
313      Parent::erase(arc);
314    }
315
316    DigraphExtender() {
317      node_notifier.setContainer(*this);
318      arc_notifier.setContainer(*this);
[209]319    }
320
[57]321
322    ~DigraphExtender() {
323      arc_notifier.clear();
324      node_notifier.clear();
325    }
326  };
327
[314]328  // \ingroup _graphbits
329  //
330  // \brief Extender for the Graphs
[209]331  template <typename Base>
[57]332  class GraphExtender : public Base {
333  public:
[209]334
[57]335    typedef Base Parent;
[78]336    typedef GraphExtender Graph;
[57]337
[77]338    typedef True UndirectedTag;
339
[57]340    typedef typename Parent::Node Node;
341    typedef typename Parent::Arc Arc;
342    typedef typename Parent::Edge Edge;
343
[209]344    // Graph extension
[57]345
346    int maxId(Node) const {
347      return Parent::maxNodeId();
348    }
349
350    int maxId(Arc) const {
351      return Parent::maxArcId();
352    }
353
354    int maxId(Edge) const {
355      return Parent::maxEdgeId();
356    }
357
358    Node fromId(int id, Node) const {
359      return Parent::nodeFromId(id);
360    }
361
362    Arc fromId(int id, Arc) const {
363      return Parent::arcFromId(id);
364    }
365
366    Edge fromId(int id, Edge) const {
367      return Parent::edgeFromId(id);
368    }
369
370    Node oppositeNode(const Node &n, const Edge &e) const {
[125]371      if( n == Parent::u(e))
[209]372        return Parent::v(e);
[125]373      else if( n == Parent::v(e))
[209]374        return Parent::u(e);
[57]375      else
[209]376        return INVALID;
[57]377    }
378
[78]379    Arc oppositeArc(const Arc &arc) const {
380      return Parent::direct(arc, !Parent::direction(arc));
[57]381    }
382
383    using Parent::direct;
[78]384    Arc direct(const Edge &edge, const Node &node) const {
[125]385      return Parent::direct(edge, Parent::u(edge) == node);
[57]386    }
387
388    // Alterable extension
389
390    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
391    typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
392    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
393
394
395  protected:
396
397    mutable NodeNotifier node_notifier;
398    mutable ArcNotifier arc_notifier;
399    mutable EdgeNotifier edge_notifier;
400
401  public:
402
403    NodeNotifier& notifier(Node) const {
404      return node_notifier;
405    }
[209]406
[57]407    ArcNotifier& notifier(Arc) const {
408      return arc_notifier;
409    }
410
411    EdgeNotifier& notifier(Edge) const {
412      return edge_notifier;
413    }
414
415
416
[209]417    class NodeIt : public Node {
[78]418      const Graph* _graph;
[57]419    public:
420
421      NodeIt() {}
422
423      NodeIt(Invalid i) : Node(i) { }
424
[78]425      explicit NodeIt(const Graph& graph) : _graph(&graph) {
[209]426        _graph->first(static_cast<Node&>(*this));
[57]427      }
428
[209]429      NodeIt(const Graph& graph, const Node& node)
430        : Node(node), _graph(&graph) {}
[57]431
[209]432      NodeIt& operator++() {
433        _graph->next(*this);
434        return *this;
[57]435      }
436
437    };
438
439
[209]440    class ArcIt : public Arc {
[78]441      const Graph* _graph;
[57]442    public:
443
444      ArcIt() { }
445
446      ArcIt(Invalid i) : Arc(i) { }
447
[78]448      explicit ArcIt(const Graph& graph) : _graph(&graph) {
[209]449        _graph->first(static_cast<Arc&>(*this));
[57]450      }
451
[209]452      ArcIt(const Graph& graph, const Arc& arc) :
453        Arc(arc), _graph(&graph) { }
[57]454
[209]455      ArcIt& operator++() {
456        _graph->next(*this);
457        return *this;
[57]458      }
459
460    };
461
462
[209]463    class OutArcIt : public Arc {
[78]464      const Graph* _graph;
[57]465    public:
466
467      OutArcIt() { }
468
469      OutArcIt(Invalid i) : Arc(i) { }
470
[209]471      OutArcIt(const Graph& graph, const Node& node)
472        : _graph(&graph) {
473        _graph->firstOut(*this, node);
[57]474      }
475
[209]476      OutArcIt(const Graph& graph, const Arc& arc)
477        : Arc(arc), _graph(&graph) {}
[57]478
[209]479      OutArcIt& operator++() {
480        _graph->nextOut(*this);
481        return *this;
[57]482      }
483
484    };
485
486
[209]487    class InArcIt : public Arc {
[78]488      const Graph* _graph;
[57]489    public:
490
491      InArcIt() { }
492
493      InArcIt(Invalid i) : Arc(i) { }
494
[209]495      InArcIt(const Graph& graph, const Node& node)
496        : _graph(&graph) {
497        _graph->firstIn(*this, node);
[57]498      }
499
[209]500      InArcIt(const Graph& graph, const Arc& arc) :
501        Arc(arc), _graph(&graph) {}
[57]502
[209]503      InArcIt& operator++() {
504        _graph->nextIn(*this);
505        return *this;
[57]506      }
507
508    };
509
510
[209]511    class EdgeIt : public Parent::Edge {
[78]512      const Graph* _graph;
[57]513    public:
514
515      EdgeIt() { }
516
517      EdgeIt(Invalid i) : Edge(i) { }
518
[78]519      explicit EdgeIt(const Graph& graph) : _graph(&graph) {
[209]520        _graph->first(static_cast<Edge&>(*this));
[57]521      }
522
[209]523      EdgeIt(const Graph& graph, const Edge& edge) :
524        Edge(edge), _graph(&graph) { }
[57]525
[209]526      EdgeIt& operator++() {
527        _graph->next(*this);
528        return *this;
[57]529      }
530
531    };
532
[78]533    class IncEdgeIt : public Parent::Edge {
[57]534      friend class GraphExtender;
[78]535      const Graph* _graph;
536      bool _direction;
[57]537    public:
538
[78]539      IncEdgeIt() { }
[57]540
[78]541      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
[57]542
[78]543      IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
[209]544        _graph->firstInc(*this, _direction, node);
[57]545      }
546
[78]547      IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
[209]548        : _graph(&graph), Edge(edge) {
549        _direction = (_graph->source(edge) == node);
[57]550      }
551
[78]552      IncEdgeIt& operator++() {
[209]553        _graph->nextInc(*this, _direction);
554        return *this;
[57]555      }
556    };
557
[314]558    // \brief Base node of the iterator
559    //
560    // Returns the base node (ie. the source in this case) of the iterator
[78]561    Node baseNode(const OutArcIt &arc) const {
562      return Parent::source(static_cast<const Arc&>(arc));
[57]563    }
[314]564    // \brief Running node of the iterator
565    //
566    // Returns the running node (ie. the target in this case) of the
567    // iterator
[78]568    Node runningNode(const OutArcIt &arc) const {
569      return Parent::target(static_cast<const Arc&>(arc));
[57]570    }
571
[314]572    // \brief Base node of the iterator
573    //
574    // Returns the base node (ie. the target in this case) of the iterator
[78]575    Node baseNode(const InArcIt &arc) const {
576      return Parent::target(static_cast<const Arc&>(arc));
[57]577    }
[314]578    // \brief Running node of the iterator
579    //
580    // Returns the running node (ie. the source in this case) of the
581    // iterator
[78]582    Node runningNode(const InArcIt &arc) const {
583      return Parent::source(static_cast<const Arc&>(arc));
[57]584    }
585
[314]586    // Base node of the iterator
587    //
588    // Returns the base node of the iterator
[78]589    Node baseNode(const IncEdgeIt &edge) const {
[125]590      return edge._direction ? u(edge) : v(edge);
[57]591    }
[314]592    // Running node of the iterator
593    //
594    // Returns the running node of the iterator
[78]595    Node runningNode(const IncEdgeIt &edge) const {
[125]596      return edge._direction ? v(edge) : u(edge);
[57]597    }
598
599    // Mappable extension
600
601    template <typename _Value>
[209]602    class NodeMap
[78]603      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
[57]604    public:
[78]605      typedef GraphExtender Graph;
606      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
[57]607
[209]608      NodeMap(const Graph& graph)
609        : Parent(graph) {}
610      NodeMap(const Graph& graph, const _Value& value)
611        : Parent(graph, value) {}
[57]612
[263]613    private:
[57]614      NodeMap& operator=(const NodeMap& cmap) {
[209]615        return operator=<NodeMap>(cmap);
[57]616      }
617
618      template <typename CMap>
619      NodeMap& operator=(const CMap& cmap) {
620        Parent::operator=(cmap);
[209]621        return *this;
[57]622      }
623
624    };
625
626    template <typename _Value>
[209]627    class ArcMap
[78]628      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
[57]629    public:
[78]630      typedef GraphExtender Graph;
631      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
[57]632
[209]633      ArcMap(const Graph& graph)
634        : Parent(graph) {}
635      ArcMap(const Graph& graph, const _Value& value)
636        : Parent(graph, value) {}
[57]637
[263]638    private:
[57]639      ArcMap& operator=(const ArcMap& cmap) {
[209]640        return operator=<ArcMap>(cmap);
[57]641      }
642
643      template <typename CMap>
644      ArcMap& operator=(const CMap& cmap) {
645        Parent::operator=(cmap);
[209]646        return *this;
[57]647      }
648    };
649
650
651    template <typename _Value>
[209]652    class EdgeMap
[78]653      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
[57]654    public:
[78]655      typedef GraphExtender Graph;
656      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
[57]657
[209]658      EdgeMap(const Graph& graph)
659        : Parent(graph) {}
[57]660
[209]661      EdgeMap(const Graph& graph, const _Value& value)
662        : Parent(graph, value) {}
[57]663
[263]664    private:
[57]665      EdgeMap& operator=(const EdgeMap& cmap) {
[209]666        return operator=<EdgeMap>(cmap);
[57]667      }
668
669      template <typename CMap>
670      EdgeMap& operator=(const CMap& cmap) {
671        Parent::operator=(cmap);
[209]672        return *this;
[57]673      }
674
675    };
676
677    // Alteration extension
678
679    Node addNode() {
680      Node node = Parent::addNode();
681      notifier(Node()).add(node);
682      return node;
683    }
684
685    Edge addEdge(const Node& from, const Node& to) {
686      Edge edge = Parent::addEdge(from, to);
687      notifier(Edge()).add(edge);
688      std::vector<Arc> ev;
689      ev.push_back(Parent::direct(edge, true));
[209]690      ev.push_back(Parent::direct(edge, false));
[57]691      notifier(Arc()).add(ev);
692      return edge;
693    }
[209]694
[57]695    void clear() {
696      notifier(Arc()).clear();
697      notifier(Edge()).clear();
698      notifier(Node()).clear();
699      Parent::clear();
700    }
701
[78]702    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
[209]703    void build(const Graph& graph, NodeRefMap& nodeRef,
[57]704               EdgeRefMap& edgeRef) {
[78]705      Parent::build(graph, nodeRef, edgeRef);
[57]706      notifier(Node()).build();
707      notifier(Edge()).build();
708      notifier(Arc()).build();
709    }
710
711    void erase(const Node& node) {
712      Arc arc;
713      Parent::firstOut(arc, node);
714      while (arc != INVALID ) {
[209]715        erase(arc);
716        Parent::firstOut(arc, node);
717      }
[57]718
719      Parent::firstIn(arc, node);
720      while (arc != INVALID ) {
[209]721        erase(arc);
722        Parent::firstIn(arc, node);
[57]723      }
724
725      notifier(Node()).erase(node);
726      Parent::erase(node);
727    }
728
729    void erase(const Edge& edge) {
[78]730      std::vector<Arc> av;
731      av.push_back(Parent::direct(edge, true));
[209]732      av.push_back(Parent::direct(edge, false));
[78]733      notifier(Arc()).erase(av);
[57]734      notifier(Edge()).erase(edge);
735      Parent::erase(edge);
736    }
737
738    GraphExtender() {
[209]739      node_notifier.setContainer(*this);
[57]740      arc_notifier.setContainer(*this);
741      edge_notifier.setContainer(*this);
[209]742    }
[57]743
744    ~GraphExtender() {
745      edge_notifier.clear();
746      arc_notifier.clear();
[209]747      node_notifier.clear();
748    }
[57]749
750  };
751
752}
753
754#endif
Note: See TracBrowser for help on using the repository browser.