COIN-OR::LEMON - Graph Library

source: lemon/lemon/graph_adaptor.h @ 430:05357da973ce

Last change on this file since 430:05357da973ce was 430:05357da973ce, checked in by Balazs Dezso <deba@…>, 11 years ago

Port graph adaptors from svn -r3498 (#67)

File size: 36.5 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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_GRAPH_ADAPTOR_H
20#define LEMON_GRAPH_ADAPTOR_H
21
22///\ingroup graph_adaptors
23///\file
24///\brief Several graph adaptors.
25///
26///This file contains several useful undirected graph adaptor classes.
27
28#include <lemon/core.h>
29#include <lemon/maps.h>
30#include <lemon/bits/graph_adaptor_extender.h>
31
32namespace lemon {
33
34  /// \brief Base type for the Graph Adaptors
35  ///
36  /// This is the base type for most of LEMON graph adaptors.
37  /// This class implements a trivial graph adaptor i.e. it only wraps the
38  /// functions and types of the graph. The purpose of this class is to
39  /// make easier implementing graph adaptors. E.g. if an adaptor is
40  /// considered which differs from the wrapped graph only in some of its
41  /// functions or types, then it can be derived from GraphAdaptor, and only
42  /// the differences should be implemented.
43  template<typename _Graph>
44  class GraphAdaptorBase {
45  public:
46    typedef _Graph Graph;
47    typedef Graph ParentGraph;
48
49  protected:
50    Graph* _graph;
51
52    GraphAdaptorBase() : _graph(0) {}
53
54    void setGraph(Graph& graph) { _graph = &graph; }
55
56  public:
57    GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
58 
59    typedef typename Graph::Node Node;
60    typedef typename Graph::Arc Arc;
61    typedef typename Graph::Edge Edge;
62   
63    void first(Node& i) const { _graph->first(i); }
64    void first(Arc& i) const { _graph->first(i); }
65    void first(Edge& i) const { _graph->first(i); }
66    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
67    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
68    void firstInc(Edge &i, bool &d, const Node &n) const {
69      _graph->firstInc(i, d, n);
70    }
71
72    void next(Node& i) const { _graph->next(i); }
73    void next(Arc& i) const { _graph->next(i); }
74    void next(Edge& i) const { _graph->next(i); }
75    void nextIn(Arc& i) const { _graph->nextIn(i); }
76    void nextOut(Arc& i) const { _graph->nextOut(i); }
77    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
78
79    Node u(const Edge& e) const { return _graph->u(e); }
80    Node v(const Edge& e) const { return _graph->v(e); }
81
82    Node source(const Arc& a) const { return _graph->source(a); }
83    Node target(const Arc& a) const { return _graph->target(a); }
84
85    typedef NodeNumTagIndicator<Graph> NodeNumTag;
86    int nodeNum() const { return _graph->nodeNum(); }
87   
88    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
89    int arcNum() const { return _graph->arcNum(); }
90    int edgeNum() const { return _graph->edgeNum(); }
91
92    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
93    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
94      return _graph->findArc(u, v, prev);
95    }
96    Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
97      return _graph->findEdge(u, v, prev);
98    }
99 
100    Node addNode() { return _graph->addNode(); }
101    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
102
103    void erase(const Node& i) { _graph->erase(i); }
104    void erase(const Edge& i) { _graph->erase(i); }
105 
106    void clear() { _graph->clear(); }
107   
108    bool direction(const Arc& a) const { return _graph->direction(a); }
109    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
110
111    int id(const Node& v) const { return _graph->id(v); }
112    int id(const Arc& a) const { return _graph->id(a); }
113    int id(const Edge& e) const { return _graph->id(e); }
114
115    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
116    Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
117    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
118
119    int maxNodeId() const { return _graph->maxNodeId(); }
120    int maxArcId() const { return _graph->maxArcId(); }
121    int maxEdgeId() const { return _graph->maxEdgeId(); }
122
123    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
124    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
125
126    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
127    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
128
129    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
130    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
131
132    template <typename _Value>
133    class NodeMap : public Graph::template NodeMap<_Value> {
134    public:
135      typedef typename Graph::template NodeMap<_Value> Parent;
136      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
137        : Parent(*adapter._graph) {}
138      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
139        : Parent(*adapter._graph, value) {}
140
141    private:
142      NodeMap& operator=(const NodeMap& cmap) {
143        return operator=<NodeMap>(cmap);
144      }
145
146      template <typename CMap>
147      NodeMap& operator=(const CMap& cmap) {
148        Parent::operator=(cmap);
149        return *this;
150      }
151     
152    };
153
154    template <typename _Value>
155    class ArcMap : public Graph::template ArcMap<_Value> {
156    public:
157      typedef typename Graph::template ArcMap<_Value> Parent;
158      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
159        : Parent(*adapter._graph) {}
160      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
161        : Parent(*adapter._graph, value) {}
162
163    private:
164      ArcMap& operator=(const ArcMap& cmap) {
165        return operator=<ArcMap>(cmap);
166      }
167
168      template <typename CMap>
169      ArcMap& operator=(const CMap& cmap) {
170        Parent::operator=(cmap);
171        return *this;
172      }
173    };
174
175    template <typename _Value>
176    class EdgeMap : public Graph::template EdgeMap<_Value> {
177    public:
178      typedef typename Graph::template EdgeMap<_Value> Parent;
179      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
180        : Parent(*adapter._graph) {}
181      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
182        : Parent(*adapter._graph, value) {}
183
184    private:
185      EdgeMap& operator=(const EdgeMap& cmap) {
186        return operator=<EdgeMap>(cmap);
187      }
188
189      template <typename CMap>
190      EdgeMap& operator=(const CMap& cmap) {
191        Parent::operator=(cmap);
192        return *this;
193      }
194    };
195
196  };
197
198  /// \ingroup graph_adaptors
199  ///
200  /// \brief Trivial graph adaptor
201  ///
202  /// This class is an adaptor which does not change the adapted undirected
203  /// graph. It can be used only to test the graph adaptors.
204  template <typename _Graph>
205  class GraphAdaptor
206    : public GraphAdaptorExtender< GraphAdaptorBase<_Graph> > {
207  public:
208    typedef _Graph Graph;
209    typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
210  protected:
211    GraphAdaptor() : Parent() {}
212
213  public:
214    explicit GraphAdaptor(Graph& graph) { setGraph(graph); }
215  };
216
217  template <typename _Graph, typename NodeFilterMap,
218            typename EdgeFilterMap, bool checked = true>
219  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
220  public:
221    typedef _Graph Graph;
222    typedef SubGraphAdaptorBase Adaptor;
223    typedef GraphAdaptorBase<_Graph> Parent;
224  protected:
225
226    NodeFilterMap* _node_filter_map;
227    EdgeFilterMap* _edge_filter_map;
228
229    SubGraphAdaptorBase()
230      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
231
232    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
233      _node_filter_map=&node_filter_map;
234    }
235    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
236      _edge_filter_map=&edge_filter_map;
237    }
238
239  public:
240
241    typedef typename Parent::Node Node;
242    typedef typename Parent::Arc Arc;
243    typedef typename Parent::Edge Edge;
244
245    void first(Node& i) const {
246      Parent::first(i);
247      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
248    }
249
250    void first(Arc& i) const {
251      Parent::first(i);
252      while (i!=INVALID && (!(*_edge_filter_map)[i]
253             || !(*_node_filter_map)[Parent::source(i)]
254             || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
255    }
256
257    void first(Edge& i) const {
258      Parent::first(i);
259      while (i!=INVALID && (!(*_edge_filter_map)[i]
260             || !(*_node_filter_map)[Parent::u(i)]
261             || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
262    }
263
264    void firstIn(Arc& i, const Node& n) const {
265      Parent::firstIn(i, n);
266      while (i!=INVALID && (!(*_edge_filter_map)[i]
267             || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
268    }
269
270    void firstOut(Arc& i, const Node& n) const {
271      Parent::firstOut(i, n);
272      while (i!=INVALID && (!(*_edge_filter_map)[i]
273             || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
274    }
275
276    void firstInc(Edge& i, bool& d, const Node& n) const {
277      Parent::firstInc(i, d, n);
278      while (i!=INVALID && (!(*_edge_filter_map)[i]
279            || !(*_node_filter_map)[Parent::u(i)]
280            || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
281    }
282
283    void next(Node& i) const {
284      Parent::next(i);
285      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
286    }
287
288    void next(Arc& i) const {
289      Parent::next(i);
290      while (i!=INVALID && (!(*_edge_filter_map)[i]
291             || !(*_node_filter_map)[Parent::source(i)]
292             || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
293    }
294
295    void next(Edge& i) const {
296      Parent::next(i);
297      while (i!=INVALID && (!(*_edge_filter_map)[i]
298             || !(*_node_filter_map)[Parent::u(i)]
299             || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
300    }
301
302    void nextIn(Arc& i) const {
303      Parent::nextIn(i);
304      while (i!=INVALID && (!(*_edge_filter_map)[i]
305             || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
306    }
307
308    void nextOut(Arc& i) const {
309      Parent::nextOut(i);
310      while (i!=INVALID && (!(*_edge_filter_map)[i]
311             || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
312    }
313
314    void nextInc(Edge& i, bool& d) const {
315      Parent::nextInc(i, d);
316      while (i!=INVALID && (!(*_edge_filter_map)[i]
317            || !(*_node_filter_map)[Parent::u(i)]
318            || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
319    }
320
321    /// \brief Hide the given node in the graph.
322    ///
323    /// This function hides \c n in the graph, i.e. the iteration
324    /// jumps over it. This is done by simply setting the value of \c n 
325    /// to be false in the corresponding node-map.
326    void hide(const Node& n) const { _node_filter_map->set(n, false); }
327
328    /// \brief Hide the given edge in the graph.
329    ///
330    /// This function hides \c e in the graph, i.e. the iteration
331    /// jumps over it. This is done by simply setting the value of \c e 
332    /// to be false in the corresponding edge-map.
333    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
334
335    /// \brief Unhide the given node in the graph.
336    ///
337    /// The value of \c n is set to be true in the node-map which stores
338    /// hide information. If \c n was hidden previuosly, then it is shown
339    /// again
340     void unHide(const Node& n) const { _node_filter_map->set(n, true); }
341
342    /// \brief Hide the given edge in the graph.
343    ///
344    /// The value of \c e is set to be true in the edge-map which stores
345    /// hide information. If \c e was hidden previuosly, then it is shown
346    /// again
347    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
348
349    /// \brief Returns true if \c n is hidden.
350    ///
351    /// Returns true if \c n is hidden.
352    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
353
354    /// \brief Returns true if \c e is hidden.
355    ///
356    /// Returns true if \c e is hidden.
357    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
358
359    typedef False NodeNumTag;
360    typedef False EdgeNumTag;
361
362    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
363    Arc findArc(const Node& u, const Node& v,
364                  const Arc& prev = INVALID) {
365      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
366        return INVALID;
367      }
368      Arc arc = Parent::findArc(u, v, prev);
369      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
370        arc = Parent::findArc(u, v, arc);
371      }
372      return arc;
373    }
374    Edge findEdge(const Node& u, const Node& v,
375                  const Edge& prev = INVALID) {
376      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
377        return INVALID;
378      }
379      Edge edge = Parent::findEdge(u, v, prev);
380      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
381        edge = Parent::findEdge(u, v, edge);
382      }
383      return edge;
384    }
385
386    template <typename _Value>
387    class NodeMap : public SubMapExtender<Adaptor,
388        typename Parent::template NodeMap<_Value> > {
389    public:
390      typedef _Value Value;
391      typedef SubMapExtender<Adaptor, typename Parent::
392                             template NodeMap<Value> > MapParent;
393   
394      NodeMap(const Adaptor& adaptor)
395        : MapParent(adaptor) {}
396      NodeMap(const Adaptor& adaptor, const Value& value)
397        : MapParent(adaptor, value) {}
398
399    private:
400      NodeMap& operator=(const NodeMap& cmap) {
401        return operator=<NodeMap>(cmap);
402      }
403   
404      template <typename CMap>
405      NodeMap& operator=(const CMap& cmap) {
406        MapParent::operator=(cmap);
407        return *this;
408      }
409    };
410
411    template <typename _Value>
412    class ArcMap : public SubMapExtender<Adaptor,
413        typename Parent::template ArcMap<_Value> > {
414    public:
415      typedef _Value Value;
416      typedef SubMapExtender<Adaptor, typename Parent::
417                             template ArcMap<Value> > MapParent;
418   
419      ArcMap(const Adaptor& adaptor)
420        : MapParent(adaptor) {}
421      ArcMap(const Adaptor& adaptor, const Value& value)
422        : MapParent(adaptor, value) {}
423
424    private:
425      ArcMap& operator=(const ArcMap& cmap) {
426        return operator=<ArcMap>(cmap);
427      }
428   
429      template <typename CMap>
430      ArcMap& operator=(const CMap& cmap) {
431        MapParent::operator=(cmap);
432        return *this;
433      }
434    };
435
436    template <typename _Value>
437    class EdgeMap : public SubMapExtender<Adaptor,
438        typename Parent::template EdgeMap<_Value> > {
439    public:
440      typedef _Value Value;
441      typedef SubMapExtender<Adaptor, typename Parent::
442                             template EdgeMap<Value> > MapParent;
443   
444      EdgeMap(const Adaptor& adaptor)
445        : MapParent(adaptor) {}
446
447      EdgeMap(const Adaptor& adaptor, const Value& value)
448        : MapParent(adaptor, value) {}
449
450    private:
451      EdgeMap& operator=(const EdgeMap& cmap) {
452        return operator=<EdgeMap>(cmap);
453      }
454   
455      template <typename CMap>
456      EdgeMap& operator=(const CMap& cmap) {
457        MapParent::operator=(cmap);
458        return *this;
459      }
460    };
461
462  };
463
464  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
465  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
466    : public GraphAdaptorBase<_Graph> {
467  public:
468    typedef _Graph Graph;
469    typedef SubGraphAdaptorBase Adaptor;
470    typedef GraphAdaptorBase<_Graph> Parent;
471  protected:
472    NodeFilterMap* _node_filter_map;
473    EdgeFilterMap* _edge_filter_map;
474    SubGraphAdaptorBase() : Parent(),
475                            _node_filter_map(0), _edge_filter_map(0) { }
476
477    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
478      _node_filter_map=&node_filter_map;
479    }
480    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
481      _edge_filter_map=&edge_filter_map;
482    }
483
484  public:
485
486    typedef typename Parent::Node Node;
487    typedef typename Parent::Arc Arc;
488    typedef typename Parent::Edge Edge;
489
490    void first(Node& i) const {
491      Parent::first(i);
492      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
493    }
494
495    void first(Arc& i) const {
496      Parent::first(i);
497      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
498    }
499
500    void first(Edge& i) const {
501      Parent::first(i);
502      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
503    }
504
505    void firstIn(Arc& i, const Node& n) const {
506      Parent::firstIn(i, n);
507      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
508    }
509
510    void firstOut(Arc& i, const Node& n) const {
511      Parent::firstOut(i, n);
512      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
513    }
514
515    void firstInc(Edge& i, bool& d, const Node& n) const {
516      Parent::firstInc(i, d, n);
517      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
518    }
519
520    void next(Node& i) const {
521      Parent::next(i);
522      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
523    }
524    void next(Arc& i) const {
525      Parent::next(i);
526      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
527    }
528    void next(Edge& i) const {
529      Parent::next(i);
530      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
531    }
532    void nextIn(Arc& i) const {
533      Parent::nextIn(i);
534      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
535    }
536
537    void nextOut(Arc& i) const {
538      Parent::nextOut(i);
539      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
540    }
541    void nextInc(Edge& i, bool& d) const {
542      Parent::nextInc(i, d);
543      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
544    }
545
546    /// \brief Hide the given node in the graph.
547    ///
548    /// This function hides \c n in the graph, i.e. the iteration
549    /// jumps over it. This is done by simply setting the value of \c n 
550    /// to be false in the corresponding node-map.
551    void hide(const Node& n) const { _node_filter_map->set(n, false); }
552
553    /// \brief Hide the given edge in the graph.
554    ///
555    /// This function hides \c e in the graph, i.e. the iteration
556    /// jumps over it. This is done by simply setting the value of \c e 
557    /// to be false in the corresponding edge-map.
558    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
559
560    /// \brief Unhide the given node in the graph.
561    ///
562    /// The value of \c n is set to be true in the node-map which stores
563    /// hide information. If \c n was hidden previuosly, then it is shown
564    /// again
565     void unHide(const Node& n) const { _node_filter_map->set(n, true); }
566
567    /// \brief Hide the given edge in the graph.
568    ///
569    /// The value of \c e is set to be true in the edge-map which stores
570    /// hide information. If \c e was hidden previuosly, then it is shown
571    /// again
572    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
573
574    /// \brief Returns true if \c n is hidden.
575    ///
576    /// Returns true if \c n is hidden.
577    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
578
579    /// \brief Returns true if \c e is hidden.
580    ///
581    /// Returns true if \c e is hidden.
582    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
583
584    typedef False NodeNumTag;
585    typedef False EdgeNumTag;
586
587    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
588    Arc findArc(const Node& u, const Node& v,
589                  const Arc& prev = INVALID) {
590      Arc arc = Parent::findArc(u, v, prev);
591      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
592        arc = Parent::findArc(u, v, arc);
593      }
594      return arc;
595    }
596    Edge findEdge(const Node& u, const Node& v,
597                  const Edge& prev = INVALID) {
598      Edge edge = Parent::findEdge(u, v, prev);
599      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
600        edge = Parent::findEdge(u, v, edge);
601      }
602      return edge;
603    }
604
605    template <typename _Value>
606    class NodeMap : public SubMapExtender<Adaptor,
607        typename Parent::template NodeMap<_Value> > {
608    public:
609      typedef _Value Value;
610      typedef SubMapExtender<Adaptor, typename Parent::
611                             template NodeMap<Value> > MapParent;
612   
613      NodeMap(const Adaptor& adaptor)
614        : MapParent(adaptor) {}
615      NodeMap(const Adaptor& adaptor, const Value& value)
616        : MapParent(adaptor, value) {}
617   
618    private:
619      NodeMap& operator=(const NodeMap& cmap) {
620        return operator=<NodeMap>(cmap);
621      }
622   
623      template <typename CMap>
624      NodeMap& operator=(const CMap& cmap) {
625        MapParent::operator=(cmap);
626        return *this;
627      }
628    };
629
630    template <typename _Value>
631    class ArcMap : public SubMapExtender<Adaptor,
632        typename Parent::template ArcMap<_Value> > {
633    public:
634      typedef _Value Value;
635      typedef SubMapExtender<Adaptor, typename Parent::
636                             template ArcMap<Value> > MapParent;
637   
638      ArcMap(const Adaptor& adaptor)
639        : MapParent(adaptor) {}
640      ArcMap(const Adaptor& adaptor, const Value& value)
641        : MapParent(adaptor, value) {}
642
643    private:
644      ArcMap& operator=(const ArcMap& cmap) {
645        return operator=<ArcMap>(cmap);
646      }
647   
648      template <typename CMap>
649      ArcMap& operator=(const CMap& cmap) {
650        MapParent::operator=(cmap);
651        return *this;
652      }
653    };
654
655    template <typename _Value>
656    class EdgeMap : public SubMapExtender<Adaptor,
657        typename Parent::template EdgeMap<_Value> > {
658    public:
659      typedef _Value Value;
660      typedef SubMapExtender<Adaptor, typename Parent::
661                             template EdgeMap<Value> > MapParent;
662   
663      EdgeMap(const Adaptor& adaptor)
664        : MapParent(adaptor) {}
665
666      EdgeMap(const Adaptor& adaptor, const _Value& value)
667        : MapParent(adaptor, value) {}
668
669    private:
670      EdgeMap& operator=(const EdgeMap& cmap) {
671        return operator=<EdgeMap>(cmap);
672      }
673   
674      template <typename CMap>
675      EdgeMap& operator=(const CMap& cmap) {
676        MapParent::operator=(cmap);
677        return *this;
678      }
679    };
680
681  };
682
683  /// \ingroup graph_adaptors
684  ///
685  /// \brief A graph adaptor for hiding nodes and arcs from an
686  /// undirected graph.
687  ///
688  /// SubGraphAdaptor shows the graph with filtered node-set and
689  /// edge-set. If the \c checked parameter is true then it filters
690  /// the edge-set to do not get invalid edges which incident node is
691  /// filtered.
692  ///
693  /// If the \c checked template parameter is false then we have to
694  /// note that the node-iterator cares only the filter on the
695  /// node-set, and the edge-iterator cares only the filter on the
696  /// edge-set.  This way the edge-map should filter all arcs which
697  /// has filtered end node.
698  template<typename _Graph, typename NodeFilterMap,
699           typename EdgeFilterMap, bool checked = true>
700  class SubGraphAdaptor :
701    public GraphAdaptorExtender<
702    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
703  public:
704    typedef _Graph Graph;
705    typedef GraphAdaptorExtender<
706      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
707  protected:
708    SubGraphAdaptor() { }
709  public:
710    SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map,
711                    EdgeFilterMap& edge_filter_map) {
712      setGraph(_graph);
713      setNodeFilterMap(node_filter_map);
714      setEdgeFilterMap(edge_filter_map);
715    }
716  };
717
718  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
719  SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
720  subGraphAdaptor(const Graph& graph,
721                   NodeFilterMap& nfm, ArcFilterMap& efm) {
722    return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
723      (graph, nfm, efm);
724  }
725
726  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
727  SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
728  subGraphAdaptor(const Graph& graph,
729                   NodeFilterMap& nfm, ArcFilterMap& efm) {
730    return SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
731      (graph, nfm, efm);
732  }
733
734  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
735  SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
736  subGraphAdaptor(const Graph& graph,
737                   NodeFilterMap& nfm, ArcFilterMap& efm) {
738    return SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
739      (graph, nfm, efm);
740  }
741
742  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
743  SubGraphAdaptor<const Graph, const NodeFilterMap, const ArcFilterMap>
744  subGraphAdaptor(const Graph& graph,
745                   NodeFilterMap& nfm, ArcFilterMap& efm) {
746    return SubGraphAdaptor<const Graph, const NodeFilterMap,
747      const ArcFilterMap>(graph, nfm, efm);
748  }
749
750  /// \ingroup graph_adaptors
751  ///
752  /// \brief An adaptor for hiding nodes from an graph.
753  ///
754  /// An adaptor for hiding nodes from an graph.  This
755  /// adaptor specializes SubGraphAdaptor in the way that only the
756  /// node-set can be filtered. In usual case the checked parameter is
757  /// true, we get the induced subgraph. But if the checked parameter
758  /// is false then we can filter only isolated nodes.
759  template<typename _Graph, typename _NodeFilterMap, bool checked = true>
760  class NodeSubGraphAdaptor :
761    public SubGraphAdaptor<_Graph, _NodeFilterMap,
762                           ConstMap<typename _Graph::Edge, bool>, checked> {
763  public:
764    typedef _Graph Graph;
765    typedef _NodeFilterMap NodeFilterMap;
766    typedef SubGraphAdaptor<Graph, NodeFilterMap,
767                            ConstMap<typename Graph::Edge, bool> > Parent;
768  protected:
769    ConstMap<typename Graph::Edge, bool> const_true_map;
770
771    NodeSubGraphAdaptor() : const_true_map(true) {
772      Parent::setEdgeFilterMap(const_true_map);
773    }
774
775  public:
776    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) :
777      Parent(), const_true_map(true) {
778      Parent::setGraph(_graph);
779      Parent::setNodeFilterMap(node_filter_map);
780      Parent::setEdgeFilterMap(const_true_map);
781    }
782  };
783
784  template<typename Graph, typename NodeFilterMap>
785  NodeSubGraphAdaptor<const Graph, NodeFilterMap>
786  nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
787    return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
788  }
789
790  template<typename Graph, typename NodeFilterMap>
791  NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
792  nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
793    return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
794  }
795
796  /// \ingroup graph_adaptors
797  ///
798  /// \brief An adaptor for hiding edges from an graph.
799  ///
800  /// \warning Graph adaptors are in even more experimental state
801  /// than the other parts of the lib. Use them at you own risk.
802  ///
803  /// An adaptor for hiding edges from an graph.
804  /// This adaptor specializes SubGraphAdaptor in the way that
805  /// only the arc-set
806  /// can be filtered.
807  template<typename _Graph, typename _EdgeFilterMap>
808  class EdgeSubGraphAdaptor :
809    public SubGraphAdaptor<_Graph, ConstMap<typename _Graph::Node,bool>,
810                           _EdgeFilterMap, false> {
811  public:
812    typedef _Graph Graph;
813    typedef _EdgeFilterMap EdgeFilterMap;
814    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
815                            EdgeFilterMap, false> Parent;
816  protected:
817    ConstMap<typename Graph::Node, bool> const_true_map;
818
819    EdgeSubGraphAdaptor() : const_true_map(true) {
820      Parent::setNodeFilterMap(const_true_map);
821    }
822
823  public:
824
825    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) :
826      Parent(), const_true_map(true) {
827      Parent::setGraph(_graph);
828      Parent::setNodeFilterMap(const_true_map);
829      Parent::setEdgeFilterMap(edge_filter_map);
830    }
831
832  };
833
834  template<typename Graph, typename EdgeFilterMap>
835  EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
836  edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
837    return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
838  }
839
840  template<typename Graph, typename EdgeFilterMap>
841  EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
842  edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
843    return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
844  }
845
846  /// \brief Base of direct graph adaptor
847  ///
848  /// Base class of the direct graph adaptor. All public member
849  /// of this class can be used with the DirGraphAdaptor too.
850  /// \sa DirGraphAdaptor
851  template <typename _Graph, typename _DirectionMap>
852  class DirGraphAdaptorBase {
853  public:
854   
855    typedef _Graph Graph;
856    typedef _DirectionMap DirectionMap;
857
858    typedef typename Graph::Node Node;
859    typedef typename Graph::Edge Arc;
860   
861    /// \brief Reverse arc
862    ///
863    /// It reverse the given arc. It simply negate the direction in the map.
864    void reverseArc(const Arc& arc) {
865      _direction->set(arc, !(*_direction)[arc]);
866    }
867
868    void first(Node& i) const { _graph->first(i); }
869    void first(Arc& i) const { _graph->first(i); }
870    void firstIn(Arc& i, const Node& n) const {
871      bool d;
872      _graph->firstInc(i, d, n);
873      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
874    }
875    void firstOut(Arc& i, const Node& n ) const {
876      bool d;
877      _graph->firstInc(i, d, n);
878      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
879    }
880
881    void next(Node& i) const { _graph->next(i); }
882    void next(Arc& i) const { _graph->next(i); }
883    void nextIn(Arc& i) const {
884      bool d = !(*_direction)[i];
885      _graph->nextInc(i, d);
886      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
887    }
888    void nextOut(Arc& i) const {
889      bool d = (*_direction)[i];
890      _graph->nextInc(i, d);
891      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
892    }
893
894    Node source(const Arc& e) const {
895      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
896    }
897    Node target(const Arc& e) const {
898      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
899    }
900
901    typedef NodeNumTagIndicator<Graph> NodeNumTag;
902    int nodeNum() const { return _graph->nodeNum(); }
903   
904    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
905    int arcNum() const { return _graph->edgeNum(); }
906
907    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
908    Arc findArc(const Node& u, const Node& v,
909                  const Arc& prev = INVALID) {
910      Arc arc = prev;
911      bool d = arc == INVALID ? true : (*_direction)[arc];
912      if (d) {
913        arc = _graph->findEdge(u, v, arc);
914        while (arc != INVALID && !(*_direction)[arc]) {
915          _graph->findEdge(u, v, arc);
916        }
917        if (arc != INVALID) return arc;
918      }
919      _graph->findEdge(v, u, arc);
920      while (arc != INVALID && (*_direction)[arc]) {
921        _graph->findEdge(u, v, arc);
922      }
923      return arc;
924    }
925 
926    Node addNode() {
927      return Node(_graph->addNode());
928    }
929
930    Arc addArc(const Node& u, const Node& v) {
931      Arc arc = _graph->addArc(u, v);
932      _direction->set(arc, _graph->source(arc) == u);
933      return arc;
934    }
935
936    void erase(const Node& i) { _graph->erase(i); }
937    void erase(const Arc& i) { _graph->erase(i); }
938 
939    void clear() { _graph->clear(); }
940   
941    int id(const Node& v) const { return _graph->id(v); }
942    int id(const Arc& e) const { return _graph->id(e); }
943
944    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
945    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
946
947    int maxNodeId() const { return _graph->maxNodeId(); }
948    int maxArcId() const { return _graph->maxEdgeId(); }
949
950    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
951    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
952
953    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
954    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
955
956    template <typename _Value>
957    class NodeMap : public _Graph::template NodeMap<_Value> {
958    public:
959
960      typedef typename _Graph::template NodeMap<_Value> Parent;
961
962      explicit NodeMap(const DirGraphAdaptorBase& adapter)
963        : Parent(*adapter._graph) {}
964
965      NodeMap(const DirGraphAdaptorBase& adapter, const _Value& value)
966        : Parent(*adapter._graph, value) {}
967
968    private:
969      NodeMap& operator=(const NodeMap& cmap) {
970        return operator=<NodeMap>(cmap);
971      }
972
973      template <typename CMap>
974      NodeMap& operator=(const CMap& cmap) {
975        Parent::operator=(cmap);
976        return *this;
977      }
978
979    };
980
981    template <typename _Value>
982    class ArcMap : public _Graph::template EdgeMap<_Value> {
983    public:
984
985      typedef typename Graph::template EdgeMap<_Value> Parent;
986
987      explicit ArcMap(const DirGraphAdaptorBase& adapter)
988        : Parent(*adapter._graph) { }
989
990      ArcMap(const DirGraphAdaptorBase& adapter, const _Value& value)
991        : Parent(*adapter._graph, value) { }
992
993    private:
994      ArcMap& operator=(const ArcMap& cmap) {
995        return operator=<ArcMap>(cmap);
996      }
997
998      template <typename CMap>
999      ArcMap& operator=(const CMap& cmap) {
1000        Parent::operator=(cmap);
1001        return *this;
1002      }
1003    };
1004
1005   
1006
1007  protected:
1008    Graph* _graph;
1009    DirectionMap* _direction;
1010
1011    void setDirectionMap(DirectionMap& direction) {
1012      _direction = &direction;
1013    }
1014
1015    void setGraph(Graph& graph) {
1016      _graph = &graph;
1017    }
1018
1019  };
1020
1021
1022  /// \ingroup graph_adaptors
1023  ///
1024  /// \brief A directed graph is made from an graph by an adaptor
1025  ///
1026  /// This adaptor gives a direction for each edge in the undirected
1027  /// graph. The direction of the arcs stored in the
1028  /// DirectionMap. This map is a bool map on the edges. If
1029  /// the edge is mapped to true then the direction of the directed
1030  /// arc will be the same as the default direction of the edge. The
1031  /// arcs can be easily reverted by the \ref
1032  /// DirGraphAdaptorBase::reverseArc "reverseArc()" member in the
1033  /// adaptor.
1034  ///
1035  /// It can be used to solve orientation problems on directed graphs.
1036  /// For example how can we orient an graph to get the minimum
1037  /// number of strongly connected components. If we orient the arcs with
1038  /// the dfs algorithm out from the source then we will get such an
1039  /// orientation.
1040  ///
1041  /// We use the \ref DfsVisitor "visitor" interface of the
1042  /// \ref DfsVisit "dfs" algorithm:
1043  ///\code
1044  /// template <typename DirMap>
1045  /// class OrientVisitor : public DfsVisitor<Graph> {
1046  /// public:
1047  ///
1048  ///   OrientVisitor(const Graph& graph, DirMap& dirMap)
1049  ///     : _graph(graph), _dirMap(dirMap), _processed(graph, false) {}
1050  ///
1051  ///   void discover(const Arc& arc) {
1052  ///     _processed.set(arc, true);
1053  ///     _dirMap.set(arc, _graph.direction(arc));
1054  ///   }
1055  ///
1056  ///   void examine(const Arc& arc) {
1057  ///     if (_processed[arc]) return;
1058  ///     _processed.set(arc, true);
1059  ///     _dirMap.set(arc, _graph.direction(arc));
1060  ///   } 
1061  ///
1062  /// private:
1063  ///   const Graph& _graph; 
1064  ///   DirMap& _dirMap;
1065  ///   Graph::EdgeMap<bool> _processed;
1066  /// };
1067  ///\endcode
1068  ///
1069  /// And now we can use the orientation:
1070  ///\code
1071  /// Graph::EdgeMap<bool> dmap(graph);
1072  ///
1073  /// typedef OrientVisitor<Graph::EdgeMap<bool> > Visitor;
1074  /// Visitor visitor(graph, dmap);
1075  ///
1076  /// DfsVisit<Graph, Visitor> dfs(graph, visitor);
1077  ///
1078  /// dfs.run();
1079  ///
1080  /// typedef DirGraphAdaptor<Graph> DGraph;
1081  /// DGraph dgraph(graph, dmap);
1082  ///
1083  /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
1084  ///              countBiArcConnectedComponents(graph), "Wrong Orientation");
1085  ///\endcode
1086  ///
1087  /// The number of the bi-connected components is a lower bound for
1088  /// the number of the strongly connected components in the directed
1089  /// graph because if we contract the bi-connected components to
1090  /// nodes we will get a tree therefore we cannot orient arcs in
1091  /// both direction between bi-connected components. In the other way
1092  /// the algorithm will orient one component to be strongly
1093  /// connected. The two relations proof that the assertion will
1094  /// be always true and the found solution is optimal.
1095  ///
1096  /// \sa DirGraphAdaptorBase
1097  /// \sa dirGraphAdaptor
1098  template<typename _Graph,
1099           typename DirectionMap = typename _Graph::template EdgeMap<bool> >
1100  class DirGraphAdaptor :
1101    public DigraphAdaptorExtender<DirGraphAdaptorBase<_Graph, DirectionMap> > {
1102  public:
1103    typedef _Graph Graph;
1104    typedef DigraphAdaptorExtender<
1105      DirGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1106  protected:
1107    DirGraphAdaptor() { }
1108  public:
1109   
1110    /// \brief Constructor of the adaptor
1111    ///
1112    /// Constructor of the adaptor
1113    DirGraphAdaptor(Graph& graph, DirectionMap& direction) {
1114      setGraph(graph);
1115      setDirectionMap(direction);
1116    }
1117  };
1118
1119  /// \brief Just gives back a DirGraphAdaptor
1120  ///
1121  /// Just gives back a DirGraphAdaptor
1122  template<typename Graph, typename DirectionMap>
1123  DirGraphAdaptor<const Graph, DirectionMap>
1124  dirGraphAdaptor(const Graph& graph, DirectionMap& dm) {
1125    return DirGraphAdaptor<const Graph, DirectionMap>(graph, dm);
1126  }
1127
1128  template<typename Graph, typename DirectionMap>
1129  DirGraphAdaptor<const Graph, const DirectionMap>
1130  dirGraphAdaptor(const Graph& graph, const DirectionMap& dm) {
1131    return DirGraphAdaptor<const Graph, const DirectionMap>(graph, dm);
1132  }
1133
1134}
1135
1136#endif
Note: See TracBrowser for help on using the repository browser.