COIN-OR::LEMON - Graph Library

source: lemon/lemon/edge_set.h @ 810:93cd93e82f9b

Last change on this file since 810:93cd93e82f9b was 717:926c47568a56, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Add artificial addNode() function to the arc/edge set classes

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