COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 1998:2ba916d7aae3

Last change on this file since 1998:2ba916d7aae3 was 1990:15fb7a4ea6be, checked in by Balazs Dezso, 18 years ago

Some classes assumed that the GraphMaps? should be inherited
from an ObserverBase?. These classes parents replaced with
DefaultMap? which cause that the graph maps should not be
inherited from the ObserverBase?.

File size: 17.8 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      typedef typename _Graph::template NodeMap<_Value> Parent;
210      explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
211        : Parent(*edgeset.graph) { }
212      NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
213        : Parent(*edgeset.graph, value) { }
214    };
215
216  };
217
218  /// \ingroup semi_adaptors
219  ///
220  /// \brief Graph using a node set of another graph and an
221  /// own edge set.
222  ///
223  /// This structure can be used to establish another graph over a node set
224  /// of an existing one. The node iterator will go through the nodes of the
225  /// original graph.
226  ///
227  /// \param _Graph The type of the graph which shares its node set with
228  /// this class. Its interface must conform to the \ref concept::StaticGraph
229  /// "StaticGraph" concept.
230  ///
231  /// In the edge extension and removing it conforms to the
232  /// \ref concept::ErasableGraph "ErasableGraph" concept.
233  template <typename _Graph>
234  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
235
236  public:
237
238    typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
239   
240    typedef typename Parent::Node Node;
241    typedef typename Parent::Edge Edge;
242   
243    typedef _Graph Graph;
244
245
246    typedef typename Parent::NodesImplBase NodesImplBase;
247
248    void eraseNode(const Node& node) {
249      Edge edge;
250      Parent::firstOut(edge, node);
251      while (edge != INVALID ) {
252        erase(edge);
253        Parent::firstOut(edge, node);
254      }
255
256      Parent::firstIn(edge, node);
257      while (edge != INVALID ) {
258        erase(edge);
259        Parent::firstIn(edge, node);
260      }
261    }
262   
263    void clearNodes() {
264      Parent::clear();
265    }
266
267    class NodesImpl : public NodesImplBase {
268    public:
269      typedef NodesImplBase Parent;
270     
271      NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
272        : Parent(graph), _edgeset(edgeset) {}
273
274      virtual ~NodesImpl() {}
275     
276    protected:
277
278      virtual void erase(const Node& node) {
279        _edgeset.eraseNode(node);
280        Parent::erase(node);
281      }
282      virtual void erase(const std::vector<Node>& nodes) {
283        for (int i = 0; i < (int)nodes.size(); ++i) {
284          _edgeset.eraseNode(nodes[i]);
285        }
286        Parent::erase(nodes);
287      }
288      virtual void clear() {
289        _edgeset.clearNodes();
290        Parent::clear();
291      }
292
293    private:
294      ListEdgeSet& _edgeset;
295    };
296
297    NodesImpl nodes;
298   
299  public:
300
301    /// \brief Constructor of the adaptor.
302    ///
303    /// Constructor of the adaptor.
304    ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
305      Parent::initalize(graph, nodes);
306    }
307   
308  };
309
310  /// \ingroup semi_adaptors
311  ///
312  /// \brief Graph using a node set of another graph and an
313  /// own uedge set.
314  ///
315  /// This structure can be used to establish another graph over a node set
316  /// of an existing one. The node iterator will go through the nodes of the
317  /// original graph.
318  ///
319  /// \param _Graph The type of the graph which shares its node set with
320  /// this class. Its interface must conform to the \ref concept::StaticGraph
321  /// "StaticGraph" concept.
322  ///
323  /// In the edge extension and removing it conforms to the
324  /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
325  template <typename _Graph>
326  class ListUEdgeSet
327    : public UEdgeSetExtender<UGraphBaseExtender<ListEdgeSetBase<_Graph> > > {
328
329  public:
330
331    typedef UEdgeSetExtender<UGraphBaseExtender<
332      ListEdgeSetBase<_Graph> > > Parent;
333   
334    typedef typename Parent::Node Node;
335    typedef typename Parent::Edge Edge;
336   
337    typedef _Graph Graph;
338
339
340    typedef typename Parent::NodesImplBase NodesImplBase;
341
342    void eraseNode(const Node& node) {
343      Edge edge;
344      Parent::firstOut(edge, node);
345      while (edge != INVALID ) {
346        erase(edge);
347        Parent::firstOut(edge, node);
348      }
349
350    }
351   
352    void clearNodes() {
353      Parent::clear();
354    }
355
356    class NodesImpl : public NodesImplBase {
357    public:
358      typedef NodesImplBase Parent;
359     
360      NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
361        : Parent(graph), _edgeset(edgeset) {}
362
363      virtual ~NodesImpl() {}
364     
365    protected:
366
367      virtual void erase(const Node& node) {
368        _edgeset.eraseNode(node);
369        Parent::erase(node);
370      }
371      virtual void erase(const std::vector<Node>& nodes) {
372        for (int i = 0; i < (int)nodes.size(); ++i) {
373          _edgeset.eraseNode(nodes[i]);
374        }
375        Parent::erase(nodes);
376      }
377      virtual void clear() {
378        _edgeset.clearNodes();
379        Parent::clear();
380      }
381
382    private:
383      ListUEdgeSet& _edgeset;
384    };
385
386    NodesImpl nodes;
387   
388  public:
389
390    /// \brief Constructor of the adaptor.
391    ///
392    /// Constructor of the adaptor.
393    ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
394      Parent::initalize(graph, nodes);
395    }
396   
397  };
398
399  template <typename _Graph>
400  class SmartEdgeSetBase {
401  public:
402
403    typedef _Graph Graph;
404    typedef typename Graph::Node Node;
405    typedef typename Graph::NodeIt NodeIt;
406
407  protected:
408
409    struct NodeT {
410      int first_out, first_in;
411      NodeT() : first_out(-1), first_in(-1) {}
412    };
413
414    typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
415
416    NodesImplBase* nodes;
417
418    struct EdgeT {
419      Node source, target;
420      int next_out, next_in;
421      EdgeT() {}
422    };
423
424    std::vector<EdgeT> edges;
425
426    const Graph* graph;
427
428    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
429      graph = &_graph;
430      nodes = &_nodes;
431    }
432   
433  public:
434
435    class Edge {
436      friend class SmartEdgeSetBase<Graph>;
437    protected:
438      Edge(int _id) : id(_id) {}
439      int id;
440    public:
441      Edge() {}
442      Edge(Invalid) : id(-1) {}
443      bool operator==(const Edge& edge) const { return id == edge.id; }
444      bool operator!=(const Edge& edge) const { return id != edge.id; }
445      bool operator<(const Edge& edge) const { return id < edge.id; }
446    };
447
448    SmartEdgeSetBase() {}
449
450    Edge addEdge(const Node& source, const Node& target) {
451      int n = edges.size();
452      edges.push_back(EdgeT());
453      edges[n].next_in = (*nodes)[target].first_in;
454      (*nodes)[target].first_in = n;
455      edges[n].next_out = (*nodes)[source].first_out;
456      (*nodes)[source].first_out = n;
457      edges[n].source = source;
458      edges[n].target = target;
459      return Edge(n);
460    }
461
462    void clear() {
463      Node node;
464      for (first(node); node != INVALID; next(node)) {
465        (*nodes)[node].first_in = -1;
466        (*nodes)[node].first_out = -1;
467      }
468      edges.clear();
469    }
470
471    void first(Node& node) const {
472      graph->first(node);
473    }
474
475    void next(Node& node) const {
476      graph->next(node);
477    }
478
479    void first(Edge& edge) const {
480      edge.id = edges.size() - 1;
481    }
482
483    void next(Edge& edge) const {
484      --edge.id;
485    }
486
487    void firstOut(Edge& edge, const Node& node) const {
488      edge.id = (*nodes)[node].first_out;   
489    }
490   
491    void nextOut(Edge& edge) const {
492      edge.id = edges[edge.id].next_out;       
493    }
494
495    void firstIn(Edge& edge, const Node& node) const {
496      edge.id = (*nodes)[node].first_in;         
497    }
498
499    void nextIn(Edge& edge) const {
500      edge.id = edges[edge.id].next_in;   
501    }
502
503    int id(const Node& node) const { return graph->id(node); }
504    int id(const Edge& edge) const { return edge.id; }
505
506    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
507    Edge edgeFromId(int id) const { return Edge(id); }
508
509    int maxNodeId() const { return graph->maxNodeId(); };
510    int maxEdgeId() const { return edges.size() - 1; }
511
512    Node source(const Edge& edge) const { return edges[edge.id].source;}
513    Node target(const Edge& edge) const { return edges[edge.id].target;}
514
515    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
516
517    NodeNotifier& getNotifier(Node) const {
518      return graph->getNotifier(Node());
519    }
520
521    template <typename _Value>
522    class NodeMap : public Graph::template NodeMap<_Value> {
523    public:
524      typedef typename _Graph::template NodeMap<_Value> Parent;
525      explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
526        : Parent(*edgeset.graph) { }
527      NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
528        : Parent(*edgeset.graph, value) { }
529    };
530
531  };
532
533
534  /// \ingroup semi_adaptors
535  ///
536  /// \brief Graph using a node set of another graph and an
537  /// own edge set.
538  ///
539  /// This structure can be used to establish another graph over a node set
540  /// of an existing one. The node iterator will go through the nodes of the
541  /// original graph.
542  ///
543  /// \param _Graph The type of the graph which shares its node set with
544  /// this class. Its interface must conform to the \ref concept::StaticGraph
545  /// "StaticGraph" concept.
546  ///
547  /// In the edge extension and removing it conforms to the
548  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
549  template <typename _Graph>
550  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
551
552  public:
553
554    typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
555   
556    typedef typename Parent::Node Node;
557    typedef typename Parent::Edge Edge;
558   
559    typedef _Graph Graph;
560
561    class UnsupportedOperation : public LogicError {
562    public:
563      virtual const char* exceptionName() const {
564        return "lemon::SmartEdgeSet::UnsupportedOperation";
565      }
566    };
567   
568
569
570  protected:
571
572    typedef typename Parent::NodesImplBase NodesImplBase;
573
574    void eraseNode(const Node&) {
575      throw UnsupportedOperation();
576    }
577   
578    void clearNodes() {
579      Parent::clear();
580    }
581
582    class NodesImpl : public NodesImplBase {
583    public:
584      typedef NodesImplBase Parent;
585     
586      NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
587        : Parent(graph), _edgeset(edgeset) {}
588
589      virtual ~NodesImpl() {}
590     
591    protected:
592
593      virtual void erase(const Node& node) {
594        _edgeset.eraseNode(node);
595        Parent::erase(node);
596      }
597      virtual void erase(const std::vector<Node>& nodes) {
598        for (int i = 0; i < (int)nodes.size(); ++i) {
599          _edgeset.eraseNode(nodes[i]);
600        }
601        Parent::erase(nodes);
602      }
603      virtual void clear() {
604        _edgeset.clearNodes();
605        Parent::clear();
606      }
607
608    private:
609      SmartEdgeSet& _edgeset;
610    };
611
612    NodesImpl nodes;
613   
614  public:
615
616    /// \brief Constructor of the adaptor.
617    ///
618    /// Constructor of the adaptor.
619    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
620      Parent::initalize(graph, nodes);
621    }
622   
623  };
624
625  /// \ingroup semi_adaptors
626  ///
627  /// \brief Graph using a node set of another graph and an
628  /// own uedge set.
629  ///
630  /// This structure can be used to establish another graph over a node set
631  /// of an existing one. The node iterator will go through the nodes of the
632  /// original graph.
633  ///
634  /// \param _Graph The type of the graph which shares its node set with
635  /// this class. Its interface must conform to the \ref concept::StaticGraph
636  /// "StaticGraph" concept.
637  ///
638  /// In the edge extension and removing it conforms to the
639  /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
640  template <typename _Graph>
641  class SmartUEdgeSet
642    : public UEdgeSetExtender<UGraphBaseExtender<SmartEdgeSetBase<_Graph> > > {
643
644  public:
645
646    typedef UEdgeSetExtender<UGraphBaseExtender<
647      SmartEdgeSetBase<_Graph> > > Parent;
648   
649    typedef typename Parent::Node Node;
650    typedef typename Parent::Edge Edge;
651   
652    typedef _Graph Graph;
653
654    class UnsupportedOperation : public LogicError {
655    public:
656      virtual const char* exceptionName() const {
657        return "lemon::SmartUEdgeSet::UnsupportedOperation";
658      }
659    };
660
661  protected:
662
663    typedef typename Parent::NodesImplBase NodesImplBase;
664
665    void eraseNode(const Node&) {
666      throw UnsupportedOperation();
667    }
668   
669    void clearNodes() {
670      Parent::clear();
671    }
672
673    class NodesImpl : public NodesImplBase {
674    public:
675      typedef NodesImplBase Parent;
676     
677      NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
678        : Parent(graph), _edgeset(edgeset) {}
679
680      virtual ~NodesImpl() {}
681     
682    protected:
683
684      virtual void erase(const Node& node) {
685        _edgeset.eraseNode(node);
686        Parent::erase(node);
687      }
688      virtual void erase(const std::vector<Node>& nodes) {
689        for (int i = 0; i < (int)nodes.size(); ++i) {
690          _edgeset.eraseNode(nodes[i]);
691        }
692        Parent::erase(nodes);
693      }
694      virtual void clear() {
695        _edgeset.clearNodes();
696        Parent::clear();
697      }
698
699    private:
700      SmartUEdgeSet& _edgeset;
701    };
702
703    NodesImpl nodes;
704   
705  public:
706
707    /// \brief Constructor of the adaptor.
708    ///
709    /// Constructor of the adaptor.
710    SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
711      Parent::initalize(graph, nodes);
712    }
713   
714  };
715
716}
717
718#endif
Note: See TracBrowser for help on using the repository browser.