COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/ugraph_adaptor.h @ 2090:923f69c38d55

Last change on this file since 2090:923f69c38d55 was 2087:67258b5a057b, checked in by Balazs Dezso, 18 years ago

DirUGraphAdaptor documentation

File size: 37.7 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    /// \brief Returns the original direction in the undirected graph.
905    ///
906    /// Returns the original direction in the undirected graph.
907    bool direction(const Edge& edge) const {
908      return (*direction)[edge];
909    }
910
911    void first(Node& i) const { graph->first(i); }
912    void first(Edge& i) const { graph->first(i); }
913    void firstIn(Edge& i, const Node& n) const {
914      bool d;
915      graph->firstInc(i, d, n);
916      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
917    }
918    void firstOut(Edge& i, const Node& n ) const {
919      bool d;
920      graph->firstInc(i, d, n);
921      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
922    }
923
924    void next(Node& i) const { graph->next(i); }
925    void next(Edge& i) const { graph->next(i); }
926    void nextIn(Edge& i) const {
927      bool d = !(*direction)[i];
928      graph->nextInc(i, d);
929      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
930    }
931    void nextOut(Edge& i) const {
932      bool d = (*direction)[i];
933      graph->nextInc(i, d);
934      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
935    }
936
937    Node source(const Edge& e) const {
938      return (*direction)[e] ? graph->source(e) : graph->target(e);
939    }
940    Node target(const Edge& e) const {
941      return (*direction)[e] ? graph->target(e) : graph->source(e);
942    }
943
944    typedef NodeNumTagIndicator<Graph> NodeNumTag;
945    int nodeNum() const { return graph->nodeNum(); }
946   
947    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
948    int edgeNum() const { return graph->uEdgeNum(); }
949
950    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
951    Edge findEdge(const Node& source, const Node& target,
952                  const Edge& prev = INVALID) {
953      Edge edge = prev;
954      bool d = edge == INVALID ? true : (*direction)[edge];
955      if (d) {
956        edge = graph->findUEdge(source, target, edge);
957        while (edge != INVALID && !(*direction)[edge]) {
958          graph->findUEdge(source, target, edge);
959        }
960        if (edge != INVALID) return edge;
961      }
962      graph->findUEdge(target, source, edge);
963      while (edge != INVALID && (*direction)[edge]) {
964        graph->findUEdge(source, target, edge);
965      }
966      return edge;
967    }
968 
969    Node addNode() const {
970      return Node(graph->addNode());
971    }
972
973    Edge addEdge(const Node& source, const Node& target) const {
974      Edge edge = graph->addEdge(source, target);
975      direction->set(edge, graph->source(edge) == source);
976      return edge;
977    }
978
979    void erase(const Node& i) const { graph->erase(i); }
980    void erase(const Edge& i) const { graph->erase(i); }
981 
982    void clear() const { graph->clear(); }
983   
984    int id(const Node& v) const { return graph->id(v); }
985    int id(const Edge& e) const { return graph->id(e); }
986
987    int maxNodeId() const {
988      return graph->maxNodeId();
989    }
990
991    int maxEdgeId() const {
992      return graph->maxEdgeId();
993    }
994
995    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
996
997    NodeNotifier& getNotifier(Node) const {
998      return graph->getNotifier(Node());
999    }
1000
1001    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
1002
1003    EdgeNotifier& getNotifier(Edge) const {
1004      return graph->getNotifier(Edge());
1005    }
1006
1007    template <typename _Value>
1008    class NodeMap : public _UGraph::template NodeMap<_Value> {
1009    public:
1010
1011      typedef typename _UGraph::template NodeMap<_Value> Parent;
1012
1013      explicit NodeMap(const DirUGraphAdaptorBase& ga)
1014        : Parent(*ga.graph) {}
1015
1016      NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
1017        : Parent(*ga.graph, value) {}
1018
1019      NodeMap& operator=(const NodeMap& cmap) {
1020        return operator=<NodeMap>(cmap);
1021      }
1022
1023      template <typename CMap>
1024      NodeMap& operator=(const CMap& cmap) {
1025        Parent::operator=(cmap);
1026        return *this;
1027      }
1028
1029    };
1030
1031    template <typename _Value>
1032    class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
1033    public:
1034
1035      typedef typename _UGraph::template UEdgeMap<_Value> Parent;
1036
1037      explicit EdgeMap(const DirUGraphAdaptorBase& ga)
1038        : Parent(*ga.graph) { }
1039
1040      EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
1041        : Parent(*ga.graph, value) { }
1042
1043      EdgeMap& operator=(const EdgeMap& cmap) {
1044        return operator=<EdgeMap>(cmap);
1045      }
1046
1047      template <typename CMap>
1048      EdgeMap& operator=(const CMap& cmap) {
1049        Parent::operator=(cmap);
1050        return *this;
1051      }
1052    };
1053
1054   
1055
1056  protected:
1057    Graph* graph;
1058    DirectionMap* direction;
1059
1060    void setDirectionMap(DirectionMap& _direction) {
1061      direction = &_direction;
1062    }
1063
1064    void setGraph(Graph& _graph) {
1065      graph = &_graph;
1066    }
1067
1068  };
1069
1070
1071  /// \ingroup graph_adaptors
1072  ///
1073  /// \brief A directed graph is made from an undirected graph by an adaptor
1074  ///
1075  /// This adaptor gives a direction for each uedge in the undirected
1076  /// graph. The direction of the edges stored in the
1077  /// DirectionMap. This map is a bool map on the undirected edges. If
1078  /// the uedge is mapped to true then the direction of the directed
1079  /// edge will be the same as the default direction of the uedge. The
1080  /// edges can be easily reverted by the \ref
1081  /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the
1082  /// adaptor.
1083  ///
1084  /// It can be used to solve orientation problems on directed graphs.
1085  /// By example how can we orient an undirected graph to get the minimum
1086  /// number of strongly connected components. If we orient the edges with
1087  /// the dfs algorithm out from the source then we will get such an
1088  /// orientation.
1089  ///
1090  /// We use the \ref DfsVisitor "visitor" interface of the
1091  /// \ref DfsVisit "dfs" algorithm:
1092  ///\code
1093  /// template <typename DirMap>
1094  /// class OrientVisitor : public DfsVisitor<UGraph> {
1095  /// public:
1096  ///
1097  ///   OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
1098  ///     : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
1099  ///
1100  ///   void discover(const Edge& edge) {
1101  ///     _processed.set(edge, true);
1102  ///     _dirMap.set(edge, _ugraph.direction(edge));
1103  ///   }
1104  ///
1105  ///   void examine(const Edge& edge) {
1106  ///     if (_processed[edge]) return;
1107  ///     _processed.set(edge, true);
1108  ///     _dirMap.set(edge, _ugraph.direction(edge));
1109  ///   } 
1110  ///
1111  /// private:
1112  ///   const UGraph& _ugraph; 
1113  ///   DirMap& _dirMap;
1114  ///   UGraph::UEdgeMap<bool> _processed;
1115  /// };
1116  ///\endcode
1117  ///
1118  /// And now we can use the orientation:
1119  ///\code
1120  /// UGraph::UEdgeMap<bool> dmap(ugraph);
1121  ///
1122  /// typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
1123  /// Visitor visitor(ugraph, dmap);
1124  ///
1125  /// DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
1126  ///
1127  /// dfs.run();
1128  ///
1129  /// typedef DirUGraphAdaptor<UGraph> DGraph;
1130  /// DGraph dgraph(ugraph, dmap);
1131  ///
1132  /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
1133  ///              countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");
1134  ///\endcode
1135  ///
1136  /// The number of the bi-connected components is a lower bound for
1137  /// the number of the strongly connected components in the directed
1138  /// graph because if we contract the bi-connected components to
1139  /// nodes we will get a tree therefore we cannot orient edges in
1140  /// both direction between bi-connected components. In the other way
1141  /// the algorithm will orient one component to be strongly
1142  /// connected. The two relations proof that the assertion will
1143  /// be always true and the found solution is optimal.
1144  ///
1145  /// \sa DirUGraphAdaptorBase
1146  /// \sa dirUGraphAdaptor
1147  template<typename _Graph,
1148           typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
1149  class DirUGraphAdaptor :
1150    public GraphAdaptorExtender<
1151    DirUGraphAdaptorBase<_Graph, DirectionMap> > {
1152  public:
1153    typedef _Graph Graph;
1154    typedef GraphAdaptorExtender<
1155      DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1156  protected:
1157    DirUGraphAdaptor() { }
1158  public:
1159   
1160    /// \brief Constructor of the adaptor
1161    ///
1162    /// Constructor of the adaptor
1163    DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
1164      setGraph(_graph);
1165      setDirectionMap(_direction_map);
1166    }
1167  };
1168
1169  /// \brief Just gives back a DirUGraphAdaptor
1170  ///
1171  /// Just gives back a DirUGraphAdaptor
1172  template<typename UGraph, typename DirectionMap>
1173  DirUGraphAdaptor<const UGraph, DirectionMap>
1174  dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
1175    return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
1176  }
1177
1178  template<typename UGraph, typename DirectionMap>
1179  DirUGraphAdaptor<const UGraph, const DirectionMap>
1180  dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
1181    return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
1182  }
1183
1184}
1185
1186#endif
Note: See TracBrowser for help on using the repository browser.