COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 2040:c7bd55c0d820

Last change on this file since 2040:c7bd55c0d820 was 2031:080d51024ac5, checked in by Balazs Dezso, 18 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

File size: 18.5 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
23#include <lemon/bits/default_map.h>
24#include <lemon/bits/edge_set_extender.h>
25
26/// \ingroup graphs
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& source, const Node& target) {
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)[target].first_in;
99      if ((*nodes)[target].first_in != -1) {
100        edges[(*nodes)[target].first_in].prev_in = n;
101      }
102      (*nodes)[target].first_in = n;
103      edges[n].next_out = (*nodes)[source].first_out;
104      if ((*nodes)[source].first_out != -1) {
105        edges[(*nodes)[source].first_out].prev_out = n;
106      }
107      (*nodes)[source].first_out = n;
108      edges[n].source = source;
109      edges[n].target = target;
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 id) const { return graph->nodeFromId(id); }
192    Edge edgeFromId(int id) const { return Edge(id); }
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& getNotifier(Node) const {
203      return graph->getNotifier(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 concept::StaticGraph
242  /// "StaticGraph" concept.
243  ///
244  /// In the edge extension and removing it conforms to the
245  /// \ref concept::ErasableGraph "ErasableGraph" concept.
246  template <typename _Graph>
247  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
248
249  public:
250
251    typedef EdgeSetExtender<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 UEdgeSetExtender<UGraphBaseExtender<ListEdgeSetBase<_Graph> > > {
341
342  public:
343
344    typedef UEdgeSetExtender<UGraphBaseExtender<
345      ListEdgeSetBase<_Graph> > > Parent;
346   
347    typedef typename Parent::Node Node;
348    typedef typename Parent::Edge Edge;
349   
350    typedef _Graph Graph;
351
352
353    typedef typename Parent::NodesImplBase NodesImplBase;
354
355    void eraseNode(const Node& node) {
356      Edge edge;
357      Parent::firstOut(edge, node);
358      while (edge != INVALID ) {
359        erase(edge);
360        Parent::firstOut(edge, node);
361      }
362
363    }
364   
365    void clearNodes() {
366      Parent::clear();
367    }
368
369    class NodesImpl : public NodesImplBase {
370    public:
371      typedef NodesImplBase Parent;
372     
373      NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
374        : Parent(graph), _edgeset(edgeset) {}
375
376      virtual ~NodesImpl() {}
377     
378    protected:
379
380      virtual void erase(const Node& node) {
381        _edgeset.eraseNode(node);
382        Parent::erase(node);
383      }
384      virtual void erase(const std::vector<Node>& nodes) {
385        for (int i = 0; i < (int)nodes.size(); ++i) {
386          _edgeset.eraseNode(nodes[i]);
387        }
388        Parent::erase(nodes);
389      }
390      virtual void clear() {
391        _edgeset.clearNodes();
392        Parent::clear();
393      }
394
395    private:
396      ListUEdgeSet& _edgeset;
397    };
398
399    NodesImpl nodes;
400   
401  public:
402
403    /// \brief Constructor of the adaptor.
404    ///
405    /// Constructor of the adaptor.
406    ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
407      Parent::initalize(graph, nodes);
408    }
409   
410  };
411
412  template <typename _Graph>
413  class SmartEdgeSetBase {
414  public:
415
416    typedef _Graph Graph;
417    typedef typename Graph::Node Node;
418    typedef typename Graph::NodeIt NodeIt;
419
420  protected:
421
422    struct NodeT {
423      int first_out, first_in;
424      NodeT() : first_out(-1), first_in(-1) {}
425    };
426
427    typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
428
429    NodesImplBase* nodes;
430
431    struct EdgeT {
432      Node source, target;
433      int next_out, next_in;
434      EdgeT() {}
435    };
436
437    std::vector<EdgeT> edges;
438
439    const Graph* graph;
440
441    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
442      graph = &_graph;
443      nodes = &_nodes;
444    }
445   
446  public:
447
448    class Edge {
449      friend class SmartEdgeSetBase<Graph>;
450    protected:
451      Edge(int _id) : id(_id) {}
452      int id;
453    public:
454      Edge() {}
455      Edge(Invalid) : id(-1) {}
456      bool operator==(const Edge& edge) const { return id == edge.id; }
457      bool operator!=(const Edge& edge) const { return id != edge.id; }
458      bool operator<(const Edge& edge) const { return id < edge.id; }
459    };
460
461    SmartEdgeSetBase() {}
462
463    Edge addEdge(const Node& source, const Node& target) {
464      int n = edges.size();
465      edges.push_back(EdgeT());
466      edges[n].next_in = (*nodes)[target].first_in;
467      (*nodes)[target].first_in = n;
468      edges[n].next_out = (*nodes)[source].first_out;
469      (*nodes)[source].first_out = n;
470      edges[n].source = source;
471      edges[n].target = target;
472      return Edge(n);
473    }
474
475    void clear() {
476      Node node;
477      for (first(node); node != INVALID; next(node)) {
478        (*nodes)[node].first_in = -1;
479        (*nodes)[node].first_out = -1;
480      }
481      edges.clear();
482    }
483
484    void first(Node& node) const {
485      graph->first(node);
486    }
487
488    void next(Node& node) const {
489      graph->next(node);
490    }
491
492    void first(Edge& edge) const {
493      edge.id = edges.size() - 1;
494    }
495
496    void next(Edge& edge) const {
497      --edge.id;
498    }
499
500    void firstOut(Edge& edge, const Node& node) const {
501      edge.id = (*nodes)[node].first_out;   
502    }
503   
504    void nextOut(Edge& edge) const {
505      edge.id = edges[edge.id].next_out;       
506    }
507
508    void firstIn(Edge& edge, const Node& node) const {
509      edge.id = (*nodes)[node].first_in;         
510    }
511
512    void nextIn(Edge& edge) const {
513      edge.id = edges[edge.id].next_in;   
514    }
515
516    int id(const Node& node) const { return graph->id(node); }
517    int id(const Edge& edge) const { return edge.id; }
518
519    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
520    Edge edgeFromId(int id) const { return Edge(id); }
521
522    int maxNodeId() const { return graph->maxNodeId(); };
523    int maxEdgeId() const { return edges.size() - 1; }
524
525    Node source(const Edge& edge) const { return edges[edge.id].source;}
526    Node target(const Edge& edge) const { return edges[edge.id].target;}
527
528    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
529
530    NodeNotifier& getNotifier(Node) const {
531      return graph->getNotifier(Node());
532    }
533
534    template <typename _Value>
535    class NodeMap : public Graph::template NodeMap<_Value> {
536    public:
537
538      typedef typename _Graph::template NodeMap<_Value> Parent;
539
540      explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
541        : Parent(*edgeset.graph) { }
542
543      NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
544        : Parent(*edgeset.graph, value) { }
545
546      NodeMap& operator=(const NodeMap& cmap) {
547        return operator=<NodeMap>(cmap);
548      }
549
550      template <typename CMap>
551      NodeMap& operator=(const CMap& cmap) {
552        Parent::operator=(cmap);
553        return *this;
554      }
555    };
556
557  };
558
559
560  /// \ingroup semi_adaptors
561  ///
562  /// \brief Graph using a node set of another graph and an
563  /// own edge set.
564  ///
565  /// This structure can be used to establish another graph over a node set
566  /// of an existing one. The node iterator will go through the nodes of the
567  /// original graph.
568  ///
569  /// \param _Graph The type of the graph which shares its node set with
570  /// this class. Its interface must conform to the \ref concept::StaticGraph
571  /// "StaticGraph" concept.
572  ///
573  /// In the edge extension and removing it conforms to the
574  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
575  template <typename _Graph>
576  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
577
578  public:
579
580    typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
581   
582    typedef typename Parent::Node Node;
583    typedef typename Parent::Edge Edge;
584   
585    typedef _Graph Graph;
586
587    class UnsupportedOperation : public LogicError {
588    public:
589      virtual const char* exceptionName() const {
590        return "lemon::SmartEdgeSet::UnsupportedOperation";
591      }
592    };
593   
594
595
596  protected:
597
598    typedef typename Parent::NodesImplBase NodesImplBase;
599
600    void eraseNode(const Node& node) {
601      if (Parent::InEdgeIt(*this, node) == INVALID &&
602          Parent::OutEdgeIt(*this, node) == INVALID) {
603        return;
604      }
605      throw UnsupportedOperation();
606    }
607   
608    void clearNodes() {
609      Parent::clear();
610    }
611
612    class NodesImpl : public NodesImplBase {
613    public:
614      typedef NodesImplBase Parent;
615     
616      NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
617        : Parent(graph), _edgeset(edgeset) {}
618
619      virtual ~NodesImpl() {}
620     
621    protected:
622
623      virtual void erase(const Node& node) {
624        _edgeset.eraseNode(node);
625        Parent::erase(node);
626      }
627      virtual void erase(const std::vector<Node>& nodes) {
628        for (int i = 0; i < (int)nodes.size(); ++i) {
629          _edgeset.eraseNode(nodes[i]);
630        }
631        Parent::erase(nodes);
632      }
633      virtual void clear() {
634        _edgeset.clearNodes();
635        Parent::clear();
636      }
637
638    private:
639      SmartEdgeSet& _edgeset;
640    };
641
642    NodesImpl nodes;
643   
644  public:
645
646    /// \brief Constructor of the adaptor.
647    ///
648    /// Constructor of the adaptor.
649    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
650      Parent::initalize(graph, nodes);
651    }
652   
653  };
654
655  /// \ingroup semi_adaptors
656  ///
657  /// \brief Graph using a node set of another graph and an
658  /// own uedge set.
659  ///
660  /// This structure can be used to establish another graph over a node set
661  /// of an existing one. The node iterator will go through the nodes of the
662  /// original graph.
663  ///
664  /// \param _Graph The type of the graph which shares its node set with
665  /// this class. Its interface must conform to the \ref concept::StaticGraph
666  /// "StaticGraph" concept.
667  ///
668  /// In the edge extension and removing it conforms to the
669  /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
670  template <typename _Graph>
671  class SmartUEdgeSet
672    : public UEdgeSetExtender<UGraphBaseExtender<SmartEdgeSetBase<_Graph> > > {
673
674  public:
675
676    typedef UEdgeSetExtender<UGraphBaseExtender<
677      SmartEdgeSetBase<_Graph> > > Parent;
678   
679    typedef typename Parent::Node Node;
680    typedef typename Parent::Edge Edge;
681   
682    typedef _Graph Graph;
683
684    class UnsupportedOperation : public LogicError {
685    public:
686      virtual const char* exceptionName() const {
687        return "lemon::SmartUEdgeSet::UnsupportedOperation";
688      }
689    };
690
691  protected:
692
693    typedef typename Parent::NodesImplBase NodesImplBase;
694
695    void eraseNode(const Node& node) {
696      if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
697        return;
698      }
699      throw UnsupportedOperation();
700    }
701   
702    void clearNodes() {
703      Parent::clear();
704    }
705
706    class NodesImpl : public NodesImplBase {
707    public:
708      typedef NodesImplBase Parent;
709     
710      NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
711        : Parent(graph), _edgeset(edgeset) {}
712
713      virtual ~NodesImpl() {}
714     
715    protected:
716
717      virtual void erase(const Node& node) {
718        _edgeset.eraseNode(node);
719        Parent::erase(node);
720      }
721      virtual void erase(const std::vector<Node>& nodes) {
722        for (int i = 0; i < (int)nodes.size(); ++i) {
723          _edgeset.eraseNode(nodes[i]);
724        }
725        Parent::erase(nodes);
726      }
727      virtual void clear() {
728        _edgeset.clearNodes();
729        Parent::clear();
730      }
731
732    private:
733      SmartUEdgeSet& _edgeset;
734    };
735
736    NodesImpl nodes;
737   
738  public:
739
740    /// \brief Constructor of the adaptor.
741    ///
742    /// Constructor of the adaptor.
743    SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
744      Parent::initalize(graph, nodes);
745    }
746   
747  };
748
749}
750
751#endif
Note: See TracBrowser for help on using the repository browser.