COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/ugraph_adaptor.h @ 2229:4dbb6dd2dd4b

Last change on this file since 2229:4dbb6dd2dd4b was 2096:dbe860a83dc9, checked in by Balazs Dezso, 13 years ago

Bug fix

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