COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 2224:f973894da54e

Last change on this file since 2224:f973894da54e was 2224:f973894da54e, checked in by Balazs Dezso, 18 years ago

Moving the file into correct group

File size: 19.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 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& 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::Graph
242  /// "Graph" concept.
243  ///
244  /// In the edge extension and removing it conforms to the
245  /// \ref concept::Graph "Graph" 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::Graph
334  /// "Graph" concept.
335  ///
336  /// In the edge extension and removing it conforms to the
337  /// \ref concept::UGraph "UGraph" concept.
338  template <typename _Graph>
339  class ListUEdgeSet
340    : public UEdgeSetExtender<UndirGraphExtender<ListEdgeSetBase<_Graph> > > {
341
342  public:
343
344    typedef UEdgeSetExtender<UndirGraphExtender<
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::Graph
571  /// "Graph" concept.
572  ///
573  /// In the edge extension and removing it conforms to the
574  /// \ref concept::Graph "Graph" 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  protected:
588
589    typedef typename Parent::NodesImplBase NodesImplBase;
590
591    void eraseNode(const Node& node) {
592      if (Parent::InEdgeIt(*this, node) == INVALID &&
593          Parent::OutEdgeIt(*this, node) == INVALID) {
594        return;
595      }
596      throw typename NodesImplBase::Notifier::ImmediateDetach();
597    }
598   
599    void clearNodes() {
600      Parent::clear();
601    }
602
603    class NodesImpl : public NodesImplBase {
604    public:
605      typedef NodesImplBase Parent;
606     
607      NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
608        : Parent(graph), _edgeset(edgeset) {}
609
610      virtual ~NodesImpl() {}
611     
612      bool attached() const {
613        return Parent::attached();
614      }
615
616    protected:
617
618      virtual void erase(const Node& node) {
619        try {
620          _edgeset.eraseNode(node);
621          Parent::erase(node);
622        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
623          Parent::clear();
624          throw;
625        }
626      }
627      virtual void erase(const std::vector<Node>& nodes) {
628        try {
629          for (int i = 0; i < (int)nodes.size(); ++i) {
630            _edgeset.eraseNode(nodes[i]);
631          }
632          Parent::erase(nodes);
633        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
634          Parent::clear();
635          throw;
636        }
637      }
638      virtual void clear() {
639        _edgeset.clearNodes();
640        Parent::clear();
641      }
642
643    private:
644      SmartEdgeSet& _edgeset;
645    };
646
647    NodesImpl nodes;
648   
649  public:
650
651    /// \brief Constructor of the adaptor.
652    ///
653    /// Constructor of the adaptor.
654    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
655      Parent::initalize(graph, nodes);
656    }
657
658    bool valid() const {
659      return nodes.attached();
660    }
661   
662  };
663
664  /// \ingroup semi_adaptors
665  ///
666  /// \brief Graph using a node set of another graph and an
667  /// own uedge set.
668  ///
669  /// This structure can be used to establish another graph over a node set
670  /// of an existing one. The node iterator will go through the nodes of the
671  /// original graph.
672  ///
673  /// \param _Graph The type of the graph which shares its node set with
674  /// this class. Its interface must conform to the \ref concept::Graph
675  /// "Graph" concept.
676  ///
677  /// In the edge extension and removing it conforms to the
678  /// \ref concept::UGraph "UGraph" concept.
679  template <typename _Graph>
680  class SmartUEdgeSet
681    : public UEdgeSetExtender<UndirGraphExtender<SmartEdgeSetBase<_Graph> > > {
682
683  public:
684
685    typedef UEdgeSetExtender<UndirGraphExtender<
686      SmartEdgeSetBase<_Graph> > > Parent;
687   
688    typedef typename Parent::Node Node;
689    typedef typename Parent::Edge Edge;
690   
691    typedef _Graph Graph;
692
693  protected:
694
695    typedef typename Parent::NodesImplBase NodesImplBase;
696
697    void eraseNode(const Node& node) {
698      if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
699        return;
700      }
701      throw typename NodesImplBase::Notifier::ImmediateDetach();
702    }
703   
704    void clearNodes() {
705      Parent::clear();
706    }
707
708    class NodesImpl : public NodesImplBase {
709    public:
710      typedef NodesImplBase Parent;
711     
712      NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
713        : Parent(graph), _edgeset(edgeset) {}
714
715      virtual ~NodesImpl() {}
716
717      bool attached() const {
718        return Parent::attached();
719      }
720     
721    protected:
722
723      virtual void erase(const Node& node) {
724        try {
725          _edgeset.eraseNode(node);
726          Parent::erase(node);
727        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
728          Parent::clear();
729          throw;
730        }
731      }
732      virtual void erase(const std::vector<Node>& nodes) {
733        try {
734          for (int i = 0; i < (int)nodes.size(); ++i) {
735            _edgeset.eraseNode(nodes[i]);
736          }
737          Parent::erase(nodes);
738        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
739          Parent::clear();
740          throw;
741        }
742      }
743      virtual void clear() {
744        _edgeset.clearNodes();
745        Parent::clear();
746      }
747
748    private:
749      SmartUEdgeSet& _edgeset;
750    };
751
752    NodesImpl nodes;
753   
754  public:
755
756    /// \brief Constructor of the adaptor.
757    ///
758    /// Constructor of the adaptor.
759    SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
760      Parent::initalize(graph, nodes);
761    }
762
763    bool valid() const {
764      return nodes.attached();
765    }
766   
767  };
768
769}
770
771#endif
Note: See TracBrowser for help on using the repository browser.