COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 1979:c2992fd74dad

Last change on this file since 1979:c2992fd74dad was 1979:c2992fd74dad, checked in by Balazs Dezso, 14 years ago

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

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