COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 2116:b6a68c15a6a3

Last change on this file since 2116:b6a68c15a6a3 was 2116:b6a68c15a6a3, checked in by Balazs Dezso, 13 years ago

Revert splitted files

File size: 18.4 KB
RevLine 
[1842]1/* -*- C++ -*-
2 *
[1956]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
[1842]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
[1979]22
[1990]23#include <lemon/bits/default_map.h>
[1979]24#include <lemon/bits/edge_set_extender.h>
[1962]25
[1842]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
[1990]49    typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
[1842]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;
[1962]99      if ((*nodes)[target].first_in != -1) {
100        edges[(*nodes)[target].first_in].prev_in = n;
101      }
[1842]102      (*nodes)[target].first_in = n;
103      edges[n].next_out = (*nodes)[source].first_out;
[1962]104      if ((*nodes)[source].first_out != -1) {
105        edges[(*nodes)[source].first_out].prev_out = n;
106      }
[1842]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() {
[1962]136      Node node;
137      for (first(node); node != INVALID; next(node)) {
138        (*nodes)[node].first_in = -1;
139        (*nodes)[node].first_out = -1;
140      }
[1842]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
[1962]191    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
[1842]192    Edge edgeFromId(int id) const { return Edge(id); }
193
[1962]194    int maxNodeId() const { return graph->maxNodeId(); };
[1842]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
[1990]200    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
201
202    NodeNotifier& getNotifier(Node) const {
203      return graph->getNotifier(Node());
204    }
205
[1842]206    template <typename _Value>
207    class NodeMap : public Graph::template NodeMap<_Value> {
208    public:
[2031]209
[1842]210      typedef typename _Graph::template NodeMap<_Value> Parent;
[2031]211
[1842]212      explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
[2031]213        : Parent(*edgeset.graph) {}
214
[1842]215      NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
[2031]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      }
[1842]227    };
228
229  };
230
[1866]231  /// \ingroup semi_adaptors
[1842]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
[2111]241  /// this class. Its interface must conform to the \ref concept::Graph
242  /// "Graph" concept.
[1842]243  ///
244  /// In the edge extension and removing it conforms to the
[2111]245  /// \ref concept::Graph "Graph" concept.
[1842]246  template <typename _Graph>
[1979]247  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
[1842]248
249  public:
250
[1979]251    typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
[1842]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) {}
[1962]286
287      virtual ~NodesImpl() {}
[1842]288     
289    protected:
290
291      virtual void erase(const Node& node) {
292        _edgeset.eraseNode(node);
293        Parent::erase(node);
294      }
[1962]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      }
[1842]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
[1866]323  /// \ingroup semi_adaptors
[1842]324  ///
325  /// \brief Graph using a node set of another graph and an
[1909]326  /// own uedge set.
[1842]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
[2111]333  /// this class. Its interface must conform to the \ref concept::Graph
334  /// "Graph" concept.
[1842]335  ///
336  /// In the edge extension and removing it conforms to the
[2111]337  /// \ref concept::UGraph "UGraph" concept.
[1842]338  template <typename _Graph>
[1979]339  class ListUEdgeSet
[2076]340    : public UEdgeSetExtender<UndirGraphExtender<ListEdgeSetBase<_Graph> > > {
[1842]341
342  public:
343
[2076]344    typedef UEdgeSetExtender<UndirGraphExtender<
[1979]345      ListEdgeSetBase<_Graph> > > Parent;
[1842]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     
[1909]373      NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
[1842]374        : Parent(graph), _edgeset(edgeset) {}
[1962]375
376      virtual ~NodesImpl() {}
[1842]377     
378    protected:
379
380      virtual void erase(const Node& node) {
381        _edgeset.eraseNode(node);
382        Parent::erase(node);
383      }
[1866]384      virtual void erase(const std::vector<Node>& nodes) {
[1962]385        for (int i = 0; i < (int)nodes.size(); ++i) {
[1866]386          _edgeset.eraseNode(nodes[i]);
387        }
388        Parent::erase(nodes);
389      }
[1842]390      virtual void clear() {
391        _edgeset.clearNodes();
392        Parent::clear();
393      }
394
395    private:
[1909]396      ListUEdgeSet& _edgeset;
[1842]397    };
398
399    NodesImpl nodes;
400   
401  public:
402
403    /// \brief Constructor of the adaptor.
404    ///
405    /// Constructor of the adaptor.
[1909]406    ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
[1842]407      Parent::initalize(graph, nodes);
408    }
409   
410  };
411
[1962]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
[1990]427    typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
[1962]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
[1990]528    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
529
530    NodeNotifier& getNotifier(Node) const {
531      return graph->getNotifier(Node());
532    }
533
[1962]534    template <typename _Value>
535    class NodeMap : public Graph::template NodeMap<_Value> {
536    public:
[2031]537
[1962]538      typedef typename _Graph::template NodeMap<_Value> Parent;
[2031]539
[1962]540      explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
541        : Parent(*edgeset.graph) { }
[2031]542
[1962]543      NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
544        : Parent(*edgeset.graph, value) { }
[2031]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      }
[1962]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
[2111]570  /// this class. Its interface must conform to the \ref concept::Graph
571  /// "Graph" concept.
[1962]572  ///
573  /// In the edge extension and removing it conforms to the
[2111]574  /// \ref concept::Graph "Graph" concept.
[1962]575  template <typename _Graph>
[1979]576  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
[1962]577
578  public:
579
[1979]580    typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
[1962]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
[1999]600    void eraseNode(const Node& node) {
601      if (Parent::InEdgeIt(*this, node) == INVALID &&
602          Parent::OutEdgeIt(*this, node) == INVALID) {
603        return;
604      }
[1962]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
[2111]665  /// this class. Its interface must conform to the \ref concept::Graph
666  /// "Graph" concept.
[1962]667  ///
668  /// In the edge extension and removing it conforms to the
[2111]669  /// \ref concept::UGraph "UGraph" concept.
[1962]670  template <typename _Graph>
[1979]671  class SmartUEdgeSet
[2076]672    : public UEdgeSetExtender<UndirGraphExtender<SmartEdgeSetBase<_Graph> > > {
[1962]673
674  public:
675
[2076]676    typedef UEdgeSetExtender<UndirGraphExtender<
[1979]677      SmartEdgeSetBase<_Graph> > > Parent;
[1962]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
[1999]695    void eraseNode(const Node& node) {
[2031]696      if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
[1999]697        return;
698      }
[1962]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
[1842]749}
750
751#endif
Note: See TracBrowser for help on using the repository browser.