COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/edge_set.h @ 864:d3ea191c3412

Last change on this file since 864:d3ea191c3412 was 787:c2230649a493, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Various doc improvements (#331)

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