COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 1962:c1c3a0fae8a1

Last change on this file since 1962:c1c3a0fae8a1 was 1962:c1c3a0fae8a1, checked in by Balazs Dezso, 14 years ago

Bug fixes in ListEdgeSet?
Added SmartEdgeSet?

File size: 19.1 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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/bits/erasable_graph_extender.h>
23#include <lemon/bits/clearable_graph_extender.h>
24#include <lemon/bits/extendable_graph_extender.h>
25#include <lemon/bits/iterable_graph_extender.h>
26#include <lemon/bits/alteration_notifier.h>
27#include <lemon/bits/default_map.h>
28#include <lemon/bits/graph_extender.h>
29
30/// \ingroup graphs
31/// \file
32/// \brief EdgeSet classes.
33///
34/// Graphs which use another graph's node-set as own.
35
36namespace lemon {
37
38  template <typename _Graph>
39  class ListEdgeSetBase {
40  public:
41
42    typedef _Graph Graph;
43    typedef typename Graph::Node Node;
44    typedef typename Graph::NodeIt NodeIt;
45
46  protected:
47
48    struct NodeT {
49      int first_out, first_in;
50      NodeT() : first_out(-1), first_in(-1) {}
51    };
52
53    typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
54
55    NodesImplBase* nodes;
56
57    struct EdgeT {
58      Node source, target;
59      int next_out, next_in;
60      int prev_out, prev_in;
61      EdgeT() : prev_out(-1), prev_in(-1) {}
62    };
63
64    std::vector<EdgeT> edges;
65
66    int first_edge;
67    int first_free_edge;
68
69    const Graph* graph;
70
71    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
72      graph = &_graph;
73      nodes = &_nodes;
74    }
75   
76  public:
77
78    class Edge {
79      friend class ListEdgeSetBase<Graph>;
80    protected:
81      Edge(int _id) : id(_id) {}
82      int id;
83    public:
84      Edge() {}
85      Edge(Invalid) : id(-1) {}
86      bool operator==(const Edge& edge) const { return id == edge.id; }
87      bool operator!=(const Edge& edge) const { return id != edge.id; }
88      bool operator<(const Edge& edge) const { return id < edge.id; }
89    };
90
91    ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
92
93    Edge addEdge(const Node& source, const Node& target) {
94      int n;
95      if (first_free_edge == -1) {
96        n = edges.size();
97        edges.push_back(EdgeT());
98      } else {
99        n = first_free_edge;
100        first_free_edge = edges[first_free_edge].next_in;
101      }
102      edges[n].next_in = (*nodes)[target].first_in;
103      if ((*nodes)[target].first_in != -1) {
104        edges[(*nodes)[target].first_in].prev_in = n;
105      }
106      (*nodes)[target].first_in = n;
107      edges[n].next_out = (*nodes)[source].first_out;
108      if ((*nodes)[source].first_out != -1) {
109        edges[(*nodes)[source].first_out].prev_out = n;
110      }
111      (*nodes)[source].first_out = n;
112      edges[n].source = source;
113      edges[n].target = target;
114      return Edge(n);
115    }
116
117    void erase(const Edge& edge) {
118      int n = edge.id;
119      if (edges[n].prev_in != -1) {
120        edges[edges[n].prev_in].next_in = edges[n].next_in;
121      } else {
122        (*nodes)[edges[n].target].first_in = edges[n].next_in;
123      }
124      if (edges[n].next_in != -1) {
125        edges[edges[n].next_in].prev_in = edges[n].prev_in;
126      }
127
128      if (edges[n].prev_out != -1) {
129        edges[edges[n].prev_out].next_out = edges[n].next_out;
130      } else {
131        (*nodes)[edges[n].source].first_out = edges[n].next_out;
132      }
133      if (edges[n].next_out != -1) {
134        edges[edges[n].next_out].prev_out = edges[n].prev_out;
135      }
136           
137    }
138
139    void clear() {
140      Node node;
141      for (first(node); node != INVALID; next(node)) {
142        (*nodes)[node].first_in = -1;
143        (*nodes)[node].first_out = -1;
144      }
145      edges.clear();
146      first_edge = -1;
147      first_free_edge = -1;
148    }
149
150    void first(Node& node) const {
151      graph->first(node);
152    }
153
154    void next(Node& node) const {
155      graph->next(node);
156    }
157
158    void first(Edge& edge) const {
159      Node node;
160      for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
161           next(node));
162      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
163    }
164
165    void next(Edge& edge) const {
166      if (edges[edge.id].next_in != -1) {
167        edge.id = edges[edge.id].next_in;
168      } else {
169        Node node = edges[edge.id].target;
170        for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
171             next(node));
172        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
173      }     
174    }
175
176    void firstOut(Edge& edge, const Node& node) const {
177      edge.id = (*nodes)[node].first_out;   
178    }
179   
180    void nextOut(Edge& edge) const {
181      edge.id = edges[edge.id].next_out;       
182    }
183
184    void firstIn(Edge& edge, const Node& node) const {
185      edge.id = (*nodes)[node].first_in;         
186    }
187
188    void nextIn(Edge& edge) const {
189      edge.id = edges[edge.id].next_in;   
190    }
191
192    int id(const Node& node) const { return graph->id(node); }
193    int id(const Edge& edge) const { return edge.id; }
194
195    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
196    Edge edgeFromId(int id) const { return Edge(id); }
197
198    int maxNodeId() const { return graph->maxNodeId(); };
199    int maxEdgeId() const { return edges.size() - 1; }
200
201    Node source(const Edge& edge) const { return edges[edge.id].source;}
202    Node target(const Edge& edge) const { return edges[edge.id].target;}
203
204    template <typename _Value>
205    class NodeMap : public Graph::template NodeMap<_Value> {
206    public:
207      typedef typename _Graph::template NodeMap<_Value> Parent;
208      explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
209        : Parent(*edgeset.graph) { }
210      NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
211        : Parent(*edgeset.graph, value) { }
212    };
213
214  };
215
216  /// \ingroup semi_adaptors
217  ///
218  /// \brief Graph using a node set of another graph and an
219  /// own edge set.
220  ///
221  /// This structure can be used to establish another graph over a node set
222  /// of an existing one. The node iterator will go through the nodes of the
223  /// original graph.
224  ///
225  /// \param _Graph The type of the graph which shares its node set with
226  /// this class. Its interface must conform to the \ref concept::StaticGraph
227  /// "StaticGraph" concept.
228  ///
229  /// In the edge extension and removing it conforms to the
230  /// \ref concept::ErasableGraph "ErasableGraph" concept.
231  template <typename _Graph>
232  class ListEdgeSet :
233    public ErasableEdgeSetExtender<
234    ClearableEdgeSetExtender<
235    ExtendableEdgeSetExtender<
236    MappableEdgeSetExtender<
237    IterableGraphExtender<
238    AlterableEdgeSetExtender<
239    GraphExtender<
240    ListEdgeSetBase<_Graph> > > > > > > > {
241
242  public:
243
244    typedef ErasableEdgeSetExtender<
245      ClearableEdgeSetExtender<
246      ExtendableEdgeSetExtender<
247      MappableEdgeSetExtender<
248      IterableGraphExtender<
249      AlterableEdgeSetExtender<
250      GraphExtender<
251      ListEdgeSetBase<_Graph> > > > > > > > Parent;
252   
253    typedef typename Parent::Node Node;
254    typedef typename Parent::Edge Edge;
255   
256    typedef _Graph Graph;
257
258
259    typedef typename Parent::NodesImplBase NodesImplBase;
260
261    void eraseNode(const Node& node) {
262      Edge edge;
263      Parent::firstOut(edge, node);
264      while (edge != INVALID ) {
265        erase(edge);
266        Parent::firstOut(edge, node);
267      }
268
269      Parent::firstIn(edge, node);
270      while (edge != INVALID ) {
271        erase(edge);
272        Parent::firstIn(edge, node);
273      }
274    }
275   
276    void clearNodes() {
277      Parent::clear();
278    }
279
280    class NodesImpl : public NodesImplBase {
281    public:
282      typedef NodesImplBase Parent;
283     
284      NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
285        : Parent(graph), _edgeset(edgeset) {}
286
287      virtual ~NodesImpl() {}
288     
289    protected:
290
291      virtual void erase(const Node& node) {
292        _edgeset.eraseNode(node);
293        Parent::erase(node);
294      }
295      virtual void erase(const std::vector<Node>& nodes) {
296        for (int i = 0; i < (int)nodes.size(); ++i) {
297          _edgeset.eraseNode(nodes[i]);
298        }
299        Parent::erase(nodes);
300      }
301      virtual void clear() {
302        _edgeset.clearNodes();
303        Parent::clear();
304      }
305
306    private:
307      ListEdgeSet& _edgeset;
308    };
309
310    NodesImpl nodes;
311   
312  public:
313
314    /// \brief Constructor of the adaptor.
315    ///
316    /// Constructor of the adaptor.
317    ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
318      Parent::initalize(graph, nodes);
319    }
320   
321  };
322
323  /// \ingroup semi_adaptors
324  ///
325  /// \brief Graph using a node set of another graph and an
326  /// own uedge set.
327  ///
328  /// This structure can be used to establish another graph over a node set
329  /// of an existing one. The node iterator will go through the nodes of the
330  /// original graph.
331  ///
332  /// \param _Graph The type of the graph which shares its node set with
333  /// this class. Its interface must conform to the \ref concept::StaticGraph
334  /// "StaticGraph" concept.
335  ///
336  /// In the edge extension and removing it conforms to the
337  /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
338  template <typename _Graph>
339  class ListUEdgeSet :
340    public ErasableUEdgeSetExtender<
341    ClearableUEdgeSetExtender<
342    ExtendableUEdgeSetExtender<
343    MappableUEdgeSetExtender<
344    IterableUGraphExtender<
345    AlterableUEdgeSetExtender<
346    UGraphExtender<
347    ListEdgeSetBase<_Graph> > > > > > > > {
348
349  public:
350
351    typedef ErasableUEdgeSetExtender<
352      ClearableUEdgeSetExtender<
353      ExtendableUEdgeSetExtender<
354      MappableUEdgeSetExtender<
355      IterableUGraphExtender<
356      AlterableUEdgeSetExtender<
357      UGraphExtender<
358      ListEdgeSetBase<_Graph> > > > > > > > Parent;
359   
360    typedef typename Parent::Node Node;
361    typedef typename Parent::Edge Edge;
362   
363    typedef _Graph Graph;
364
365
366    typedef typename Parent::NodesImplBase NodesImplBase;
367
368    void eraseNode(const Node& node) {
369      Edge edge;
370      Parent::firstOut(edge, node);
371      while (edge != INVALID ) {
372        erase(edge);
373        Parent::firstOut(edge, node);
374      }
375
376    }
377   
378    void clearNodes() {
379      Parent::clear();
380    }
381
382    class NodesImpl : public NodesImplBase {
383    public:
384      typedef NodesImplBase Parent;
385     
386      NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
387        : Parent(graph), _edgeset(edgeset) {}
388
389      virtual ~NodesImpl() {}
390     
391    protected:
392
393      virtual void erase(const Node& node) {
394        _edgeset.eraseNode(node);
395        Parent::erase(node);
396      }
397      virtual void erase(const std::vector<Node>& nodes) {
398        for (int i = 0; i < (int)nodes.size(); ++i) {
399          _edgeset.eraseNode(nodes[i]);
400        }
401        Parent::erase(nodes);
402      }
403      virtual void clear() {
404        _edgeset.clearNodes();
405        Parent::clear();
406      }
407
408    private:
409      ListUEdgeSet& _edgeset;
410    };
411
412    NodesImpl nodes;
413   
414  public:
415
416    /// \brief Constructor of the adaptor.
417    ///
418    /// Constructor of the adaptor.
419    ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
420      Parent::initalize(graph, nodes);
421    }
422   
423  };
424
425  template <typename _Graph>
426  class SmartEdgeSetBase {
427  public:
428
429    typedef _Graph Graph;
430    typedef typename Graph::Node Node;
431    typedef typename Graph::NodeIt NodeIt;
432
433  protected:
434
435    struct NodeT {
436      int first_out, first_in;
437      NodeT() : first_out(-1), first_in(-1) {}
438    };
439
440    typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
441
442    NodesImplBase* nodes;
443
444    struct EdgeT {
445      Node source, target;
446      int next_out, next_in;
447      EdgeT() {}
448    };
449
450    std::vector<EdgeT> edges;
451
452    const Graph* graph;
453
454    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
455      graph = &_graph;
456      nodes = &_nodes;
457    }
458   
459  public:
460
461    class Edge {
462      friend class SmartEdgeSetBase<Graph>;
463    protected:
464      Edge(int _id) : id(_id) {}
465      int id;
466    public:
467      Edge() {}
468      Edge(Invalid) : id(-1) {}
469      bool operator==(const Edge& edge) const { return id == edge.id; }
470      bool operator!=(const Edge& edge) const { return id != edge.id; }
471      bool operator<(const Edge& edge) const { return id < edge.id; }
472    };
473
474    SmartEdgeSetBase() {}
475
476    Edge addEdge(const Node& source, const Node& target) {
477      int n = edges.size();
478      edges.push_back(EdgeT());
479      edges[n].next_in = (*nodes)[target].first_in;
480      (*nodes)[target].first_in = n;
481      edges[n].next_out = (*nodes)[source].first_out;
482      (*nodes)[source].first_out = n;
483      edges[n].source = source;
484      edges[n].target = target;
485      return Edge(n);
486    }
487
488    void clear() {
489      Node node;
490      for (first(node); node != INVALID; next(node)) {
491        (*nodes)[node].first_in = -1;
492        (*nodes)[node].first_out = -1;
493      }
494      edges.clear();
495    }
496
497    void first(Node& node) const {
498      graph->first(node);
499    }
500
501    void next(Node& node) const {
502      graph->next(node);
503    }
504
505    void first(Edge& edge) const {
506      edge.id = edges.size() - 1;
507    }
508
509    void next(Edge& edge) const {
510      --edge.id;
511    }
512
513    void firstOut(Edge& edge, const Node& node) const {
514      edge.id = (*nodes)[node].first_out;   
515    }
516   
517    void nextOut(Edge& edge) const {
518      edge.id = edges[edge.id].next_out;       
519    }
520
521    void firstIn(Edge& edge, const Node& node) const {
522      edge.id = (*nodes)[node].first_in;         
523    }
524
525    void nextIn(Edge& edge) const {
526      edge.id = edges[edge.id].next_in;   
527    }
528
529    int id(const Node& node) const { return graph->id(node); }
530    int id(const Edge& edge) const { return edge.id; }
531
532    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
533    Edge edgeFromId(int id) const { return Edge(id); }
534
535    int maxNodeId() const { return graph->maxNodeId(); };
536    int maxEdgeId() const { return edges.size() - 1; }
537
538    Node source(const Edge& edge) const { return edges[edge.id].source;}
539    Node target(const Edge& edge) const { return edges[edge.id].target;}
540
541    template <typename _Value>
542    class NodeMap : public Graph::template NodeMap<_Value> {
543    public:
544      typedef typename _Graph::template NodeMap<_Value> Parent;
545      explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
546        : Parent(*edgeset.graph) { }
547      NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
548        : Parent(*edgeset.graph, value) { }
549    };
550
551  };
552
553
554  /// \ingroup semi_adaptors
555  ///
556  /// \brief Graph using a node set of another graph and an
557  /// own edge set.
558  ///
559  /// This structure can be used to establish another graph over a node set
560  /// of an existing one. The node iterator will go through the nodes of the
561  /// original graph.
562  ///
563  /// \param _Graph The type of the graph which shares its node set with
564  /// this class. Its interface must conform to the \ref concept::StaticGraph
565  /// "StaticGraph" concept.
566  ///
567  /// In the edge extension and removing it conforms to the
568  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
569  template <typename _Graph>
570  class SmartEdgeSet :
571    public ClearableEdgeSetExtender<
572    ExtendableEdgeSetExtender<
573    MappableEdgeSetExtender<
574    IterableGraphExtender<
575    AlterableEdgeSetExtender<
576    GraphExtender<
577    SmartEdgeSetBase<_Graph> > > > > > > {
578
579  public:
580
581    typedef ClearableEdgeSetExtender<
582      ExtendableEdgeSetExtender<
583      MappableEdgeSetExtender<
584      IterableGraphExtender<
585      AlterableEdgeSetExtender<
586      GraphExtender<
587      SmartEdgeSetBase<_Graph> > > > > > > Parent;
588   
589    typedef typename Parent::Node Node;
590    typedef typename Parent::Edge Edge;
591   
592    typedef _Graph Graph;
593
594    class UnsupportedOperation : public LogicError {
595    public:
596      virtual const char* exceptionName() const {
597        return "lemon::SmartEdgeSet::UnsupportedOperation";
598      }
599    };
600   
601
602
603  protected:
604
605    typedef typename Parent::NodesImplBase NodesImplBase;
606
607    void eraseNode(const Node&) {
608      throw UnsupportedOperation();
609    }
610   
611    void clearNodes() {
612      Parent::clear();
613    }
614
615    class NodesImpl : public NodesImplBase {
616    public:
617      typedef NodesImplBase Parent;
618     
619      NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
620        : Parent(graph), _edgeset(edgeset) {}
621
622      virtual ~NodesImpl() {}
623     
624    protected:
625
626      virtual void erase(const Node& node) {
627        _edgeset.eraseNode(node);
628        Parent::erase(node);
629      }
630      virtual void erase(const std::vector<Node>& nodes) {
631        for (int i = 0; i < (int)nodes.size(); ++i) {
632          _edgeset.eraseNode(nodes[i]);
633        }
634        Parent::erase(nodes);
635      }
636      virtual void clear() {
637        _edgeset.clearNodes();
638        Parent::clear();
639      }
640
641    private:
642      SmartEdgeSet& _edgeset;
643    };
644
645    NodesImpl nodes;
646   
647  public:
648
649    /// \brief Constructor of the adaptor.
650    ///
651    /// Constructor of the adaptor.
652    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
653      Parent::initalize(graph, nodes);
654    }
655   
656  };
657
658  /// \ingroup semi_adaptors
659  ///
660  /// \brief Graph using a node set of another graph and an
661  /// own uedge set.
662  ///
663  /// This structure can be used to establish another graph over a node set
664  /// of an existing one. The node iterator will go through the nodes of the
665  /// original graph.
666  ///
667  /// \param _Graph The type of the graph which shares its node set with
668  /// this class. Its interface must conform to the \ref concept::StaticGraph
669  /// "StaticGraph" concept.
670  ///
671  /// In the edge extension and removing it conforms to the
672  /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
673  template <typename _Graph>
674  class SmartUEdgeSet :
675    public ClearableUEdgeSetExtender<
676    ExtendableUEdgeSetExtender<
677    MappableUEdgeSetExtender<
678    IterableUGraphExtender<
679    AlterableUEdgeSetExtender<
680    UGraphExtender<
681    SmartEdgeSetBase<_Graph> > > > > > > {
682
683  public:
684
685    typedef ClearableUEdgeSetExtender<
686      ExtendableUEdgeSetExtender<
687      MappableUEdgeSetExtender<
688      IterableUGraphExtender<
689      AlterableUEdgeSetExtender<
690      UGraphExtender<
691      SmartEdgeSetBase<_Graph> > > > > > > Parent;
692   
693    typedef typename Parent::Node Node;
694    typedef typename Parent::Edge Edge;
695   
696    typedef _Graph Graph;
697
698    class UnsupportedOperation : public LogicError {
699    public:
700      virtual const char* exceptionName() const {
701        return "lemon::SmartUEdgeSet::UnsupportedOperation";
702      }
703    };
704
705  protected:
706
707    typedef typename Parent::NodesImplBase NodesImplBase;
708
709    void eraseNode(const Node&) {
710      throw UnsupportedOperation();
711    }
712   
713    void clearNodes() {
714      Parent::clear();
715    }
716
717    class NodesImpl : public NodesImplBase {
718    public:
719      typedef NodesImplBase Parent;
720     
721      NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
722        : Parent(graph), _edgeset(edgeset) {}
723
724      virtual ~NodesImpl() {}
725     
726    protected:
727
728      virtual void erase(const Node& node) {
729        _edgeset.eraseNode(node);
730        Parent::erase(node);
731      }
732      virtual void erase(const std::vector<Node>& nodes) {
733        for (int i = 0; i < (int)nodes.size(); ++i) {
734          _edgeset.eraseNode(nodes[i]);
735        }
736        Parent::erase(nodes);
737      }
738      virtual void clear() {
739        _edgeset.clearNodes();
740        Parent::clear();
741      }
742
743    private:
744      SmartUEdgeSet& _edgeset;
745    };
746
747    NodesImpl nodes;
748   
749  public:
750
751    /// \brief Constructor of the adaptor.
752    ///
753    /// Constructor of the adaptor.
754    SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
755      Parent::initalize(graph, nodes);
756    }
757   
758  };
759
760}
761
762#endif
Note: See TracBrowser for help on using the repository browser.