COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/edge_set.h @ 603:425cc8328c0e

Last change on this file since 603:425cc8328c0e was 512:9b9ffe7d9b75, checked in by Balazs Dezso <deba@…>, 11 years ago

Fixes for MSVC 2008 in grap_adaptors.h and edge_set.h (#194)

Several renamings and changes in adaptors and edge sets

File size: 36.1 KB
RevLine 
[468]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
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_EDGE_SET_H
20#define LEMON_EDGE_SET_H
21
22#include <lemon/core.h>
23#include <lemon/bits/edge_set_extender.h>
24
25/// \ingroup semi_adaptors
26/// \file
27/// \brief ArcSet and EdgeSet classes.
28///
29/// Graphs which use another graph's node-set as own.
30namespace lemon {
31
[512]32  template <typename GR>
[468]33  class ListArcSetBase {
34  public:
35
[512]36    typedef GR Graph;
37    typedef typename GR::Node Node;
38    typedef typename GR::NodeIt NodeIt;
[468]39
40  protected:
41
42    struct NodeT {
43      int first_out, first_in;
44      NodeT() : first_out(-1), first_in(-1) {}
45    };
46
[512]47    typedef typename ItemSetTraits<GR, Node>::
[468]48    template Map<NodeT>::Type NodesImplBase;
49
[512]50    NodesImplBase* _nodes;
[468]51
52    struct ArcT {
53      Node source, target;
54      int next_out, next_in;
55      int prev_out, prev_in;
56      ArcT() : prev_out(-1), prev_in(-1) {}
57    };
58
59    std::vector<ArcT> arcs;
60
61    int first_arc;
62    int first_free_arc;
63
[512]64    const GR* _graph;
[468]65
[512]66    void initalize(const GR& graph, NodesImplBase& nodes) {
67      _graph = &graph;
68      _nodes = &nodes;
[468]69    }
70
71  public:
72
73    class Arc {
[512]74      friend class ListArcSetBase<GR>;
[468]75    protected:
76      Arc(int _id) : id(_id) {}
77      int id;
78    public:
79      Arc() {}
80      Arc(Invalid) : id(-1) {}
81      bool operator==(const Arc& arc) const { return id == arc.id; }
82      bool operator!=(const Arc& arc) const { return id != arc.id; }
83      bool operator<(const Arc& arc) const { return id < arc.id; }
84    };
85
86    ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
87
88    Arc addArc(const Node& u, const Node& v) {
89      int n;
90      if (first_free_arc == -1) {
91        n = arcs.size();
92        arcs.push_back(ArcT());
93      } else {
94        n = first_free_arc;
95        first_free_arc = arcs[first_free_arc].next_in;
96      }
[512]97      arcs[n].next_in = (*_nodes)[v].first_in;
98      if ((*_nodes)[v].first_in != -1) {
99        arcs[(*_nodes)[v].first_in].prev_in = n;
[468]100      }
[512]101      (*_nodes)[v].first_in = n;
102      arcs[n].next_out = (*_nodes)[u].first_out;
103      if ((*_nodes)[u].first_out != -1) {
104        arcs[(*_nodes)[u].first_out].prev_out = n;
[468]105      }
[512]106      (*_nodes)[u].first_out = n;
[468]107      arcs[n].source = u;
108      arcs[n].target = v;
109      return Arc(n);
110    }
111
112    void erase(const Arc& arc) {
113      int n = arc.id;
114      if (arcs[n].prev_in != -1) {
115        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
116      } else {
[512]117        (*_nodes)[arcs[n].target].first_in = arcs[n].next_in;
[468]118      }
119      if (arcs[n].next_in != -1) {
120        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
121      }
122
123      if (arcs[n].prev_out != -1) {
124        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
125      } else {
[512]126        (*_nodes)[arcs[n].source].first_out = arcs[n].next_out;
[468]127      }
128      if (arcs[n].next_out != -1) {
129        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
130      }
131
132    }
133
134    void clear() {
135      Node node;
136      for (first(node); node != INVALID; next(node)) {
[512]137        (*_nodes)[node].first_in = -1;
138        (*_nodes)[node].first_out = -1;
[468]139      }
140      arcs.clear();
141      first_arc = -1;
142      first_free_arc = -1;
143    }
144
145    void first(Node& node) const {
[512]146      _graph->first(node);
[468]147    }
148
149    void next(Node& node) const {
[512]150      _graph->next(node);
[468]151    }
152
153    void first(Arc& arc) const {
154      Node node;
155      first(node);
[512]156      while (node != INVALID && (*_nodes)[node].first_in == -1) {
[468]157        next(node);
158      }
[512]159      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
[468]160    }
161
162    void next(Arc& arc) const {
163      if (arcs[arc.id].next_in != -1) {
164        arc.id = arcs[arc.id].next_in;
165      } else {
166        Node node = arcs[arc.id].target;
167        next(node);
[512]168        while (node != INVALID && (*_nodes)[node].first_in == -1) {
[468]169          next(node);
170        }
[512]171        arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
[468]172      }
173    }
174
175    void firstOut(Arc& arc, const Node& node) const {
[512]176      arc.id = (*_nodes)[node].first_out;
[468]177    }
178
179    void nextOut(Arc& arc) const {
180      arc.id = arcs[arc.id].next_out;
181    }
182
183    void firstIn(Arc& arc, const Node& node) const {
[512]184      arc.id = (*_nodes)[node].first_in;
[468]185    }
186
187    void nextIn(Arc& arc) const {
188      arc.id = arcs[arc.id].next_in;
189    }
190
[512]191    int id(const Node& node) const { return _graph->id(node); }
[468]192    int id(const Arc& arc) const { return arc.id; }
193
[512]194    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
[468]195    Arc arcFromId(int ix) const { return Arc(ix); }
196
[512]197    int maxNodeId() const { return _graph->maxNodeId(); };
[468]198    int maxArcId() const { return arcs.size() - 1; }
199
200    Node source(const Arc& arc) const { return arcs[arc.id].source;}
201    Node target(const Arc& arc) const { return arcs[arc.id].target;}
202
[512]203    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
[468]204
205    NodeNotifier& notifier(Node) const {
[512]206      return _graph->notifier(Node());
[468]207    }
208
[512]209    template <typename V>
210    class NodeMap : public GR::template NodeMap<V> {
[468]211    public:
212
[512]213      typedef typename GR::template NodeMap<V> Parent;
[468]214
[512]215      explicit NodeMap(const ListArcSetBase<GR>& arcset)
216        : Parent(*arcset._graph) {}
[468]217
[512]218      NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
219        : Parent(*arcset._graph, value) {}
[468]220
221      NodeMap& operator=(const NodeMap& cmap) {
222        return operator=<NodeMap>(cmap);
223      }
224
225      template <typename CMap>
226      NodeMap& operator=(const CMap& cmap) {
227        Parent::operator=(cmap);
228        return *this;
229      }
230    };
231
232  };
233
234  /// \ingroup semi_adaptors
235  ///
236  /// \brief Digraph using a node set of another digraph or graph and
237  /// an own arc set.
238  ///
239  /// This structure can be used to establish another directed graph
240  /// over a node set of an existing one. This class uses the same
241  /// Node type as the underlying graph, and each valid node of the
242  /// original graph is valid in this arc set, therefore the node
243  /// objects of the original graph can be used directly with this
244  /// class. The node handling functions (id handling, observing, and
245  /// iterators) works equivalently as in the original graph.
246  ///
247  /// This implementation is based on doubly-linked lists, from each
248  /// node the outgoing and the incoming arcs make up lists, therefore
249  /// one arc can be erased in constant time. It also makes possible,
250  /// that node can be removed from the underlying graph, in this case
251  /// all arcs incident to the given node is erased from the arc set.
252  ///
[512]253  /// \param GR The type of the graph which shares its node set with
[468]254  /// this class. Its interface must conform to the
255  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
256  /// concept.
257  ///
258  /// This class is fully conform to the \ref concepts::Digraph
259  /// "Digraph" concept.
[512]260  template <typename GR>
261  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
[468]262
263  public:
264
[512]265    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
[468]266
267    typedef typename Parent::Node Node;
268    typedef typename Parent::Arc Arc;
269
[512]270    typedef GR Graph;
[468]271
272
273    typedef typename Parent::NodesImplBase NodesImplBase;
274
275    void eraseNode(const Node& node) {
276      Arc arc;
277      Parent::firstOut(arc, node);
278      while (arc != INVALID ) {
279        erase(arc);
280        Parent::firstOut(arc, node);
281      }
282
283      Parent::firstIn(arc, node);
284      while (arc != INVALID ) {
285        erase(arc);
286        Parent::firstIn(arc, node);
287      }
288    }
289
290    void clearNodes() {
291      Parent::clear();
292    }
293
294    class NodesImpl : public NodesImplBase {
295    public:
296      typedef NodesImplBase Parent;
297
[512]298      NodesImpl(const GR& graph, ListArcSet& arcset)
[468]299        : Parent(graph), _arcset(arcset) {}
300
301      virtual ~NodesImpl() {}
302
303    protected:
304
305      virtual void erase(const Node& node) {
306        _arcset.eraseNode(node);
307        Parent::erase(node);
308      }
309      virtual void erase(const std::vector<Node>& nodes) {
310        for (int i = 0; i < int(nodes.size()); ++i) {
311          _arcset.eraseNode(nodes[i]);
312        }
313        Parent::erase(nodes);
314      }
315      virtual void clear() {
316        _arcset.clearNodes();
317        Parent::clear();
318      }
319
320    private:
321      ListArcSet& _arcset;
322    };
323
[512]324    NodesImpl _nodes;
[468]325
326  public:
327
328    /// \brief Constructor of the ArcSet.
329    ///
330    /// Constructor of the ArcSet.
[512]331    ListArcSet(const GR& graph) : _nodes(graph, *this) {
332      Parent::initalize(graph, _nodes);
[468]333    }
334
335    /// \brief Add a new arc to the digraph.
336    ///
337    /// Add a new arc to the digraph with source node \c s
338    /// and target node \c t.
339    /// \return the new arc.
340    Arc addArc(const Node& s, const Node& t) {
341      return Parent::addArc(s, t);
342    }
343
344    /// \brief Erase an arc from the digraph.
345    ///
346    /// Erase an arc \c a from the digraph.
347    void erase(const Arc& a) {
348      return Parent::erase(a);
349    }
350
351  };
352
[512]353  template <typename GR>
[468]354  class ListEdgeSetBase {
355  public:
356
[512]357    typedef GR Graph;
358    typedef typename GR::Node Node;
359    typedef typename GR::NodeIt NodeIt;
[468]360
361  protected:
362
363    struct NodeT {
364      int first_out;
365      NodeT() : first_out(-1) {}
366    };
367
[512]368    typedef typename ItemSetTraits<GR, Node>::
[468]369    template Map<NodeT>::Type NodesImplBase;
370
[512]371    NodesImplBase* _nodes;
[468]372
373    struct ArcT {
374      Node target;
375      int prev_out, next_out;
376      ArcT() : prev_out(-1), next_out(-1) {}
377    };
378
379    std::vector<ArcT> arcs;
380
381    int first_arc;
382    int first_free_arc;
383
[512]384    const GR* _graph;
[468]385
[512]386    void initalize(const GR& graph, NodesImplBase& nodes) {
387      _graph = &graph;
388      _nodes = &nodes;
[468]389    }
390
391  public:
392
393    class Edge {
394      friend class ListEdgeSetBase;
395    protected:
396
397      int id;
398      explicit Edge(int _id) { id = _id;}
399
400    public:
401      Edge() {}
402      Edge (Invalid) { id = -1; }
403      bool operator==(const Edge& arc) const {return id == arc.id;}
404      bool operator!=(const Edge& arc) const {return id != arc.id;}
405      bool operator<(const Edge& arc) const {return id < arc.id;}
406    };
407
408    class Arc {
409      friend class ListEdgeSetBase;
410    protected:
411      Arc(int _id) : id(_id) {}
412      int id;
413    public:
414      operator Edge() const { return edgeFromId(id / 2); }
415
416      Arc() {}
417      Arc(Invalid) : id(-1) {}
418      bool operator==(const Arc& arc) const { return id == arc.id; }
419      bool operator!=(const Arc& arc) const { return id != arc.id; }
420      bool operator<(const Arc& arc) const { return id < arc.id; }
421    };
422
423    ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
424
425    Edge addEdge(const Node& u, const Node& v) {
426      int n;
427
428      if (first_free_arc == -1) {
429        n = arcs.size();
430        arcs.push_back(ArcT());
431        arcs.push_back(ArcT());
432      } else {
433        n = first_free_arc;
434        first_free_arc = arcs[n].next_out;
435      }
436
437      arcs[n].target = u;
438      arcs[n | 1].target = v;
439
[512]440      arcs[n].next_out = (*_nodes)[v].first_out;
441      if ((*_nodes)[v].first_out != -1) {
442        arcs[(*_nodes)[v].first_out].prev_out = n;
[468]443      }
[512]444      (*_nodes)[v].first_out = n;
[468]445      arcs[n].prev_out = -1;
446
[512]447      if ((*_nodes)[u].first_out != -1) {
448        arcs[(*_nodes)[u].first_out].prev_out = (n | 1);
[468]449      }
[512]450      arcs[n | 1].next_out = (*_nodes)[u].first_out;
451      (*_nodes)[u].first_out = (n | 1);
[468]452      arcs[n | 1].prev_out = -1;
453
454      return Edge(n / 2);
455    }
456
457    void erase(const Edge& arc) {
458      int n = arc.id * 2;
459
460      if (arcs[n].next_out != -1) {
461        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
462      }
463
464      if (arcs[n].prev_out != -1) {
465        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
466      } else {
[512]467        (*_nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
[468]468      }
469
470      if (arcs[n | 1].next_out != -1) {
471        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
472      }
473
474      if (arcs[n | 1].prev_out != -1) {
475        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
476      } else {
[512]477        (*_nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
[468]478      }
479
480      arcs[n].next_out = first_free_arc;
481      first_free_arc = n;
482
483    }
484
485    void clear() {
486      Node node;
487      for (first(node); node != INVALID; next(node)) {
[512]488        (*_nodes)[node].first_out = -1;
[468]489      }
490      arcs.clear();
491      first_arc = -1;
492      first_free_arc = -1;
493    }
494
495    void first(Node& node) const {
[512]496      _graph->first(node);
[468]497    }
498
499    void next(Node& node) const {
[512]500      _graph->next(node);
[468]501    }
502
503    void first(Arc& arc) const {
504      Node node;
505      first(node);
[512]506      while (node != INVALID && (*_nodes)[node].first_out == -1) {
[468]507        next(node);
508      }
[512]509      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
[468]510    }
511
512    void next(Arc& arc) const {
513      if (arcs[arc.id].next_out != -1) {
514        arc.id = arcs[arc.id].next_out;
515      } else {
516        Node node = arcs[arc.id ^ 1].target;
517        next(node);
[512]518        while(node != INVALID && (*_nodes)[node].first_out == -1) {
[468]519          next(node);
520        }
[512]521        arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
[468]522      }
523    }
524
525    void first(Edge& edge) const {
526      Node node;
527      first(node);
528      while (node != INVALID) {
[512]529        edge.id = (*_nodes)[node].first_out;
[468]530        while ((edge.id & 1) != 1) {
531          edge.id = arcs[edge.id].next_out;
532        }
533        if (edge.id != -1) {
534          edge.id /= 2;
535          return;
536        }
537        next(node);
538      }
539      edge.id = -1;
540    }
541
542    void next(Edge& edge) const {
543      Node node = arcs[edge.id * 2].target;
544      edge.id = arcs[(edge.id * 2) | 1].next_out;
545      while ((edge.id & 1) != 1) {
546        edge.id = arcs[edge.id].next_out;
547      }
548      if (edge.id != -1) {
549        edge.id /= 2;
550        return;
551      }
552      next(node);
553      while (node != INVALID) {
[512]554        edge.id = (*_nodes)[node].first_out;
[468]555        while ((edge.id & 1) != 1) {
556          edge.id = arcs[edge.id].next_out;
557        }
558        if (edge.id != -1) {
559          edge.id /= 2;
560          return;
561        }
562        next(node);
563      }
564      edge.id = -1;
565    }
566
567    void firstOut(Arc& arc, const Node& node) const {
[512]568      arc.id = (*_nodes)[node].first_out;
[468]569    }
570
571    void nextOut(Arc& arc) const {
572      arc.id = arcs[arc.id].next_out;
573    }
574
575    void firstIn(Arc& arc, const Node& node) const {
[512]576      arc.id = (((*_nodes)[node].first_out) ^ 1);
[468]577      if (arc.id == -2) arc.id = -1;
578    }
579
580    void nextIn(Arc& arc) const {
581      arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
582      if (arc.id == -2) arc.id = -1;
583    }
584
585    void firstInc(Edge &arc, bool& dir, const Node& node) const {
[512]586      int de = (*_nodes)[node].first_out;
[468]587      if (de != -1 ) {
588        arc.id = de / 2;
589        dir = ((de & 1) == 1);
590      } else {
591        arc.id = -1;
592        dir = true;
593      }
594    }
595    void nextInc(Edge &arc, bool& dir) const {
596      int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
597      if (de != -1 ) {
598        arc.id = de / 2;
599        dir = ((de & 1) == 1);
600      } else {
601        arc.id = -1;
602        dir = true;
603      }
604    }
605
606    static bool direction(Arc arc) {
607      return (arc.id & 1) == 1;
608    }
609
610    static Arc direct(Edge edge, bool dir) {
611      return Arc(edge.id * 2 + (dir ? 1 : 0));
612    }
613
[512]614    int id(const Node& node) const { return _graph->id(node); }
[468]615    static int id(Arc e) { return e.id; }
616    static int id(Edge e) { return e.id; }
617
[512]618    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
[468]619    static Arc arcFromId(int id) { return Arc(id);}
620    static Edge edgeFromId(int id) { return Edge(id);}
621
[512]622    int maxNodeId() const { return _graph->maxNodeId(); };
[468]623    int maxEdgeId() const { return arcs.size() / 2 - 1; }
624    int maxArcId() const { return arcs.size()-1; }
625
626    Node source(Arc e) const { return arcs[e.id ^ 1].target; }
627    Node target(Arc e) const { return arcs[e.id].target; }
628
629    Node u(Edge e) const { return arcs[2 * e.id].target; }
630    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
631
[512]632    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
[468]633
634    NodeNotifier& notifier(Node) const {
[512]635      return _graph->notifier(Node());
[468]636    }
637
[512]638    template <typename V>
639    class NodeMap : public GR::template NodeMap<V> {
[468]640    public:
641
[512]642      typedef typename GR::template NodeMap<V> Parent;
[468]643
[512]644      explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
645        : Parent(*arcset._graph) {}
[468]646
[512]647      NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
648        : Parent(*arcset._graph, value) {}
[468]649
650      NodeMap& operator=(const NodeMap& cmap) {
651        return operator=<NodeMap>(cmap);
652      }
653
654      template <typename CMap>
655      NodeMap& operator=(const CMap& cmap) {
656        Parent::operator=(cmap);
657        return *this;
658      }
659    };
660
661  };
662
663  /// \ingroup semi_adaptors
664  ///
665  /// \brief Graph using a node set of another digraph or graph and an
666  /// own edge set.
667  ///
668  /// This structure can be used to establish another graph over a
669  /// node set of an existing one. This class uses the same Node type
670  /// as the underlying graph, and each valid node of the original
671  /// graph is valid in this arc set, therefore the node objects of
672  /// the original graph can be used directly with this class. The
673  /// node handling functions (id handling, observing, and iterators)
674  /// works equivalently as in the original graph.
675  ///
676  /// This implementation is based on doubly-linked lists, from each
677  /// node the incident edges make up lists, therefore one edge can be
678  /// erased in constant time. It also makes possible, that node can
679  /// be removed from the underlying graph, in this case all edges
680  /// incident to the given node is erased from the arc set.
681  ///
[512]682  /// \param GR The type of the graph which shares its node set
[468]683  /// with this class. Its interface must conform to the
684  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
685  /// concept.
686  ///
687  /// This class is fully conform to the \ref concepts::Graph "Graph"
688  /// concept.
[512]689  template <typename GR>
690  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
[468]691
692  public:
693
[512]694    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
[468]695
696    typedef typename Parent::Node Node;
697    typedef typename Parent::Arc Arc;
698    typedef typename Parent::Edge Edge;
699
[512]700    typedef GR Graph;
[468]701
702
703    typedef typename Parent::NodesImplBase NodesImplBase;
704
705    void eraseNode(const Node& node) {
706      Arc arc;
707      Parent::firstOut(arc, node);
708      while (arc != INVALID ) {
709        erase(arc);
710        Parent::firstOut(arc, node);
711      }
712
713    }
714
715    void clearNodes() {
716      Parent::clear();
717    }
718
719    class NodesImpl : public NodesImplBase {
720    public:
721      typedef NodesImplBase Parent;
722
[512]723      NodesImpl(const GR& graph, ListEdgeSet& arcset)
[468]724        : Parent(graph), _arcset(arcset) {}
725
726      virtual ~NodesImpl() {}
727
728    protected:
729
730      virtual void erase(const Node& node) {
731        _arcset.eraseNode(node);
732        Parent::erase(node);
733      }
734      virtual void erase(const std::vector<Node>& nodes) {
735        for (int i = 0; i < int(nodes.size()); ++i) {
736          _arcset.eraseNode(nodes[i]);
737        }
738        Parent::erase(nodes);
739      }
740      virtual void clear() {
741        _arcset.clearNodes();
742        Parent::clear();
743      }
744
745    private:
746      ListEdgeSet& _arcset;
747    };
748
[512]749    NodesImpl _nodes;
[468]750
751  public:
752
753    /// \brief Constructor of the EdgeSet.
754    ///
755    /// Constructor of the EdgeSet.
[512]756    ListEdgeSet(const GR& graph) : _nodes(graph, *this) {
757      Parent::initalize(graph, _nodes);
[468]758    }
759
760    /// \brief Add a new edge to the graph.
761    ///
762    /// Add a new edge to the graph with node \c u
763    /// and node \c v endpoints.
764    /// \return the new edge.
765    Edge addEdge(const Node& u, const Node& v) {
766      return Parent::addEdge(u, v);
767    }
768
769    /// \brief Erase an edge from the graph.
770    ///
771    /// Erase the edge \c e from the graph.
772    void erase(const Edge& e) {
773      return Parent::erase(e);
774    }
775
776  };
777
[512]778  template <typename GR>
[468]779  class SmartArcSetBase {
780  public:
781
[512]782    typedef GR Graph;
[468]783    typedef typename Graph::Node Node;
784    typedef typename Graph::NodeIt NodeIt;
785
786  protected:
787
788    struct NodeT {
789      int first_out, first_in;
790      NodeT() : first_out(-1), first_in(-1) {}
791    };
792
[512]793    typedef typename ItemSetTraits<GR, Node>::
[468]794    template Map<NodeT>::Type NodesImplBase;
795
[512]796    NodesImplBase* _nodes;
[468]797
798    struct ArcT {
799      Node source, target;
800      int next_out, next_in;
801      ArcT() {}
802    };
803
804    std::vector<ArcT> arcs;
805
[512]806    const GR* _graph;
[468]807
[512]808    void initalize(const GR& graph, NodesImplBase& nodes) {
809      _graph = &graph;
810      _nodes = &nodes;
[468]811    }
812
813  public:
814
815    class Arc {
[512]816      friend class SmartArcSetBase<GR>;
[468]817    protected:
818      Arc(int _id) : id(_id) {}
819      int id;
820    public:
821      Arc() {}
822      Arc(Invalid) : id(-1) {}
823      bool operator==(const Arc& arc) const { return id == arc.id; }
824      bool operator!=(const Arc& arc) const { return id != arc.id; }
825      bool operator<(const Arc& arc) const { return id < arc.id; }
826    };
827
828    SmartArcSetBase() {}
829
830    Arc addArc(const Node& u, const Node& v) {
831      int n = arcs.size();
832      arcs.push_back(ArcT());
[512]833      arcs[n].next_in = (*_nodes)[v].first_in;
834      (*_nodes)[v].first_in = n;
835      arcs[n].next_out = (*_nodes)[u].first_out;
836      (*_nodes)[u].first_out = n;
[468]837      arcs[n].source = u;
838      arcs[n].target = v;
839      return Arc(n);
840    }
841
842    void clear() {
843      Node node;
844      for (first(node); node != INVALID; next(node)) {
[512]845        (*_nodes)[node].first_in = -1;
846        (*_nodes)[node].first_out = -1;
[468]847      }
848      arcs.clear();
849    }
850
851    void first(Node& node) const {
[512]852      _graph->first(node);
[468]853    }
854
855    void next(Node& node) const {
[512]856      _graph->next(node);
[468]857    }
858
859    void first(Arc& arc) const {
860      arc.id = arcs.size() - 1;
861    }
862
863    void next(Arc& arc) const {
864      --arc.id;
865    }
866
867    void firstOut(Arc& arc, const Node& node) const {
[512]868      arc.id = (*_nodes)[node].first_out;
[468]869    }
870
871    void nextOut(Arc& arc) const {
872      arc.id = arcs[arc.id].next_out;
873    }
874
875    void firstIn(Arc& arc, const Node& node) const {
[512]876      arc.id = (*_nodes)[node].first_in;
[468]877    }
878
879    void nextIn(Arc& arc) const {
880      arc.id = arcs[arc.id].next_in;
881    }
882
[512]883    int id(const Node& node) const { return _graph->id(node); }
[468]884    int id(const Arc& arc) const { return arc.id; }
885
[512]886    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
[468]887    Arc arcFromId(int ix) const { return Arc(ix); }
888
[512]889    int maxNodeId() const { return _graph->maxNodeId(); };
[468]890    int maxArcId() const { return arcs.size() - 1; }
891
892    Node source(const Arc& arc) const { return arcs[arc.id].source;}
893    Node target(const Arc& arc) const { return arcs[arc.id].target;}
894
[512]895    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
[468]896
897    NodeNotifier& notifier(Node) const {
[512]898      return _graph->notifier(Node());
[468]899    }
900
[512]901    template <typename V>
902    class NodeMap : public GR::template NodeMap<V> {
[468]903    public:
904
[512]905      typedef typename GR::template NodeMap<V> Parent;
[468]906
[512]907      explicit NodeMap(const SmartArcSetBase<GR>& arcset)
908        : Parent(*arcset._graph) { }
[468]909
[512]910      NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
911        : Parent(*arcset._graph, value) { }
[468]912
913      NodeMap& operator=(const NodeMap& cmap) {
914        return operator=<NodeMap>(cmap);
915      }
916
917      template <typename CMap>
918      NodeMap& operator=(const CMap& cmap) {
919        Parent::operator=(cmap);
920        return *this;
921      }
922    };
923
924  };
925
926
927  /// \ingroup semi_adaptors
928  ///
929  /// \brief Digraph using a node set of another digraph or graph and
930  /// an own arc set.
931  ///
932  /// This structure can be used to establish another directed graph
933  /// over a node set of an existing one. This class uses the same
934  /// Node type as the underlying graph, and each valid node of the
935  /// original graph is valid in this arc set, therefore the node
936  /// objects of the original graph can be used directly with this
937  /// class. The node handling functions (id handling, observing, and
938  /// iterators) works equivalently as in the original graph.
939  ///
[512]940  /// \param GR The type of the graph which shares its node set with
[468]941  /// this class. Its interface must conform to the
942  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
943  /// concept.
944  ///
945  /// This implementation is slightly faster than the \c ListArcSet,
946  /// because it uses continuous storage for arcs and it uses just
947  /// single-linked lists for enumerate outgoing and incoming
948  /// arcs. Therefore the arcs cannot be erased from the arc sets.
949  ///
950  /// \warning If a node is erased from the underlying graph and this
951  /// node is the source or target of one arc in the arc set, then
952  /// the arc set is invalidated, and it cannot be used anymore. The
953  /// validity can be checked with the \c valid() member function.
954  ///
955  /// This class is fully conform to the \ref concepts::Digraph
956  /// "Digraph" concept.
[512]957  template <typename GR>
958  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
[468]959
960  public:
961
[512]962    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
[468]963
964    typedef typename Parent::Node Node;
965    typedef typename Parent::Arc Arc;
966
[512]967    typedef GR Graph;
[468]968
969  protected:
970
971    typedef typename Parent::NodesImplBase NodesImplBase;
972
973    void eraseNode(const Node& node) {
974      if (typename Parent::InArcIt(*this, node) == INVALID &&
975          typename Parent::OutArcIt(*this, node) == INVALID) {
976        return;
977      }
978      throw typename NodesImplBase::Notifier::ImmediateDetach();
979    }
980
981    void clearNodes() {
982      Parent::clear();
983    }
984
985    class NodesImpl : public NodesImplBase {
986    public:
987      typedef NodesImplBase Parent;
988
[512]989      NodesImpl(const GR& graph, SmartArcSet& arcset)
[468]990        : Parent(graph), _arcset(arcset) {}
991
992      virtual ~NodesImpl() {}
993
994      bool attached() const {
995        return Parent::attached();
996      }
997
998    protected:
999
1000      virtual void erase(const Node& node) {
1001        try {
1002          _arcset.eraseNode(node);
1003          Parent::erase(node);
1004        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
1005          Parent::clear();
1006          throw;
1007        }
1008      }
1009      virtual void erase(const std::vector<Node>& nodes) {
1010        try {
1011          for (int i = 0; i < int(nodes.size()); ++i) {
1012            _arcset.eraseNode(nodes[i]);
1013          }
1014          Parent::erase(nodes);
1015        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
1016          Parent::clear();
1017          throw;
1018        }
1019      }
1020      virtual void clear() {
1021        _arcset.clearNodes();
1022        Parent::clear();
1023      }
1024
1025    private:
1026      SmartArcSet& _arcset;
1027    };
1028
[512]1029    NodesImpl _nodes;
[468]1030
1031  public:
1032
1033    /// \brief Constructor of the ArcSet.
1034    ///
1035    /// Constructor of the ArcSet.
[512]1036    SmartArcSet(const GR& graph) : _nodes(graph, *this) {
1037      Parent::initalize(graph, _nodes);
[468]1038    }
1039
1040    /// \brief Add a new arc to the digraph.
1041    ///
1042    /// Add a new arc to the digraph with source node \c s
1043    /// and target node \c t.
1044    /// \return the new arc.
1045    Arc addArc(const Node& s, const Node& t) {
1046      return Parent::addArc(s, t);
1047    }
1048
1049    /// \brief Validity check
1050    ///
1051    /// This functions gives back false if the ArcSet is
1052    /// invalidated. It occurs when a node in the underlying graph is
1053    /// erased and it is not isolated in the ArcSet.
1054    bool valid() const {
[512]1055      return _nodes.attached();
[468]1056    }
1057
1058  };
1059
1060
[512]1061  template <typename GR>
[468]1062  class SmartEdgeSetBase {
1063  public:
1064
[512]1065    typedef GR Graph;
1066    typedef typename GR::Node Node;
1067    typedef typename GR::NodeIt NodeIt;
[468]1068
1069  protected:
1070
1071    struct NodeT {
1072      int first_out;
1073      NodeT() : first_out(-1) {}
1074    };
1075
[512]1076    typedef typename ItemSetTraits<GR, Node>::
[468]1077    template Map<NodeT>::Type NodesImplBase;
1078
[512]1079    NodesImplBase* _nodes;
[468]1080
1081    struct ArcT {
1082      Node target;
1083      int next_out;
1084      ArcT() {}
1085    };
1086
1087    std::vector<ArcT> arcs;
1088
[512]1089    const GR* _graph;
[468]1090
[512]1091    void initalize(const GR& graph, NodesImplBase& nodes) {
1092      _graph = &graph;
1093      _nodes = &nodes;
[468]1094    }
1095
1096  public:
1097
1098    class Edge {
1099      friend class SmartEdgeSetBase;
1100    protected:
1101
1102      int id;
1103      explicit Edge(int _id) { id = _id;}
1104
1105    public:
1106      Edge() {}
1107      Edge (Invalid) { id = -1; }
1108      bool operator==(const Edge& arc) const {return id == arc.id;}
1109      bool operator!=(const Edge& arc) const {return id != arc.id;}
1110      bool operator<(const Edge& arc) const {return id < arc.id;}
1111    };
1112
1113    class Arc {
1114      friend class SmartEdgeSetBase;
1115    protected:
1116      Arc(int _id) : id(_id) {}
1117      int id;
1118    public:
1119      operator Edge() const { return edgeFromId(id / 2); }
1120
1121      Arc() {}
1122      Arc(Invalid) : id(-1) {}
1123      bool operator==(const Arc& arc) const { return id == arc.id; }
1124      bool operator!=(const Arc& arc) const { return id != arc.id; }
1125      bool operator<(const Arc& arc) const { return id < arc.id; }
1126    };
1127
1128    SmartEdgeSetBase() {}
1129
1130    Edge addEdge(const Node& u, const Node& v) {
1131      int n = arcs.size();
1132      arcs.push_back(ArcT());
1133      arcs.push_back(ArcT());
1134
1135      arcs[n].target = u;
1136      arcs[n | 1].target = v;
1137
[512]1138      arcs[n].next_out = (*_nodes)[v].first_out;
1139      (*_nodes)[v].first_out = n;
[468]1140
[512]1141      arcs[n | 1].next_out = (*_nodes)[u].first_out;
1142      (*_nodes)[u].first_out = (n | 1);
[468]1143
1144      return Edge(n / 2);
1145    }
1146
1147    void clear() {
1148      Node node;
1149      for (first(node); node != INVALID; next(node)) {
[512]1150        (*_nodes)[node].first_out = -1;
[468]1151      }
1152      arcs.clear();
1153    }
1154
1155    void first(Node& node) const {
[512]1156      _graph->first(node);
[468]1157    }
1158
1159    void next(Node& node) const {
[512]1160      _graph->next(node);
[468]1161    }
1162
1163    void first(Arc& arc) const {
1164      arc.id = arcs.size() - 1;
1165    }
1166
1167    void next(Arc& arc) const {
1168      --arc.id;
1169    }
1170
1171    void first(Edge& arc) const {
1172      arc.id = arcs.size() / 2 - 1;
1173    }
1174
1175    void next(Edge& arc) const {
1176      --arc.id;
1177    }
1178
1179    void firstOut(Arc& arc, const Node& node) const {
[512]1180      arc.id = (*_nodes)[node].first_out;
[468]1181    }
1182
1183    void nextOut(Arc& arc) const {
1184      arc.id = arcs[arc.id].next_out;
1185    }
1186
1187    void firstIn(Arc& arc, const Node& node) const {
[512]1188      arc.id = (((*_nodes)[node].first_out) ^ 1);
[468]1189      if (arc.id == -2) arc.id = -1;
1190    }
1191
1192    void nextIn(Arc& arc) const {
1193      arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
1194      if (arc.id == -2) arc.id = -1;
1195    }
1196
1197    void firstInc(Edge &arc, bool& dir, const Node& node) const {
[512]1198      int de = (*_nodes)[node].first_out;
[468]1199      if (de != -1 ) {
1200        arc.id = de / 2;
1201        dir = ((de & 1) == 1);
1202      } else {
1203        arc.id = -1;
1204        dir = true;
1205      }
1206    }
1207    void nextInc(Edge &arc, bool& dir) const {
1208      int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
1209      if (de != -1 ) {
1210        arc.id = de / 2;
1211        dir = ((de & 1) == 1);
1212      } else {
1213        arc.id = -1;
1214        dir = true;
1215      }
1216    }
1217
1218    static bool direction(Arc arc) {
1219      return (arc.id & 1) == 1;
1220    }
1221
1222    static Arc direct(Edge edge, bool dir) {
1223      return Arc(edge.id * 2 + (dir ? 1 : 0));
1224    }
1225
[512]1226    int id(Node node) const { return _graph->id(node); }
[468]1227    static int id(Arc arc) { return arc.id; }
1228    static int id(Edge arc) { return arc.id; }
1229
[512]1230    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
[468]1231    static Arc arcFromId(int id) { return Arc(id); }
1232    static Edge edgeFromId(int id) { return Edge(id);}
1233
[512]1234    int maxNodeId() const { return _graph->maxNodeId(); };
[468]1235    int maxArcId() const { return arcs.size() - 1; }
1236    int maxEdgeId() const { return arcs.size() / 2 - 1; }
1237
1238    Node source(Arc e) const { return arcs[e.id ^ 1].target; }
1239    Node target(Arc e) const { return arcs[e.id].target; }
1240
1241    Node u(Edge e) const { return arcs[2 * e.id].target; }
1242    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
1243
[512]1244    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
[468]1245
1246    NodeNotifier& notifier(Node) const {
[512]1247      return _graph->notifier(Node());
[468]1248    }
1249
[512]1250    template <typename V>
1251    class NodeMap : public GR::template NodeMap<V> {
[468]1252    public:
1253
[512]1254      typedef typename GR::template NodeMap<V> Parent;
[468]1255
[512]1256      explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
1257        : Parent(*arcset._graph) { }
[468]1258
[512]1259      NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
1260        : Parent(*arcset._graph, value) { }
[468]1261
1262      NodeMap& operator=(const NodeMap& cmap) {
1263        return operator=<NodeMap>(cmap);
1264      }
1265
1266      template <typename CMap>
1267      NodeMap& operator=(const CMap& cmap) {
1268        Parent::operator=(cmap);
1269        return *this;
1270      }
1271    };
1272
1273  };
1274
1275  /// \ingroup semi_adaptors
1276  ///
1277  /// \brief Graph using a node set of another digraph or graph and an
1278  /// own edge set.
1279  ///
1280  /// This structure can be used to establish another graph over a
1281  /// node set of an existing one. This class uses the same Node type
1282  /// as the underlying graph, and each valid node of the original
1283  /// graph is valid in this arc set, therefore the node objects of
1284  /// the original graph can be used directly with this class. The
1285  /// node handling functions (id handling, observing, and iterators)
1286  /// works equivalently as in the original graph.
1287  ///
[512]1288  /// \param GR The type of the graph which shares its node set
[468]1289  /// with this class. Its interface must conform to the
1290  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
1291  ///  concept.
1292  ///
1293  /// This implementation is slightly faster than the \c ListEdgeSet,
1294  /// because it uses continuous storage for edges and it uses just
1295  /// single-linked lists for enumerate incident edges. Therefore the
1296  /// edges cannot be erased from the edge sets.
1297  ///
1298  /// \warning If a node is erased from the underlying graph and this
1299  /// node is incident to one edge in the edge set, then the edge set
1300  /// is invalidated, and it cannot be used anymore. The validity can
1301  /// be checked with the \c valid() member function.
1302  ///
1303  /// This class is fully conform to the \ref concepts::Graph
1304  /// "Graph" concept.
[512]1305  template <typename GR>
1306  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
[468]1307
1308  public:
1309
[512]1310    typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
[468]1311
1312    typedef typename Parent::Node Node;
1313    typedef typename Parent::Arc Arc;
1314    typedef typename Parent::Edge Edge;
1315
[512]1316    typedef GR Graph;
[468]1317
1318  protected:
1319
1320    typedef typename Parent::NodesImplBase NodesImplBase;
1321
1322    void eraseNode(const Node& node) {
1323      if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
1324        return;
1325      }
1326      throw typename NodesImplBase::Notifier::ImmediateDetach();
1327    }
1328
1329    void clearNodes() {
1330      Parent::clear();
1331    }
1332
1333    class NodesImpl : public NodesImplBase {
1334    public:
1335      typedef NodesImplBase Parent;
1336
[512]1337      NodesImpl(const GR& graph, SmartEdgeSet& arcset)
[468]1338        : Parent(graph), _arcset(arcset) {}
1339
1340      virtual ~NodesImpl() {}
1341
1342      bool attached() const {
1343        return Parent::attached();
1344      }
1345
1346    protected:
1347
1348      virtual void erase(const Node& node) {
1349        try {
1350          _arcset.eraseNode(node);
1351          Parent::erase(node);
1352        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
1353          Parent::clear();
1354          throw;
1355        }
1356      }
1357      virtual void erase(const std::vector<Node>& nodes) {
1358        try {
1359          for (int i = 0; i < int(nodes.size()); ++i) {
1360            _arcset.eraseNode(nodes[i]);
1361          }
1362          Parent::erase(nodes);
1363        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
1364          Parent::clear();
1365          throw;
1366        }
1367      }
1368      virtual void clear() {
1369        _arcset.clearNodes();
1370        Parent::clear();
1371      }
1372
1373    private:
1374      SmartEdgeSet& _arcset;
1375    };
1376
[512]1377    NodesImpl _nodes;
[468]1378
1379  public:
1380
1381    /// \brief Constructor of the EdgeSet.
1382    ///
1383    /// Constructor of the EdgeSet.
[512]1384    SmartEdgeSet(const GR& graph) : _nodes(graph, *this) {
1385      Parent::initalize(graph, _nodes);
[468]1386    }
1387
1388    /// \brief Add a new edge to the graph.
1389    ///
1390    /// Add a new edge to the graph with node \c u
1391    /// and node \c v endpoints.
1392    /// \return the new edge.
1393    Edge addEdge(const Node& u, const Node& v) {
1394      return Parent::addEdge(u, v);
1395    }
1396
1397    /// \brief Validity check
1398    ///
1399    /// This functions gives back false if the EdgeSet is
1400    /// invalidated. It occurs when a node in the underlying graph is
1401    /// erased and it is not isolated in the EdgeSet.
1402    bool valid() const {
[512]1403      return _nodes.attached();
[468]1404    }
1405
1406  };
1407
1408}
1409
1410#endif
Note: See TracBrowser for help on using the repository browser.