COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 2618:6aa6fcaeaea5

Last change on this file since 2618:6aa6fcaeaea5 was 2618:6aa6fcaeaea5, checked in by Balazs Dezso, 11 years ago

G++-4.3 compatibility changes

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-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
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.