COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/edge_set.h @ 468:68fe66e2b34a

Last change on this file since 468:68fe66e2b34a was 468:68fe66e2b34a, checked in by Balazs Dezso <deba@…>, 11 years ago

ArcSet? and EdgeSet? ports from SVN 3489 (ticket #67)

File size: 36.3 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 _Graph>
33  class ListArcSetBase {
34  public:
35
36    typedef _Graph Graph;
37    typedef typename Graph::Node Node;
38    typedef typename Graph::NodeIt NodeIt;
39
40  protected:
41
42    struct NodeT {
43      int first_out, first_in;
44      NodeT() : first_out(-1), first_in(-1) {}
45    };
46
47    typedef typename ItemSetTraits<Graph, Node>::
48    template Map<NodeT>::Type NodesImplBase;
49
50    NodesImplBase* nodes;
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
64    const Graph* graph;
65
66    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
67      graph = &_graph;
68      nodes = &_nodes;
69    }
70
71  public:
72
73    class Arc {
74      friend class ListArcSetBase<Graph>;
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      }
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;
100      }
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;
105      }
106      (*nodes)[u].first_out = n;
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 {
117        (*nodes)[arcs[n].target].first_in = arcs[n].next_in;
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 {
126        (*nodes)[arcs[n].source].first_out = arcs[n].next_out;
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)) {
137        (*nodes)[node].first_in = -1;
138        (*nodes)[node].first_out = -1;
139      }
140      arcs.clear();
141      first_arc = -1;
142      first_free_arc = -1;
143    }
144
145    void first(Node& node) const {
146      graph->first(node);
147    }
148
149    void next(Node& node) const {
150      graph->next(node);
151    }
152
153    void first(Arc& arc) const {
154      Node node;
155      first(node);
156      while (node != INVALID && (*nodes)[node].first_in == -1) {
157        next(node);
158      }
159      arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
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);
168        while (node != INVALID && (*nodes)[node].first_in == -1) {
169          next(node);
170        }
171        arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
172      }
173    }
174
175    void firstOut(Arc& arc, const Node& node) const {
176      arc.id = (*nodes)[node].first_out;
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 {
184      arc.id = (*nodes)[node].first_in;
185    }
186
187    void nextIn(Arc& arc) const {
188      arc.id = arcs[arc.id].next_in;
189    }
190
191    int id(const Node& node) const { return graph->id(node); }
192    int id(const Arc& arc) const { return arc.id; }
193
194    Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
195    Arc arcFromId(int ix) const { return Arc(ix); }
196
197    int maxNodeId() const { return graph->maxNodeId(); };
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
203    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
204
205    NodeNotifier& notifier(Node) const {
206      return graph->notifier(Node());
207    }
208
209    template <typename _Value>
210    class NodeMap : public Graph::template NodeMap<_Value> {
211    public:
212
213      typedef typename _Graph::template NodeMap<_Value> Parent;
214
215      explicit NodeMap(const ListArcSetBase<Graph>& arcset)
216        : Parent(*arcset.graph) {}
217
218      NodeMap(const ListArcSetBase<Graph>& arcset, const _Value& value)
219        : Parent(*arcset.graph, value) {}
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  ///
253  /// \param _Graph The type of the graph which shares its node set with
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.
260  template <typename _Graph>
261  class ListArcSet : public ArcSetExtender<ListArcSetBase<_Graph> > {
262
263  public:
264
265    typedef ArcSetExtender<ListArcSetBase<_Graph> > Parent;
266
267    typedef typename Parent::Node Node;
268    typedef typename Parent::Arc Arc;
269
270    typedef _Graph Graph;
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
298      NodesImpl(const Graph& graph, ListArcSet& arcset)
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
324    NodesImpl nodes;
325
326  public:
327
328    /// \brief Constructor of the ArcSet.
329    ///
330    /// Constructor of the ArcSet.
331    ListArcSet(const Graph& graph) : nodes(graph, *this) {
332      Parent::initalize(graph, nodes);
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
353  template <typename _Graph>
354  class ListEdgeSetBase {
355  public:
356
357    typedef _Graph Graph;
358    typedef typename Graph::Node Node;
359    typedef typename Graph::NodeIt NodeIt;
360
361  protected:
362
363    struct NodeT {
364      int first_out;
365      NodeT() : first_out(-1) {}
366    };
367
368    typedef typename ItemSetTraits<Graph, Node>::
369    template Map<NodeT>::Type NodesImplBase;
370
371    NodesImplBase* nodes;
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
384    const Graph* graph;
385
386    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
387      graph = &_graph;
388      nodes = &_nodes;
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
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;
443      }
444      (*nodes)[v].first_out = n;
445      arcs[n].prev_out = -1;
446
447      if ((*nodes)[u].first_out != -1) {
448        arcs[(*nodes)[u].first_out].prev_out = (n | 1);
449      }
450      arcs[n | 1].next_out = (*nodes)[u].first_out;
451      (*nodes)[u].first_out = (n | 1);
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 {
467        (*nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
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 {
477        (*nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
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)) {
488        (*nodes)[node].first_out = -1;
489      }
490      arcs.clear();
491      first_arc = -1;
492      first_free_arc = -1;
493    }
494
495    void first(Node& node) const {
496      graph->first(node);
497    }
498
499    void next(Node& node) const {
500      graph->next(node);
501    }
502
503    void first(Arc& arc) const {
504      Node node;
505      first(node);
506      while (node != INVALID && (*nodes)[node].first_out == -1) {
507        next(node);
508      }
509      arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
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);
518        while(node != INVALID && (*nodes)[node].first_out == -1) {
519          next(node);
520        }
521        arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
522      }
523    }
524
525    void first(Edge& edge) const {
526      Node node;
527      first(node);
528      while (node != INVALID) {
529        edge.id = (*nodes)[node].first_out;
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) {
554        edge.id = (*nodes)[node].first_out;
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 {
568      arc.id = (*nodes)[node].first_out;
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 {
576      arc.id = (((*nodes)[node].first_out) ^ 1);
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 {
586      int de = (*nodes)[node].first_out;
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
614    int id(const Node& node) const { return graph->id(node); }
615    static int id(Arc e) { return e.id; }
616    static int id(Edge e) { return e.id; }
617
618    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
619    static Arc arcFromId(int id) { return Arc(id);}
620    static Edge edgeFromId(int id) { return Edge(id);}
621
622    int maxNodeId() const { return graph->maxNodeId(); };
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
632    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
633
634    NodeNotifier& notifier(Node) const {
635      return graph->notifier(Node());
636    }
637
638    template <typename _Value>
639    class NodeMap : public Graph::template NodeMap<_Value> {
640    public:
641
642      typedef typename _Graph::template NodeMap<_Value> Parent;
643
644      explicit NodeMap(const ListEdgeSetBase<Graph>& arcset)
645        : Parent(*arcset.graph) {}
646
647      NodeMap(const ListEdgeSetBase<Graph>& arcset, const _Value& value)
648        : Parent(*arcset.graph, value) {}
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  ///
682  /// \param _Graph The type of the graph which shares its node set
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.
689  template <typename _Graph>
690  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
691
692  public:
693
694    typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
695
696    typedef typename Parent::Node Node;
697    typedef typename Parent::Arc Arc;
698    typedef typename Parent::Edge Edge;
699
700    typedef _Graph Graph;
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
723      NodesImpl(const Graph& graph, ListEdgeSet& arcset)
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
749    NodesImpl nodes;
750
751  public:
752
753    /// \brief Constructor of the EdgeSet.
754    ///
755    /// Constructor of the EdgeSet.
756    ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
757      Parent::initalize(graph, nodes);
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
778  template <typename _Graph>
779  class SmartArcSetBase {
780  public:
781
782    typedef _Graph Graph;
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
793    typedef typename ItemSetTraits<Graph, Node>::
794    template Map<NodeT>::Type NodesImplBase;
795
796    NodesImplBase* nodes;
797
798    struct ArcT {
799      Node source, target;
800      int next_out, next_in;
801      ArcT() {}
802    };
803
804    std::vector<ArcT> arcs;
805
806    const Graph* graph;
807
808    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
809      graph = &_graph;
810      nodes = &_nodes;
811    }
812
813  public:
814
815    class Arc {
816      friend class SmartArcSetBase<Graph>;
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());
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;
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)) {
845        (*nodes)[node].first_in = -1;
846        (*nodes)[node].first_out = -1;
847      }
848      arcs.clear();
849    }
850
851    void first(Node& node) const {
852      graph->first(node);
853    }
854
855    void next(Node& node) const {
856      graph->next(node);
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 {
868      arc.id = (*nodes)[node].first_out;
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 {
876      arc.id = (*nodes)[node].first_in;
877    }
878
879    void nextIn(Arc& arc) const {
880      arc.id = arcs[arc.id].next_in;
881    }
882
883    int id(const Node& node) const { return graph->id(node); }
884    int id(const Arc& arc) const { return arc.id; }
885
886    Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
887    Arc arcFromId(int ix) const { return Arc(ix); }
888
889    int maxNodeId() const { return graph->maxNodeId(); };
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
895    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
896
897    NodeNotifier& notifier(Node) const {
898      return graph->notifier(Node());
899    }
900
901    template <typename _Value>
902    class NodeMap : public Graph::template NodeMap<_Value> {
903    public:
904
905      typedef typename _Graph::template NodeMap<_Value> Parent;
906
907      explicit NodeMap(const SmartArcSetBase<Graph>& arcset)
908        : Parent(*arcset.graph) { }
909
910      NodeMap(const SmartArcSetBase<Graph>& arcset, const _Value& value)
911        : Parent(*arcset.graph, value) { }
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  ///
940  /// \param _Graph The type of the graph which shares its node set with
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.
957  template <typename _Graph>
958  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<_Graph> > {
959
960  public:
961
962    typedef ArcSetExtender<SmartArcSetBase<_Graph> > Parent;
963
964    typedef typename Parent::Node Node;
965    typedef typename Parent::Arc Arc;
966
967    typedef _Graph Graph;
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
989      NodesImpl(const Graph& graph, SmartArcSet& arcset)
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
1029    NodesImpl nodes;
1030
1031  public:
1032
1033    /// \brief Constructor of the ArcSet.
1034    ///
1035    /// Constructor of the ArcSet.
1036    SmartArcSet(const Graph& graph) : nodes(graph, *this) {
1037      Parent::initalize(graph, nodes);
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 {
1055      return nodes.attached();
1056    }
1057
1058  };
1059
1060
1061  template <typename _Graph>
1062  class SmartEdgeSetBase {
1063  public:
1064
1065    typedef _Graph Graph;
1066    typedef typename Graph::Node Node;
1067    typedef typename Graph::NodeIt NodeIt;
1068
1069  protected:
1070
1071    struct NodeT {
1072      int first_out;
1073      NodeT() : first_out(-1) {}
1074    };
1075
1076    typedef typename ItemSetTraits<Graph, Node>::
1077    template Map<NodeT>::Type NodesImplBase;
1078
1079    NodesImplBase* nodes;
1080
1081    struct ArcT {
1082      Node target;
1083      int next_out;
1084      ArcT() {}
1085    };
1086
1087    std::vector<ArcT> arcs;
1088
1089    const Graph* graph;
1090
1091    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
1092      graph = &_graph;
1093      nodes = &_nodes;
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
1138      arcs[n].next_out = (*nodes)[v].first_out;
1139      (*nodes)[v].first_out = n;
1140
1141      arcs[n | 1].next_out = (*nodes)[u].first_out;
1142      (*nodes)[u].first_out = (n | 1);
1143
1144      return Edge(n / 2);
1145    }
1146
1147    void clear() {
1148      Node node;
1149      for (first(node); node != INVALID; next(node)) {
1150        (*nodes)[node].first_out = -1;
1151      }
1152      arcs.clear();
1153    }
1154
1155    void first(Node& node) const {
1156      graph->first(node);
1157    }
1158
1159    void next(Node& node) const {
1160      graph->next(node);
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 {
1180      arc.id = (*nodes)[node].first_out;
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 {
1188      arc.id = (((*nodes)[node].first_out) ^ 1);
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 {
1198      int de = (*nodes)[node].first_out;
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
1226    int id(Node node) const { return graph->id(node); }
1227    static int id(Arc arc) { return arc.id; }
1228    static int id(Edge arc) { return arc.id; }
1229
1230    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
1231    static Arc arcFromId(int id) { return Arc(id); }
1232    static Edge edgeFromId(int id) { return Edge(id);}
1233
1234    int maxNodeId() const { return graph->maxNodeId(); };
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
1244    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1245
1246    NodeNotifier& notifier(Node) const {
1247      return graph->notifier(Node());
1248    }
1249
1250    template <typename _Value>
1251    class NodeMap : public Graph::template NodeMap<_Value> {
1252    public:
1253
1254      typedef typename _Graph::template NodeMap<_Value> Parent;
1255
1256      explicit NodeMap(const SmartEdgeSetBase<Graph>& arcset)
1257        : Parent(*arcset.graph) { }
1258
1259      NodeMap(const SmartEdgeSetBase<Graph>& arcset, const _Value& value)
1260        : Parent(*arcset.graph, value) { }
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  ///
1288  /// \param _Graph The type of the graph which shares its node set
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.
1305  template <typename _Graph>
1306  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
1307
1308  public:
1309
1310    typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
1311
1312    typedef typename Parent::Node Node;
1313    typedef typename Parent::Arc Arc;
1314    typedef typename Parent::Edge Edge;
1315
1316    typedef _Graph Graph;
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
1337      NodesImpl(const Graph& graph, SmartEdgeSet& arcset)
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
1377    NodesImpl nodes;
1378
1379  public:
1380
1381    /// \brief Constructor of the EdgeSet.
1382    ///
1383    /// Constructor of the EdgeSet.
1384    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
1385      Parent::initalize(graph, nodes);
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 {
1403      return nodes.attached();
1404    }
1405
1406  };
1407
1408}
1409
1410#endif
Note: See TracBrowser for help on using the repository browser.