COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/ugraph_adaptor.h @ 2390:8450951a8e2d

Last change on this file since 2390:8450951a8e2d was 2386:81b47fc5c444, checked in by Balazs Dezso, 13 years ago

Hard Warning checking

  • based on the remark of the ZIB user
  • we do not use -Winline
File size: 37.2 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& u, const Node& v,
103                  const Edge& prev = INVALID) {
104      return graph->findEdge(u, v, prev);
105    }
106    UEdge findUEdge(const Node& u, const Node& v,
107                    const UEdge& prev = INVALID) {
108      return graph->findUEdge(u, v, prev);
109    }
110 
111    Node addNode() const { return graph->addNode(); }
112    UEdge addEdge(const Node& u, const Node& v) const {
113      return graph->addEdge(u, v);
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 ix) const {
129      return graph->fromNodeId(ix);
130    }
131
132    Edge fromEdgeId(int ix) const {
133      return graph->fromEdgeId(ix);
134    }
135
136    UEdge fromUEdgeId(int ix) const {
137      return graph->fromUEdgeId(ix);
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& notifier(Node) const {
155      return graph->notifier(Node());
156    }
157
158    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
159
160    EdgeNotifier& notifier(Edge) const {
161      return graph->notifier(Edge());
162    }
163
164    typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
165
166    UEdgeNotifier& notifier(UEdge) const {
167      return graph->notifier(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::source(i)]
315            || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d);
316    }
317
318    void next(Node& i) const {
319      Parent::next(i);
320      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
321    }
322
323    void next(Edge& i) const {
324      Parent::next(i);
325      while (i!=INVALID && (!(*uedge_filter_map)[i]
326             || !(*node_filter_map)[Parent::source(i)]
327             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
328    }
329
330    void next(UEdge& i) const {
331      Parent::next(i);
332      while (i!=INVALID && (!(*uedge_filter_map)[i]
333             || !(*node_filter_map)[Parent::source(i)]
334             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
335    }
336
337    void nextIn(Edge& i) const {
338      Parent::nextIn(i);
339      while (i!=INVALID && (!(*uedge_filter_map)[i]
340             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
341    }
342
343    void nextOut(Edge& i) const {
344      Parent::nextOut(i);
345      while (i!=INVALID && (!(*uedge_filter_map)[i]
346             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
347    }
348
349    void nextInc(UEdge& i, bool& d) const {
350      Parent::nextInc(i, d);
351      while (i!=INVALID && (!(*uedge_filter_map)[i]
352            || !(*node_filter_map)[Parent::source(i)]
353            || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d);
354    }
355
356    /// \brief Hide the given node in the graph.
357    ///
358    /// This function hides \c n in the graph, i.e. the iteration
359    /// jumps over it. This is done by simply setting the value of \c n 
360    /// to be false in the corresponding node-map.
361    void hide(const Node& n) const { node_filter_map->set(n, false); }
362
363    /// \brief Hide the given undirected edge in the graph.
364    ///
365    /// This function hides \c e in the graph, i.e. the iteration
366    /// jumps over it. This is done by simply setting the value of \c e 
367    /// to be false in the corresponding uedge-map.
368    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
369
370    /// \brief Unhide the given node in the graph.
371    ///
372    /// The value of \c n is set to be true in the node-map which stores
373    /// hide information. If \c n was hidden previuosly, then it is shown
374    /// again
375     void unHide(const Node& n) const { node_filter_map->set(n, true); }
376
377    /// \brief Hide the given undirected edge in the graph.
378    ///
379    /// The value of \c e is set to be true in the uedge-map which stores
380    /// hide information. If \c e was hidden previuosly, then it is shown
381    /// again
382    void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
383
384    /// \brief Returns true if \c n is hidden.
385    ///
386    /// Returns true if \c n is hidden.
387    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
388
389    /// \brief Returns true if \c e is hidden.
390    ///
391    /// Returns true if \c e is hidden.
392    bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
393
394    typedef False NodeNumTag;
395    typedef False EdgeNumTag;
396
397    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
398    Edge findEdge(const Node& u, const Node& v,
399                  const Edge& prev = INVALID) {
400      if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {
401        return INVALID;
402      }
403      Edge edge = Parent::findEdge(u, v, prev);
404      while (edge != INVALID && !(*uedge_filter_map)[edge]) {
405        edge = Parent::findEdge(u, v, edge);
406      }
407      return edge;
408    }
409    UEdge findUEdge(const Node& u, const Node& v,
410                  const UEdge& prev = INVALID) {
411      if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {
412        return INVALID;
413      }
414      UEdge uedge = Parent::findUEdge(u, v, prev);
415      while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
416        uedge = Parent::findUEdge(u, v, uedge);
417      }
418      return uedge;
419    }
420
421    template <typename _Value>
422    class NodeMap
423      : public SubMapExtender<Adaptor,
424                              typename Parent::template NodeMap<_Value> >
425    {
426    public:
427      typedef Adaptor Graph;
428      typedef SubMapExtender<Adaptor, typename Parent::
429                             template NodeMap<_Value> > Parent;
430   
431      NodeMap(const Graph& g)
432        : Parent(g) {}
433      NodeMap(const Graph& g, const _Value& v)
434        : Parent(g, v) {}
435   
436      NodeMap& operator=(const NodeMap& cmap) {
437        return operator=<NodeMap>(cmap);
438      }
439   
440      template <typename CMap>
441      NodeMap& operator=(const CMap& cmap) {
442        Parent::operator=(cmap);
443        return *this;
444      }
445    };
446
447    template <typename _Value>
448    class EdgeMap
449      : public SubMapExtender<Adaptor,
450                              typename Parent::template EdgeMap<_Value> >
451    {
452    public:
453      typedef Adaptor Graph;
454      typedef SubMapExtender<Adaptor, typename Parent::
455                             template EdgeMap<_Value> > Parent;
456   
457      EdgeMap(const Graph& g)
458        : Parent(g) {}
459      EdgeMap(const Graph& g, const _Value& v)
460        : Parent(g, v) {}
461   
462      EdgeMap& operator=(const EdgeMap& cmap) {
463        return operator=<EdgeMap>(cmap);
464      }
465   
466      template <typename CMap>
467      EdgeMap& operator=(const CMap& cmap) {
468        Parent::operator=(cmap);
469        return *this;
470      }
471    };
472
473    template <typename _Value>
474    class UEdgeMap
475      : public SubMapExtender<Adaptor,
476                              typename Parent::template UEdgeMap<_Value> >
477    {
478    public:
479      typedef Adaptor Graph;
480      typedef SubMapExtender<Adaptor, typename Parent::
481                             template UEdgeMap<_Value> > Parent;
482   
483      UEdgeMap(const Graph& g)
484        : Parent(g) {}
485      UEdgeMap(const Graph& g, const _Value& v)
486        : Parent(g, v) {}
487   
488      UEdgeMap& operator=(const UEdgeMap& cmap) {
489        return operator=<UEdgeMap>(cmap);
490      }
491   
492      template <typename CMap>
493      UEdgeMap& operator=(const CMap& cmap) {
494        Parent::operator=(cmap);
495        return *this;
496      }
497    };
498
499  };
500
501  template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
502  class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false>
503    : public UGraphAdaptorBase<_UGraph> {
504  public:
505    typedef _UGraph Graph;
506    typedef SubUGraphAdaptorBase Adaptor;
507    typedef UGraphAdaptorBase<_UGraph> Parent;
508  protected:
509    NodeFilterMap* node_filter_map;
510    UEdgeFilterMap* uedge_filter_map;
511    SubUGraphAdaptorBase() : Parent(),
512                            node_filter_map(0), uedge_filter_map(0) { }
513
514    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
515      node_filter_map=&_node_filter_map;
516    }
517    void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
518      uedge_filter_map=&_uedge_filter_map;
519    }
520
521  public:
522
523    typedef typename Parent::Node Node;
524    typedef typename Parent::Edge Edge;
525    typedef typename Parent::UEdge UEdge;
526
527    void first(Node& i) const {
528      Parent::first(i);
529      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
530    }
531
532    void first(Edge& i) const {
533      Parent::first(i);
534      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
535    }
536
537    void first(UEdge& i) const {
538      Parent::first(i);
539      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
540    }
541
542    void firstIn(Edge& i, const Node& n) const {
543      Parent::firstIn(i, n);
544      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
545    }
546
547    void firstOut(Edge& i, const Node& n) const {
548      Parent::firstOut(i, n);
549      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
550    }
551
552    void firstInc(UEdge& i, bool& d, const Node& n) const {
553      Parent::firstInc(i, d, n);
554      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
555    }
556
557    void next(Node& i) const {
558      Parent::next(i);
559      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
560    }
561    void next(Edge& i) const {
562      Parent::next(i);
563      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
564    }
565    void next(UEdge& i) const {
566      Parent::next(i);
567      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
568    }
569    void nextIn(Edge& i) const {
570      Parent::nextIn(i);
571      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
572    }
573
574    void nextOut(Edge& i) const {
575      Parent::nextOut(i);
576      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
577    }
578    void nextInc(UEdge& i, bool& d) const {
579      Parent::nextInc(i, d);
580      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
581    }
582
583    /// \brief Hide the given node in the graph.
584    ///
585    /// This function hides \c n in the graph, i.e. the iteration
586    /// jumps over it. This is done by simply setting the value of \c n 
587    /// to be false in the corresponding node-map.
588    void hide(const Node& n) const { node_filter_map->set(n, false); }
589
590    /// \brief Hide the given undirected edge in the graph.
591    ///
592    /// This function hides \c e in the graph, i.e. the iteration
593    /// jumps over it. This is done by simply setting the value of \c e 
594    /// to be false in the corresponding uedge-map.
595    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
596
597    /// \brief Unhide the given node in the graph.
598    ///
599    /// The value of \c n is set to be true in the node-map which stores
600    /// hide information. If \c n was hidden previuosly, then it is shown
601    /// again
602     void unHide(const Node& n) const { node_filter_map->set(n, true); }
603
604    /// \brief Hide the given undirected edge in the graph.
605    ///
606    /// The value of \c e is set to be true in the uedge-map which stores
607    /// hide information. If \c e was hidden previuosly, then it is shown
608    /// again
609    void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
610
611    /// \brief Returns true if \c n is hidden.
612    ///
613    /// Returns true if \c n is hidden.
614    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
615
616    /// \brief Returns true if \c e is hidden.
617    ///
618    /// Returns true if \c e is hidden.
619    bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
620
621    typedef False NodeNumTag;
622    typedef False EdgeNumTag;
623
624    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
625    Edge findEdge(const Node& u, const Node& v,
626                  const Edge& prev = INVALID) {
627      Edge edge = Parent::findEdge(u, v, prev);
628      while (edge != INVALID && !(*uedge_filter_map)[edge]) {
629        edge = Parent::findEdge(u, v, edge);
630      }
631      return edge;
632    }
633    UEdge findUEdge(const Node& u, const Node& v,
634                  const UEdge& prev = INVALID) {
635      UEdge uedge = Parent::findUEdge(u, v, prev);
636      while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
637        uedge = Parent::findUEdge(u, v, uedge);
638      }
639      return uedge;
640    }
641
642    template <typename _Value>
643    class NodeMap
644      : public SubMapExtender<Adaptor,
645                              typename Parent::template NodeMap<_Value> >
646    {
647    public:
648      typedef Adaptor Graph;
649      typedef SubMapExtender<Adaptor, typename Parent::
650                             template NodeMap<_Value> > Parent;
651   
652      NodeMap(const Graph& g)
653        : Parent(g) {}
654      NodeMap(const Graph& g, const _Value& v)
655        : Parent(g, v) {}
656   
657      NodeMap& operator=(const NodeMap& cmap) {
658        return operator=<NodeMap>(cmap);
659      }
660   
661      template <typename CMap>
662      NodeMap& operator=(const CMap& cmap) {
663        Parent::operator=(cmap);
664        return *this;
665      }
666    };
667
668    template <typename _Value>
669    class EdgeMap
670      : public SubMapExtender<Adaptor,
671                              typename Parent::template EdgeMap<_Value> >
672    {
673    public:
674      typedef Adaptor Graph;
675      typedef SubMapExtender<Adaptor, typename Parent::
676                             template EdgeMap<_Value> > Parent;
677   
678      EdgeMap(const Graph& g)
679        : Parent(g) {}
680      EdgeMap(const Graph& g, const _Value& v)
681        : Parent(g, v) {}
682   
683      EdgeMap& operator=(const EdgeMap& cmap) {
684        return operator=<EdgeMap>(cmap);
685      }
686   
687      template <typename CMap>
688      EdgeMap& operator=(const CMap& cmap) {
689        Parent::operator=(cmap);
690        return *this;
691      }
692    };
693
694    template <typename _Value>
695    class UEdgeMap
696      : public SubMapExtender<Adaptor,
697                              typename Parent::template UEdgeMap<_Value> >
698    {
699    public:
700      typedef Adaptor Graph;
701      typedef SubMapExtender<Adaptor, typename Parent::
702                             template UEdgeMap<_Value> > Parent;
703   
704      UEdgeMap(const Graph& g)
705        : Parent(g) {}
706      UEdgeMap(const Graph& g, const _Value& v)
707        : Parent(g, v) {}
708   
709      UEdgeMap& operator=(const UEdgeMap& cmap) {
710        return operator=<UEdgeMap>(cmap);
711      }
712   
713      template <typename CMap>
714      UEdgeMap& operator=(const CMap& cmap) {
715        Parent::operator=(cmap);
716        return *this;
717      }
718    };
719  };
720
721  /// \ingroup graph_adaptors
722  ///
723  /// \brief A graph adaptor for hiding nodes and edges from an undirected
724  /// graph.
725  ///
726  /// SubUGraphAdaptor shows the undirected graph with filtered node-set and
727  /// edge-set. If the \c checked parameter is true then it filters the edgeset
728  /// to do not get invalid edges without source or target.
729  ///
730  /// If the \c checked template parameter is false then we have to note that
731  /// the node-iterator cares only the filter on the node-set, and the
732  /// edge-iterator cares only the filter on the edge-set.
733  /// This way the edge-map
734  /// should filter all edges which's source or target is filtered by the
735  /// node-filter.
736  ///
737  template<typename _UGraph, typename NodeFilterMap,
738           typename UEdgeFilterMap, bool checked = true>
739  class SubUGraphAdaptor :
740    public UGraphAdaptorExtender<
741    SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
742  public:
743    typedef _UGraph Graph;
744    typedef UGraphAdaptorExtender<
745      SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
746  protected:
747    SubUGraphAdaptor() { }
748  public:
749    SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,
750                    UEdgeFilterMap& _uedge_filter_map) {
751      setGraph(_graph);
752      setNodeFilterMap(_node_filter_map);
753      setUEdgeFilterMap(_uedge_filter_map);
754    }
755  };
756
757  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
758  SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
759  subUGraphAdaptor(const UGraph& graph,
760                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
761    return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
762      (graph, nfm, efm);
763  }
764
765  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
766  SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
767  subUGraphAdaptor(const UGraph& graph,
768                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
769    return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
770      (graph, nfm, efm);
771  }
772
773  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
774  SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
775  subUGraphAdaptor(const UGraph& graph,
776                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
777    return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
778      (graph, nfm, efm);
779  }
780
781  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
782  SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
783  subUGraphAdaptor(const UGraph& graph,
784                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
785    return SubUGraphAdaptor<const UGraph, const NodeFilterMap,
786      const EdgeFilterMap>(graph, nfm, efm);
787  }
788
789  /// \ingroup graph_adaptors
790  ///
791  /// \brief An adaptor for hiding nodes from an undirected graph.
792  ///
793  /// An adaptor for hiding nodes from an undirected graph.
794  /// This adaptor specializes SubUGraphAdaptor in the way that only
795  /// the node-set
796  /// can be filtered. In usual case the checked parameter is true, we get the
797  /// induced subgraph. But if the checked parameter is false then we can only
798  /// filter only isolated nodes.
799  template<typename _UGraph, typename NodeFilterMap, bool checked = true>
800  class NodeSubUGraphAdaptor :
801    public SubUGraphAdaptor<_UGraph, NodeFilterMap,
802                            ConstMap<typename _UGraph::UEdge, bool>, checked> {
803  public:
804    typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
805                             ConstMap<typename _UGraph::UEdge, bool> > Parent;
806    typedef _UGraph Graph;
807  protected:
808    ConstMap<typename _UGraph::UEdge, bool> const_true_map;
809
810    NodeSubUGraphAdaptor() : const_true_map(true) {
811      Parent::setUEdgeFilterMap(const_true_map);
812    }
813
814  public:
815    NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
816      Parent(), const_true_map(true) {
817      Parent::setGraph(_graph);
818      Parent::setNodeFilterMap(_node_filter_map);
819      Parent::setUEdgeFilterMap(const_true_map);
820    }
821  };
822
823  template<typename UGraph, typename NodeFilterMap>
824  NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
825  nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
826    return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
827  }
828
829  template<typename UGraph, typename NodeFilterMap>
830  NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
831  nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
832    return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
833  }
834
835  /// \ingroup graph_adaptors
836  ///
837  /// \brief An adaptor for hiding undirected edges from an undirected graph.
838  ///
839  /// \warning Graph adaptors are in even more experimental state
840  /// than the other parts of the lib. Use them at you own risk.
841  ///
842  /// An adaptor for hiding undirected edges from an undirected graph.
843  /// This adaptor specializes SubUGraphAdaptor in the way that
844  /// only the edge-set
845  /// can be filtered.
846  template<typename _UGraph, typename UEdgeFilterMap>
847  class EdgeSubUGraphAdaptor :
848    public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
849                            UEdgeFilterMap, false> {
850  public:
851    typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
852                             UEdgeFilterMap, false> Parent;
853    typedef _UGraph Graph;
854  protected:
855    ConstMap<typename Graph::Node, bool> const_true_map;
856
857    EdgeSubUGraphAdaptor() : const_true_map(true) {
858      Parent::setNodeFilterMap(const_true_map);
859    }
860
861  public:
862
863    EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
864      Parent(), const_true_map(true) {
865      Parent::setGraph(_graph);
866      Parent::setNodeFilterMap(const_true_map);
867      Parent::setUEdgeFilterMap(_uedge_filter_map);
868    }
869
870  };
871
872  template<typename UGraph, typename EdgeFilterMap>
873  EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
874  edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
875    return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
876  }
877
878  template<typename UGraph, typename EdgeFilterMap>
879  EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
880  edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
881    return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
882  }
883
884  /// \brief Base of direct undirected graph adaptor
885  ///
886  /// Base class of the direct undirected graph adaptor. All public member
887  /// of this class can be used with the DirUGraphAdaptor too.
888  /// \sa DirUGraphAdaptor
889  template <typename _UGraph, typename _DirectionMap>
890  class DirUGraphAdaptorBase {
891  public:
892   
893    typedef _UGraph Graph;
894    typedef _DirectionMap DirectionMap;
895
896    typedef typename _UGraph::Node Node;
897    typedef typename _UGraph::UEdge Edge;
898   
899    /// \brief Reverse edge
900    ///
901    /// It reverse the given edge. It simply negate the direction in the map.
902    void reverseEdge(const Edge& edge) {
903      direction->set(edge, !(*direction)[edge]);
904    }
905
906    void first(Node& i) const { graph->first(i); }
907    void first(Edge& i) const { graph->first(i); }
908    void firstIn(Edge& i, const Node& n) const {
909      bool d;
910      graph->firstInc(i, d, n);
911      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
912    }
913    void firstOut(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
919    void next(Node& i) const { graph->next(i); }
920    void next(Edge& i) const { graph->next(i); }
921    void nextIn(Edge& i) const {
922      bool d = !(*direction)[i];
923      graph->nextInc(i, d);
924      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
925    }
926    void nextOut(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
932    Node source(const Edge& e) const {
933      return (*direction)[e] ? graph->source(e) : graph->target(e);
934    }
935    Node target(const Edge& e) const {
936      return (*direction)[e] ? graph->target(e) : graph->source(e);
937    }
938
939    typedef NodeNumTagIndicator<Graph> NodeNumTag;
940    int nodeNum() const { return graph->nodeNum(); }
941   
942    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
943    int edgeNum() const { return graph->uEdgeNum(); }
944
945    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
946    Edge findEdge(const Node& u, const Node& v,
947                  const Edge& prev = INVALID) {
948      Edge edge = prev;
949      bool d = edge == INVALID ? true : (*direction)[edge];
950      if (d) {
951        edge = graph->findUEdge(u, v, edge);
952        while (edge != INVALID && !(*direction)[edge]) {
953          graph->findUEdge(u, v, edge);
954        }
955        if (edge != INVALID) return edge;
956      }
957      graph->findUEdge(v, u, edge);
958      while (edge != INVALID && (*direction)[edge]) {
959        graph->findUEdge(u, v, edge);
960      }
961      return edge;
962    }
963 
964    Node addNode() const {
965      return Node(graph->addNode());
966    }
967
968    Edge addEdge(const Node& u, const Node& v) const {
969      Edge edge = graph->addEdge(u, v);
970      direction->set(edge, graph->source(edge) == u);
971      return edge;
972    }
973
974    void erase(const Node& i) const { graph->erase(i); }
975    void erase(const Edge& i) const { graph->erase(i); }
976 
977    void clear() const { graph->clear(); }
978   
979    int id(const Node& v) const { return graph->id(v); }
980    int id(const Edge& e) const { return graph->id(e); }
981
982    int maxNodeId() const {
983      return graph->maxNodeId();
984    }
985
986    int maxEdgeId() const {
987      return graph->maxEdgeId();
988    }
989
990    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
991
992    NodeNotifier& notifier(Node) const {
993      return graph->notifier(Node());
994    }
995
996    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
997
998    EdgeNotifier& notifier(Edge) const {
999      return graph->notifier(Edge());
1000    }
1001
1002    template <typename _Value>
1003    class NodeMap : public _UGraph::template NodeMap<_Value> {
1004    public:
1005
1006      typedef typename _UGraph::template NodeMap<_Value> Parent;
1007
1008      explicit NodeMap(const DirUGraphAdaptorBase& ga)
1009        : Parent(*ga.graph) {}
1010
1011      NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
1012        : Parent(*ga.graph, value) {}
1013
1014      NodeMap& operator=(const NodeMap& cmap) {
1015        return operator=<NodeMap>(cmap);
1016      }
1017
1018      template <typename CMap>
1019      NodeMap& operator=(const CMap& cmap) {
1020        Parent::operator=(cmap);
1021        return *this;
1022      }
1023
1024    };
1025
1026    template <typename _Value>
1027    class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
1028    public:
1029
1030      typedef typename _UGraph::template UEdgeMap<_Value> Parent;
1031
1032      explicit EdgeMap(const DirUGraphAdaptorBase& ga)
1033        : Parent(*ga.graph) { }
1034
1035      EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
1036        : Parent(*ga.graph, value) { }
1037
1038      EdgeMap& operator=(const EdgeMap& cmap) {
1039        return operator=<EdgeMap>(cmap);
1040      }
1041
1042      template <typename CMap>
1043      EdgeMap& operator=(const CMap& cmap) {
1044        Parent::operator=(cmap);
1045        return *this;
1046      }
1047    };
1048
1049   
1050
1051  protected:
1052    Graph* graph;
1053    DirectionMap* direction;
1054
1055    void setDirectionMap(DirectionMap& _direction) {
1056      direction = &_direction;
1057    }
1058
1059    void setGraph(Graph& _graph) {
1060      graph = &_graph;
1061    }
1062
1063  };
1064
1065
1066  /// \ingroup graph_adaptors
1067  ///
1068  /// \brief A directed graph is made from an undirected graph by an adaptor
1069  ///
1070  /// This adaptor gives a direction for each uedge in the undirected
1071  /// graph. The direction of the edges stored in the
1072  /// DirectionMap. This map is a bool map on the undirected edges. If
1073  /// the uedge is mapped to true then the direction of the directed
1074  /// edge will be the same as the default direction of the uedge. The
1075  /// edges can be easily reverted by the \ref
1076  /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the
1077  /// adaptor.
1078  ///
1079  /// It can be used to solve orientation problems on directed graphs.
1080  /// By example how can we orient an undirected graph to get the minimum
1081  /// number of strongly connected components. If we orient the edges with
1082  /// the dfs algorithm out from the source then we will get such an
1083  /// orientation.
1084  ///
1085  /// We use the \ref DfsVisitor "visitor" interface of the
1086  /// \ref DfsVisit "dfs" algorithm:
1087  ///\code
1088  /// template <typename DirMap>
1089  /// class OrientVisitor : public DfsVisitor<UGraph> {
1090  /// public:
1091  ///
1092  ///   OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
1093  ///     : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
1094  ///
1095  ///   void discover(const Edge& edge) {
1096  ///     _processed.set(edge, true);
1097  ///     _dirMap.set(edge, _ugraph.direction(edge));
1098  ///   }
1099  ///
1100  ///   void examine(const Edge& edge) {
1101  ///     if (_processed[edge]) return;
1102  ///     _processed.set(edge, true);
1103  ///     _dirMap.set(edge, _ugraph.direction(edge));
1104  ///   } 
1105  ///
1106  /// private:
1107  ///   const UGraph& _ugraph; 
1108  ///   DirMap& _dirMap;
1109  ///   UGraph::UEdgeMap<bool> _processed;
1110  /// };
1111  ///\endcode
1112  ///
1113  /// And now we can use the orientation:
1114  ///\code
1115  /// UGraph::UEdgeMap<bool> dmap(ugraph);
1116  ///
1117  /// typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
1118  /// Visitor visitor(ugraph, dmap);
1119  ///
1120  /// DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
1121  ///
1122  /// dfs.run();
1123  ///
1124  /// typedef DirUGraphAdaptor<UGraph> DGraph;
1125  /// DGraph dgraph(ugraph, dmap);
1126  ///
1127  /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
1128  ///              countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");
1129  ///\endcode
1130  ///
1131  /// The number of the bi-connected components is a lower bound for
1132  /// the number of the strongly connected components in the directed
1133  /// graph because if we contract the bi-connected components to
1134  /// nodes we will get a tree therefore we cannot orient edges in
1135  /// both direction between bi-connected components. In the other way
1136  /// the algorithm will orient one component to be strongly
1137  /// connected. The two relations proof that the assertion will
1138  /// be always true and the found solution is optimal.
1139  ///
1140  /// \sa DirUGraphAdaptorBase
1141  /// \sa dirUGraphAdaptor
1142  template<typename _Graph,
1143           typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
1144  class DirUGraphAdaptor :
1145    public GraphAdaptorExtender<
1146    DirUGraphAdaptorBase<_Graph, DirectionMap> > {
1147  public:
1148    typedef _Graph Graph;
1149    typedef GraphAdaptorExtender<
1150      DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1151  protected:
1152    DirUGraphAdaptor() { }
1153  public:
1154   
1155    /// \brief Constructor of the adaptor
1156    ///
1157    /// Constructor of the adaptor
1158    DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
1159      setGraph(_graph);
1160      setDirectionMap(_direction_map);
1161    }
1162  };
1163
1164  /// \brief Just gives back a DirUGraphAdaptor
1165  ///
1166  /// Just gives back a DirUGraphAdaptor
1167  template<typename UGraph, typename DirectionMap>
1168  DirUGraphAdaptor<const UGraph, DirectionMap>
1169  dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
1170    return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
1171  }
1172
1173  template<typename UGraph, typename DirectionMap>
1174  DirUGraphAdaptor<const UGraph, const DirectionMap>
1175  dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
1176    return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
1177  }
1178
1179}
1180
1181#endif
Note: See TracBrowser for help on using the repository browser.