COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 2498:290e43cddc1a

Last change on this file since 2498:290e43cddc1a was 2498:290e43cddc1a, checked in by Balazs Dezso, 12 years ago

Bug fix in undirected graphs (adding loops)
Bug fix in undirected edgesets (alteration notifying)

Redesigned undirected edgesets (like the smart or ugraph)

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