COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/edge_set.h @ 642:111698359429

Last change on this file since 642:111698359429 was 617:4137ef9aacc6, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Fix and uniform the usage of Graph and Parent typedefs (#268)

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