COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 2000:ebcc93ead7da

Last change on this file since 2000:ebcc93ead7da was 1999:2ff283124dfc, checked in by Balazs Dezso, 14 years ago

Clarifing alteration observing system
It is directly connected now to a container

File size: 18.0 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& node) {
575      if (Parent::InEdgeIt(*this, node) == INVALID &&
576          Parent::OutEdgeIt(*this, node) == INVALID) {
577        return;
578      }
579      throw UnsupportedOperation();
580    }
581   
582    void clearNodes() {
583      Parent::clear();
584    }
585
586    class NodesImpl : public NodesImplBase {
587    public:
588      typedef NodesImplBase Parent;
589     
590      NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
591        : Parent(graph), _edgeset(edgeset) {}
592
593      virtual ~NodesImpl() {}
594     
595    protected:
596
597      virtual void erase(const Node& node) {
598        _edgeset.eraseNode(node);
599        Parent::erase(node);
600      }
601      virtual void erase(const std::vector<Node>& nodes) {
602        for (int i = 0; i < (int)nodes.size(); ++i) {
603          _edgeset.eraseNode(nodes[i]);
604        }
605        Parent::erase(nodes);
606      }
607      virtual void clear() {
608        _edgeset.clearNodes();
609        Parent::clear();
610      }
611
612    private:
613      SmartEdgeSet& _edgeset;
614    };
615
616    NodesImpl nodes;
617   
618  public:
619
620    /// \brief Constructor of the adaptor.
621    ///
622    /// Constructor of the adaptor.
623    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
624      Parent::initalize(graph, nodes);
625    }
626   
627  };
628
629  /// \ingroup semi_adaptors
630  ///
631  /// \brief Graph using a node set of another graph and an
632  /// own uedge set.
633  ///
634  /// This structure can be used to establish another graph over a node set
635  /// of an existing one. The node iterator will go through the nodes of the
636  /// original graph.
637  ///
638  /// \param _Graph The type of the graph which shares its node set with
639  /// this class. Its interface must conform to the \ref concept::StaticGraph
640  /// "StaticGraph" concept.
641  ///
642  /// In the edge extension and removing it conforms to the
643  /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
644  template <typename _Graph>
645  class SmartUEdgeSet
646    : public UEdgeSetExtender<UGraphBaseExtender<SmartEdgeSetBase<_Graph> > > {
647
648  public:
649
650    typedef UEdgeSetExtender<UGraphBaseExtender<
651      SmartEdgeSetBase<_Graph> > > Parent;
652   
653    typedef typename Parent::Node Node;
654    typedef typename Parent::Edge Edge;
655   
656    typedef _Graph Graph;
657
658    class UnsupportedOperation : public LogicError {
659    public:
660      virtual const char* exceptionName() const {
661        return "lemon::SmartUEdgeSet::UnsupportedOperation";
662      }
663    };
664
665  protected:
666
667    typedef typename Parent::NodesImplBase NodesImplBase;
668
669    void eraseNode(const Node& node) {
670      if (Parent::IncEdgeIt(*this, node) == INVALID) {
671        return;
672      }
673      throw UnsupportedOperation();
674    }
675   
676    void clearNodes() {
677      Parent::clear();
678    }
679
680    class NodesImpl : public NodesImplBase {
681    public:
682      typedef NodesImplBase Parent;
683     
684      NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
685        : Parent(graph), _edgeset(edgeset) {}
686
687      virtual ~NodesImpl() {}
688     
689    protected:
690
691      virtual void erase(const Node& node) {
692        _edgeset.eraseNode(node);
693        Parent::erase(node);
694      }
695      virtual void erase(const std::vector<Node>& nodes) {
696        for (int i = 0; i < (int)nodes.size(); ++i) {
697          _edgeset.eraseNode(nodes[i]);
698        }
699        Parent::erase(nodes);
700      }
701      virtual void clear() {
702        _edgeset.clearNodes();
703        Parent::clear();
704      }
705
706    private:
707      SmartUEdgeSet& _edgeset;
708    };
709
710    NodesImpl nodes;
711   
712  public:
713
714    /// \brief Constructor of the adaptor.
715    ///
716    /// Constructor of the adaptor.
717    SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
718      Parent::initalize(graph, nodes);
719    }
720   
721  };
722
723}
724
725#endif
Note: See TracBrowser for help on using the repository browser.