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
RevLine 
[468]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_EDGE_SET_H
20#define LEMON_EDGE_SET_H
21
22#include <lemon/core.h>
23#include <lemon/bits/edge_set_extender.h>
24
[660]25/// \ingroup graphs
[468]26/// \file
27/// \brief ArcSet and EdgeSet classes.
28///
29/// Graphs which use another graph's node-set as own.
30namespace lemon {
31
[512]32  template <typename GR>
[468]33  class ListArcSetBase {
34  public:
35
[512]36    typedef typename GR::Node Node;
37    typedef typename GR::NodeIt NodeIt;
[468]38
39  protected:
40
41    struct NodeT {
42      int first_out, first_in;
43      NodeT() : first_out(-1), first_in(-1) {}
44    };
45
[512]46    typedef typename ItemSetTraits<GR, Node>::
[468]47    template Map<NodeT>::Type NodesImplBase;
48
[512]49    NodesImplBase* _nodes;
[468]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
[512]63    const GR* _graph;
[468]64
[512]65    void initalize(const GR& graph, NodesImplBase& nodes) {
66      _graph = &graph;
67      _nodes = &nodes;
[468]68    }
69
70  public:
71
72    class Arc {
[512]73      friend class ListArcSetBase<GR>;
[468]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
[670]87    Node addNode() {
88      LEMON_ASSERT(false,
89        "This graph structure does not support node insertion");
90      return INVALID; // avoid warning
91    }
92
[468]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      }
[512]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;
[468]105      }
[512]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;
[468]110      }
[512]111      (*_nodes)[u].first_out = n;
[468]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 {
[512]122        (*_nodes)[arcs[n].target].first_in = arcs[n].next_in;
[468]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 {
[512]131        (*_nodes)[arcs[n].source].first_out = arcs[n].next_out;
[468]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)) {
[512]142        (*_nodes)[node].first_in = -1;
143        (*_nodes)[node].first_out = -1;
[468]144      }
145      arcs.clear();
146      first_arc = -1;
147      first_free_arc = -1;
148    }
149
150    void first(Node& node) const {
[512]151      _graph->first(node);
[468]152    }
153
154    void next(Node& node) const {
[512]155      _graph->next(node);
[468]156    }
157
158    void first(Arc& arc) const {
159      Node node;
160      first(node);
[512]161      while (node != INVALID && (*_nodes)[node].first_in == -1) {
[468]162        next(node);
163      }
[512]164      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
[468]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);
[512]173        while (node != INVALID && (*_nodes)[node].first_in == -1) {
[468]174          next(node);
175        }
[512]176        arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
[468]177      }
178    }
179
180    void firstOut(Arc& arc, const Node& node) const {
[512]181      arc.id = (*_nodes)[node].first_out;
[468]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 {
[512]189      arc.id = (*_nodes)[node].first_in;
[468]190    }
191
192    void nextIn(Arc& arc) const {
193      arc.id = arcs[arc.id].next_in;
194    }
195
[512]196    int id(const Node& node) const { return _graph->id(node); }
[468]197    int id(const Arc& arc) const { return arc.id; }
198
[512]199    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
[468]200    Arc arcFromId(int ix) const { return Arc(ix); }
201
[512]202    int maxNodeId() const { return _graph->maxNodeId(); };
[468]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
[512]208    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
[468]209
210    NodeNotifier& notifier(Node) const {
[512]211      return _graph->notifier(Node());
[468]212    }
213
[512]214    template <typename V>
215    class NodeMap : public GR::template NodeMap<V> {
[617]216      typedef typename GR::template NodeMap<V> Parent;
217
[468]218    public:
219
[512]220      explicit NodeMap(const ListArcSetBase<GR>& arcset)
221        : Parent(*arcset._graph) {}
[468]222
[512]223      NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
224        : Parent(*arcset._graph, value) {}
[468]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
[660]239  /// \ingroup graphs
[468]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  ///
[787]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  ///
[512]262  /// \param GR The type of the graph which shares its node set with
[468]263  /// this class. Its interface must conform to the
264  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
265  /// concept.
[512]266  template <typename GR>
267  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
[617]268    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
[468]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
[617]299    public:
[512]300      NodesImpl(const GR& graph, ListArcSet& arcset)
[468]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
[512]326    NodesImpl _nodes;
[468]327
328  public:
329
330    /// \brief Constructor of the ArcSet.
331    ///
332    /// Constructor of the ArcSet.
[512]333    ListArcSet(const GR& graph) : _nodes(graph, *this) {
334      Parent::initalize(graph, _nodes);
[468]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.
[559]341    /// \return The new arc.
[468]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
[512]355  template <typename GR>
[468]356  class ListEdgeSetBase {
357  public:
358
[512]359    typedef typename GR::Node Node;
360    typedef typename GR::NodeIt NodeIt;
[468]361
362  protected:
363
364    struct NodeT {
365      int first_out;
366      NodeT() : first_out(-1) {}
367    };
368
[512]369    typedef typename ItemSetTraits<GR, Node>::
[468]370    template Map<NodeT>::Type NodesImplBase;
371
[512]372    NodesImplBase* _nodes;
[468]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
[512]385    const GR* _graph;
[468]386
[512]387    void initalize(const GR& graph, NodesImplBase& nodes) {
388      _graph = &graph;
389      _nodes = &nodes;
[468]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
[670]426    Node addNode() {
427      LEMON_ASSERT(false,
428        "This graph structure does not support node insertion");
429      return INVALID; // avoid warning
430    }
431
[468]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
[512]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;
[468]450      }
[512]451      (*_nodes)[v].first_out = n;
[468]452      arcs[n].prev_out = -1;
453
[512]454      if ((*_nodes)[u].first_out != -1) {
455        arcs[(*_nodes)[u].first_out].prev_out = (n | 1);
[468]456      }
[512]457      arcs[n | 1].next_out = (*_nodes)[u].first_out;
458      (*_nodes)[u].first_out = (n | 1);
[468]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 {
[512]474        (*_nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
[468]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 {
[512]484        (*_nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
[468]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)) {
[512]495        (*_nodes)[node].first_out = -1;
[468]496      }
497      arcs.clear();
498      first_arc = -1;
499      first_free_arc = -1;
500    }
501
502    void first(Node& node) const {
[512]503      _graph->first(node);
[468]504    }
505
506    void next(Node& node) const {
[512]507      _graph->next(node);
[468]508    }
509
510    void first(Arc& arc) const {
511      Node node;
512      first(node);
[512]513      while (node != INVALID && (*_nodes)[node].first_out == -1) {
[468]514        next(node);
515      }
[512]516      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
[468]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);
[512]525        while(node != INVALID && (*_nodes)[node].first_out == -1) {
[468]526          next(node);
527        }
[512]528        arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
[468]529      }
530    }
531
532    void first(Edge& edge) const {
533      Node node;
534      first(node);
535      while (node != INVALID) {
[512]536        edge.id = (*_nodes)[node].first_out;
[468]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) {
[512]561        edge.id = (*_nodes)[node].first_out;
[468]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 {
[512]575      arc.id = (*_nodes)[node].first_out;
[468]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 {
[512]583      arc.id = (((*_nodes)[node].first_out) ^ 1);
[468]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 {
[512]593      int de = (*_nodes)[node].first_out;
[468]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
[512]621    int id(const Node& node) const { return _graph->id(node); }
[468]622    static int id(Arc e) { return e.id; }
623    static int id(Edge e) { return e.id; }
624
[512]625    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
[468]626    static Arc arcFromId(int id) { return Arc(id);}
627    static Edge edgeFromId(int id) { return Edge(id);}
628
[512]629    int maxNodeId() const { return _graph->maxNodeId(); };
[468]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
[512]639    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
[468]640
641    NodeNotifier& notifier(Node) const {
[512]642      return _graph->notifier(Node());
[468]643    }
644
[512]645    template <typename V>
646    class NodeMap : public GR::template NodeMap<V> {
[617]647      typedef typename GR::template NodeMap<V> Parent;
648
[468]649    public:
650
[512]651      explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
652        : Parent(*arcset._graph) {}
[468]653
[512]654      NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
655        : Parent(*arcset._graph, value) {}
[468]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
[660]670  /// \ingroup graphs
[468]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  ///
[787]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  ///
[512]693  /// \param GR The type of the graph which shares its node set
[468]694  /// with this class. Its interface must conform to the
695  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
696  /// concept.
[512]697  template <typename GR>
698  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
[617]699    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
[468]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
[617]726    public:
[512]727      NodesImpl(const GR& graph, ListEdgeSet& arcset)
[468]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
[512]753    NodesImpl _nodes;
[468]754
755  public:
756
757    /// \brief Constructor of the EdgeSet.
758    ///
759    /// Constructor of the EdgeSet.
[512]760    ListEdgeSet(const GR& graph) : _nodes(graph, *this) {
761      Parent::initalize(graph, _nodes);
[468]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.
[559]768    /// \return The new edge.
[468]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
[512]782  template <typename GR>
[468]783  class SmartArcSetBase {
784  public:
785
[617]786    typedef typename GR::Node Node;
787    typedef typename GR::NodeIt NodeIt;
[468]788
789  protected:
790
791    struct NodeT {
792      int first_out, first_in;
793      NodeT() : first_out(-1), first_in(-1) {}
794    };
795
[512]796    typedef typename ItemSetTraits<GR, Node>::
[468]797    template Map<NodeT>::Type NodesImplBase;
798
[512]799    NodesImplBase* _nodes;
[468]800
801    struct ArcT {
802      Node source, target;
803      int next_out, next_in;
804      ArcT() {}
805    };
806
807    std::vector<ArcT> arcs;
808
[512]809    const GR* _graph;
[468]810
[512]811    void initalize(const GR& graph, NodesImplBase& nodes) {
812      _graph = &graph;
813      _nodes = &nodes;
[468]814    }
815
816  public:
817
818    class Arc {
[512]819      friend class SmartArcSetBase<GR>;
[468]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
[670]833    Node addNode() {
834      LEMON_ASSERT(false,
835        "This graph structure does not support node insertion");
836      return INVALID; // avoid warning
837    }
838
[468]839    Arc addArc(const Node& u, const Node& v) {
840      int n = arcs.size();
841      arcs.push_back(ArcT());
[512]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;
[468]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)) {
[512]854        (*_nodes)[node].first_in = -1;
855        (*_nodes)[node].first_out = -1;
[468]856      }
857      arcs.clear();
858    }
859
860    void first(Node& node) const {
[512]861      _graph->first(node);
[468]862    }
863
864    void next(Node& node) const {
[512]865      _graph->next(node);
[468]866    }
867
868    void first(Arc& arc) const {
869      arc.id = arcs.size() - 1;
870    }
871
[778]872    static void next(Arc& arc) {
[468]873      --arc.id;
874    }
875
876    void firstOut(Arc& arc, const Node& node) const {
[512]877      arc.id = (*_nodes)[node].first_out;
[468]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 {
[512]885      arc.id = (*_nodes)[node].first_in;
[468]886    }
887
888    void nextIn(Arc& arc) const {
889      arc.id = arcs[arc.id].next_in;
890    }
891
[512]892    int id(const Node& node) const { return _graph->id(node); }
[468]893    int id(const Arc& arc) const { return arc.id; }
894
[512]895    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
[468]896    Arc arcFromId(int ix) const { return Arc(ix); }
897
[512]898    int maxNodeId() const { return _graph->maxNodeId(); };
[468]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
[512]904    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
[468]905
906    NodeNotifier& notifier(Node) const {
[512]907      return _graph->notifier(Node());
[468]908    }
909
[512]910    template <typename V>
911    class NodeMap : public GR::template NodeMap<V> {
[617]912      typedef typename GR::template NodeMap<V> Parent;
913
[468]914    public:
915
[512]916      explicit NodeMap(const SmartArcSetBase<GR>& arcset)
917        : Parent(*arcset._graph) { }
[468]918
[512]919      NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
920        : Parent(*arcset._graph, value) { }
[468]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
[660]936  /// \ingroup graphs
[468]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  ///
[512]949  /// \param GR The type of the graph which shares its node set with
[468]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  ///
[787]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  ///
[468]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.
[512]967  template <typename GR>
968  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
[617]969    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
[468]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
[617]995    public:
[512]996      NodesImpl(const GR& graph, SmartArcSet& arcset)
[468]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
[512]1036    NodesImpl _nodes;
[468]1037
1038  public:
1039
1040    /// \brief Constructor of the ArcSet.
1041    ///
1042    /// Constructor of the ArcSet.
[512]1043    SmartArcSet(const GR& graph) : _nodes(graph, *this) {
1044      Parent::initalize(graph, _nodes);
[468]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.
[559]1051    /// \return The new arc.
[468]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 {
[512]1062      return _nodes.attached();
[468]1063    }
1064
1065  };
1066
1067
[512]1068  template <typename GR>
[468]1069  class SmartEdgeSetBase {
1070  public:
1071
[512]1072    typedef typename GR::Node Node;
1073    typedef typename GR::NodeIt NodeIt;
[468]1074
1075  protected:
1076
1077    struct NodeT {
1078      int first_out;
1079      NodeT() : first_out(-1) {}
1080    };
1081
[512]1082    typedef typename ItemSetTraits<GR, Node>::
[468]1083    template Map<NodeT>::Type NodesImplBase;
1084
[512]1085    NodesImplBase* _nodes;
[468]1086
1087    struct ArcT {
1088      Node target;
1089      int next_out;
1090      ArcT() {}
1091    };
1092
1093    std::vector<ArcT> arcs;
1094
[512]1095    const GR* _graph;
[468]1096
[512]1097    void initalize(const GR& graph, NodesImplBase& nodes) {
1098      _graph = &graph;
1099      _nodes = &nodes;
[468]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
[670]1136    Node addNode() {
1137      LEMON_ASSERT(false,
1138        "This graph structure does not support node insertion");
1139      return INVALID; // avoid warning
1140    }
1141
[468]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
[512]1150      arcs[n].next_out = (*_nodes)[v].first_out;
1151      (*_nodes)[v].first_out = n;
[468]1152
[512]1153      arcs[n | 1].next_out = (*_nodes)[u].first_out;
1154      (*_nodes)[u].first_out = (n | 1);
[468]1155
1156      return Edge(n / 2);
1157    }
1158
1159    void clear() {
1160      Node node;
1161      for (first(node); node != INVALID; next(node)) {
[512]1162        (*_nodes)[node].first_out = -1;
[468]1163      }
1164      arcs.clear();
1165    }
1166
1167    void first(Node& node) const {
[512]1168      _graph->first(node);
[468]1169    }
1170
1171    void next(Node& node) const {
[512]1172      _graph->next(node);
[468]1173    }
1174
1175    void first(Arc& arc) const {
1176      arc.id = arcs.size() - 1;
1177    }
1178
[778]1179    static void next(Arc& arc) {
[468]1180      --arc.id;
1181    }
1182
1183    void first(Edge& arc) const {
1184      arc.id = arcs.size() / 2 - 1;
1185    }
1186
[778]1187    static void next(Edge& arc) {
[468]1188      --arc.id;
1189    }
1190
1191    void firstOut(Arc& arc, const Node& node) const {
[512]1192      arc.id = (*_nodes)[node].first_out;
[468]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 {
[512]1200      arc.id = (((*_nodes)[node].first_out) ^ 1);
[468]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 {
[512]1210      int de = (*_nodes)[node].first_out;
[468]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
[512]1238    int id(Node node) const { return _graph->id(node); }
[468]1239    static int id(Arc arc) { return arc.id; }
1240    static int id(Edge arc) { return arc.id; }
1241
[512]1242    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
[468]1243    static Arc arcFromId(int id) { return Arc(id); }
1244    static Edge edgeFromId(int id) { return Edge(id);}
1245
[512]1246    int maxNodeId() const { return _graph->maxNodeId(); };
[468]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
[512]1256    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
[468]1257
1258    NodeNotifier& notifier(Node) const {
[512]1259      return _graph->notifier(Node());
[468]1260    }
1261
[512]1262    template <typename V>
1263    class NodeMap : public GR::template NodeMap<V> {
[617]1264      typedef typename GR::template NodeMap<V> Parent;
1265
[468]1266    public:
1267
[512]1268      explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
1269        : Parent(*arcset._graph) { }
[468]1270
[512]1271      NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
1272        : Parent(*arcset._graph, value) { }
[468]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
[660]1287  /// \ingroup graphs
[468]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  ///
[512]1300  /// \param GR The type of the graph which shares its node set
[468]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  ///
[787]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  ///
[468]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.
[512]1318  template <typename GR>
1319  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
[617]1320    typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
[468]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
[617]1346    public:
[512]1347      NodesImpl(const GR& graph, SmartEdgeSet& arcset)
[468]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
[512]1387    NodesImpl _nodes;
[468]1388
1389  public:
1390
1391    /// \brief Constructor of the EdgeSet.
1392    ///
1393    /// Constructor of the EdgeSet.
[512]1394    SmartEdgeSet(const GR& graph) : _nodes(graph, *this) {
1395      Parent::initalize(graph, _nodes);
[468]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.
[559]1402    /// \return The new edge.
[468]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 {
[512]1413      return _nodes.attached();
[468]1414    }
1415
1416  };
1417
1418}
1419
1420#endif
Note: See TracBrowser for help on using the repository browser.