COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 2115:4cd528a30ec1

Last change on this file since 2115:4cd528a30ec1 was 2115:4cd528a30ec1, checked in by Balazs Dezso, 13 years ago

Splitted graph files

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