COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/ugraph_adaptor.h

Last change on this file was 2617:5222a3c470ed, checked in by Balazs Dezso, 16 years ago

Backport bug fix for Id handling from hg changeset [e67acd83a9ca]

File size: 37.1 KB
RevLine 
[1979]1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
[2553]5 * Copyright (C) 2003-2008
[1979]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
[1993]30#include <lemon/bits/invalid.h>
[1979]31#include <lemon/maps.h>
32
33#include <lemon/bits/graph_adaptor_extender.h>
34
[1993]35#include <lemon/bits/traits.h>
[1979]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(); }
[2031]99    int uEdgeNum() const { return graph->uEdgeNum(); }
[1979]100
101    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
[2386]102    Edge findEdge(const Node& u, const Node& v,
[1979]103                  const Edge& prev = INVALID) {
[2386]104      return graph->findEdge(u, v, prev);
[1979]105    }
[2386]106    UEdge findUEdge(const Node& u, const Node& v,
[1979]107                    const UEdge& prev = INVALID) {
[2386]108      return graph->findUEdge(u, v, prev);
[1979]109    }
110 
111    Node addNode() const { return graph->addNode(); }
[2386]112    UEdge addEdge(const Node& u, const Node& v) const {
113      return graph->addEdge(u, v);
[1979]114    }
115
116    void erase(const Node& i) const { graph->erase(i); }
[2031]117    void erase(const UEdge& i) const { graph->erase(i); }
[1979]118 
119    void clear() const { graph->clear(); }
120   
[2031]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
[1979]124    int id(const Node& v) const { return graph->id(v); }
[2031]125    int id(const Edge& e) const { return graph->id(e); }
[1979]126    int id(const UEdge& e) const { return graph->id(e); }
127
[2617]128    Node nodeFromId(int ix) const {
129      return graph->nodeFromId(ix);
[2031]130    }
131
[2617]132    Edge edgeFromId(int ix) const {
133      return graph->edgeFromId(ix);
[2031]134    }
135
[2617]136    UEdge uEdgeFromId(int ix) const {
137      return graph->uEdgeFromId(ix);
[2031]138    }
[1991]139
140    int maxNodeId() const {
141      return graph->maxNodeId();
[1979]142    }
143
[1991]144    int maxEdgeId() const {
145      return graph->maxEdgeId();
[1979]146    }
147
[1991]148    int maxUEdgeId() const {
149      return graph->maxEdgeId();
[1979]150    }
151
[1991]152    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
153
[2381]154    NodeNotifier& notifier(Node) const {
155      return graph->notifier(Node());
[1991]156    }
157
158    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
159
[2381]160    EdgeNotifier& notifier(Edge) const {
161      return graph->notifier(Edge());
[1991]162    }
163
164    typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
165
[2381]166    UEdgeNotifier& notifier(UEdge) const {
167      return graph->notifier(UEdge());
[1991]168    }
[1979]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) {
[2031]185        Parent::operator=(cmap);
186        return *this;
[1979]187      }
[2031]188
[1979]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) {
[2031]206        Parent::operator=(cmap);
[1979]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) {
[2031]226        Parent::operator=(cmap);
227        return *this;
[1979]228      }
229    };
230
231  };
232
233  /// \ingroup graph_adaptors
[2084]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.
[1979]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;
[2031]257    typedef SubUGraphAdaptorBase Adaptor;
[1979]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]
[2381]314            || !(*node_filter_map)[Parent::source(i)]
[1979]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);
[2381]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);
[1979]354    }
355
[2084]356    /// \brief Hide the given node in the graph.
357    ///
[1979]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
[2084]363    /// \brief Hide the given undirected edge in the graph.
364    ///
[1979]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 
[2084]367    /// to be false in the corresponding uedge-map.
[1979]368    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
369
[2084]370    /// \brief Unhide the given node in the graph.
371    ///
[1979]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
[2084]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
[1979]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
[2084]384    /// \brief Returns true if \c n is hidden.
385    ///
[1979]386    /// Returns true if \c n is hidden.
387    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
388
[2084]389    /// \brief Returns true if \c e is hidden.
[1979]390    ///
[2084]391    /// Returns true if \c e is hidden.
[1979]392    bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
393
394    typedef False NodeNumTag;
395    typedef False EdgeNumTag;
[1991]396
397    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
[2386]398    Edge findEdge(const Node& u, const Node& v,
[1991]399                  const Edge& prev = INVALID) {
[2386]400      if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {
[1991]401        return INVALID;
402      }
[2386]403      Edge edge = Parent::findEdge(u, v, prev);
[1991]404      while (edge != INVALID && !(*uedge_filter_map)[edge]) {
[2386]405        edge = Parent::findEdge(u, v, edge);
[1991]406      }
407      return edge;
408    }
[2386]409    UEdge findUEdge(const Node& u, const Node& v,
[1991]410                  const UEdge& prev = INVALID) {
[2386]411      if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {
[1991]412        return INVALID;
413      }
[2386]414      UEdge uedge = Parent::findUEdge(u, v, prev);
[1991]415      while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
[2386]416        uedge = Parent::findUEdge(u, v, uedge);
[1991]417      }
418      return uedge;
419    }
[2031]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   
[2386]431      NodeMap(const Graph& g)
432        : Parent(g) {}
433      NodeMap(const Graph& g, const _Value& v)
434        : Parent(g, v) {}
[2031]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   
[2386]457      EdgeMap(const Graph& g)
458        : Parent(g) {}
459      EdgeMap(const Graph& g, const _Value& v)
460        : Parent(g, v) {}
[2031]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   
[2386]483      UEdgeMap(const Graph& g)
484        : Parent(g) {}
485      UEdgeMap(const Graph& g, const _Value& v)
486        : Parent(g, v) {}
[2031]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
[1979]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;
[2031]506    typedef SubUGraphAdaptorBase Adaptor;
[1979]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
[2084]583    /// \brief Hide the given node in the graph.
584    ///
[1979]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
[2084]590    /// \brief Hide the given undirected edge in the graph.
591    ///
[1979]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 
[2084]594    /// to be false in the corresponding uedge-map.
[1979]595    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
596
[2084]597    /// \brief Unhide the given node in the graph.
598    ///
[1979]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
[2084]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
[1979]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
[2084]611    /// \brief Returns true if \c n is hidden.
612    ///
[1979]613    /// Returns true if \c n is hidden.
614    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
615
[2084]616    /// \brief Returns true if \c e is hidden.
[1979]617    ///
[2084]618    /// Returns true if \c e is hidden.
[1979]619    bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
620
621    typedef False NodeNumTag;
622    typedef False EdgeNumTag;
[1991]623
624    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
[2386]625    Edge findEdge(const Node& u, const Node& v,
[1991]626                  const Edge& prev = INVALID) {
[2386]627      Edge edge = Parent::findEdge(u, v, prev);
[1991]628      while (edge != INVALID && !(*uedge_filter_map)[edge]) {
[2386]629        edge = Parent::findEdge(u, v, edge);
[1991]630      }
631      return edge;
632    }
[2386]633    UEdge findUEdge(const Node& u, const Node& v,
[1991]634                  const UEdge& prev = INVALID) {
[2386]635      UEdge uedge = Parent::findUEdge(u, v, prev);
[1991]636      while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
[2386]637        uedge = Parent::findUEdge(u, v, uedge);
[1991]638      }
639      return uedge;
640    }
[2031]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   
[2386]652      NodeMap(const Graph& g)
653        : Parent(g) {}
654      NodeMap(const Graph& g, const _Value& v)
655        : Parent(g, v) {}
[2031]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   
[2386]678      EdgeMap(const Graph& g)
679        : Parent(g) {}
680      EdgeMap(const Graph& g, const _Value& v)
681        : Parent(g, v) {}
[2031]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   
[2386]704      UEdgeMap(const Graph& g)
705        : Parent(g) {}
706      UEdgeMap(const Graph& g, const _Value& v)
707        : Parent(g, v) {}
[2031]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    };
[1979]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
[1980]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
[1979]789  /// \ingroup graph_adaptors
790  ///
[1980]791  /// \brief An adaptor for hiding nodes from an undirected graph.
[1979]792  ///
[2422]793  /// An adaptor for hiding nodes from an undirected graph.  This
794  /// adaptor specializes SubUGraphAdaptor in the way that only the
795  /// node-set can be filtered. In usual case the checked parameter is
796  /// true, we get the induced subgraph. But if the checked parameter
797  /// is false then we can filter only isolated nodes.
[1979]798  template<typename _UGraph, typename NodeFilterMap, bool checked = true>
799  class NodeSubUGraphAdaptor :
800    public SubUGraphAdaptor<_UGraph, NodeFilterMap,
801                            ConstMap<typename _UGraph::UEdge, bool>, checked> {
802  public:
803    typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
804                             ConstMap<typename _UGraph::UEdge, bool> > Parent;
805    typedef _UGraph Graph;
806  protected:
[1985]807    ConstMap<typename _UGraph::UEdge, bool> const_true_map;
[1991]808
809    NodeSubUGraphAdaptor() : const_true_map(true) {
810      Parent::setUEdgeFilterMap(const_true_map);
811    }
812
[1979]813  public:
814    NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
815      Parent(), const_true_map(true) {
816      Parent::setGraph(_graph);
817      Parent::setNodeFilterMap(_node_filter_map);
818      Parent::setUEdgeFilterMap(const_true_map);
819    }
820  };
821
822  template<typename UGraph, typename NodeFilterMap>
823  NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
824  nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
825    return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
826  }
827
828  template<typename UGraph, typename NodeFilterMap>
829  NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
830  nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
831    return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
832  }
833
[2042]834  /// \ingroup graph_adaptors
835  ///
[1979]836  /// \brief An adaptor for hiding undirected edges from an undirected graph.
837  ///
838  /// \warning Graph adaptors are in even more experimental state
839  /// than the other parts of the lib. Use them at you own risk.
840  ///
841  /// An adaptor for hiding undirected edges from an undirected graph.
842  /// This adaptor specializes SubUGraphAdaptor in the way that
843  /// only the edge-set
844  /// can be filtered.
845  template<typename _UGraph, typename UEdgeFilterMap>
846  class EdgeSubUGraphAdaptor :
847    public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
848                            UEdgeFilterMap, false> {
849  public:
850    typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
851                             UEdgeFilterMap, false> Parent;
852    typedef _UGraph Graph;
853  protected:
854    ConstMap<typename Graph::Node, bool> const_true_map;
[1991]855
856    EdgeSubUGraphAdaptor() : const_true_map(true) {
857      Parent::setNodeFilterMap(const_true_map);
858    }
859
[1979]860  public:
[2031]861
[1979]862    EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
863      Parent(), const_true_map(true) {
864      Parent::setGraph(_graph);
865      Parent::setNodeFilterMap(const_true_map);
866      Parent::setUEdgeFilterMap(_uedge_filter_map);
867    }
[2031]868
[1979]869  };
870
871  template<typename UGraph, typename EdgeFilterMap>
872  EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
873  edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
874    return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
875  }
876
877  template<typename UGraph, typename EdgeFilterMap>
878  EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
879  edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
880    return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
881  }
882
[2087]883  /// \brief Base of direct undirected graph adaptor
884  ///
885  /// Base class of the direct undirected graph adaptor. All public member
886  /// of this class can be used with the DirUGraphAdaptor too.
887  /// \sa DirUGraphAdaptor
[1979]888  template <typename _UGraph, typename _DirectionMap>
[1980]889  class DirUGraphAdaptorBase {
[1979]890  public:
891   
892    typedef _UGraph Graph;
893    typedef _DirectionMap DirectionMap;
894
895    typedef typename _UGraph::Node Node;
896    typedef typename _UGraph::UEdge Edge;
897   
[2087]898    /// \brief Reverse edge
899    ///
900    /// It reverse the given edge. It simply negate the direction in the map.
[1991]901    void reverseEdge(const Edge& edge) {
902      direction->set(edge, !(*direction)[edge]);
903    }
904
[1979]905    void first(Node& i) const { graph->first(i); }
906    void first(Edge& i) const { graph->first(i); }
907    void firstIn(Edge& i, const Node& n) const {
908      bool d;
909      graph->firstInc(i, d, n);
910      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
911    }
912    void firstOut(Edge& i, const Node& n ) const {
913      bool d;
914      graph->firstInc(i, d, n);
915      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
916    }
917
918    void next(Node& i) const { graph->next(i); }
919    void next(Edge& i) const { graph->next(i); }
920    void nextIn(Edge& i) const {
921      bool d = !(*direction)[i];
922      graph->nextInc(i, d);
923      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
924    }
925    void nextOut(Edge& i) const {
926      bool d = (*direction)[i];
927      graph->nextInc(i, d);
928      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
929    }
930
931    Node source(const Edge& e) const {
932      return (*direction)[e] ? graph->source(e) : graph->target(e);
933    }
934    Node target(const Edge& e) const {
935      return (*direction)[e] ? graph->target(e) : graph->source(e);
936    }
937
938    typedef NodeNumTagIndicator<Graph> NodeNumTag;
939    int nodeNum() const { return graph->nodeNum(); }
940   
941    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
942    int edgeNum() const { return graph->uEdgeNum(); }
943
944    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
[2386]945    Edge findEdge(const Node& u, const Node& v,
[1979]946                  const Edge& prev = INVALID) {
947      Edge edge = prev;
948      bool d = edge == INVALID ? true : (*direction)[edge];
949      if (d) {
[2386]950        edge = graph->findUEdge(u, v, edge);
[1979]951        while (edge != INVALID && !(*direction)[edge]) {
[2386]952          graph->findUEdge(u, v, edge);
[1979]953        }
954        if (edge != INVALID) return edge;
955      }
[2386]956      graph->findUEdge(v, u, edge);
[1979]957      while (edge != INVALID && (*direction)[edge]) {
[2386]958        graph->findUEdge(u, v, edge);
[1979]959      }
960      return edge;
961    }
962 
963    Node addNode() const {
964      return Node(graph->addNode());
965    }
966
[2386]967    Edge addEdge(const Node& u, const Node& v) const {
968      Edge edge = graph->addEdge(u, v);
969      direction->set(edge, graph->source(edge) == u);
[1979]970      return edge;
971    }
972
973    void erase(const Node& i) const { graph->erase(i); }
974    void erase(const Edge& i) const { graph->erase(i); }
975 
976    void clear() const { graph->clear(); }
977   
978    int id(const Node& v) const { return graph->id(v); }
979    int id(const Edge& e) const { return graph->id(e); }
980
[1991]981    int maxNodeId() const {
982      return graph->maxNodeId();
[1979]983    }
984
[1991]985    int maxEdgeId() const {
986      return graph->maxEdgeId();
987    }
988
989    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
990
[2381]991    NodeNotifier& notifier(Node) const {
992      return graph->notifier(Node());
[1991]993    }
994
995    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
996
[2381]997    EdgeNotifier& notifier(Edge) const {
998      return graph->notifier(Edge());
[1991]999    }
1000
[1979]1001    template <typename _Value>
1002    class NodeMap : public _UGraph::template NodeMap<_Value> {
1003    public:
[2031]1004
[1979]1005      typedef typename _UGraph::template NodeMap<_Value> Parent;
[2031]1006
[1980]1007      explicit NodeMap(const DirUGraphAdaptorBase& ga)
[2031]1008        : Parent(*ga.graph) {}
1009
[1980]1010      NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
[2031]1011        : Parent(*ga.graph, value) {}
1012
1013      NodeMap& operator=(const NodeMap& cmap) {
1014        return operator=<NodeMap>(cmap);
1015      }
1016
1017      template <typename CMap>
1018      NodeMap& operator=(const CMap& cmap) {
1019        Parent::operator=(cmap);
1020        return *this;
1021      }
1022
[1979]1023    };
1024
1025    template <typename _Value>
1026    class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
1027    public:
[2031]1028
[1980]1029      typedef typename _UGraph::template UEdgeMap<_Value> Parent;
[2031]1030
[1980]1031      explicit EdgeMap(const DirUGraphAdaptorBase& ga)
[1979]1032        : Parent(*ga.graph) { }
[2031]1033
[1980]1034      EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
[1979]1035        : Parent(*ga.graph, value) { }
[2031]1036
1037      EdgeMap& operator=(const EdgeMap& cmap) {
1038        return operator=<EdgeMap>(cmap);
1039      }
1040
1041      template <typename CMap>
1042      EdgeMap& operator=(const CMap& cmap) {
1043        Parent::operator=(cmap);
1044        return *this;
1045      }
[1979]1046    };
1047
1048   
1049
1050  protected:
1051    Graph* graph;
1052    DirectionMap* direction;
1053
1054    void setDirectionMap(DirectionMap& _direction) {
1055      direction = &_direction;
1056    }
1057
1058    void setGraph(Graph& _graph) {
1059      graph = &_graph;
1060    }
1061
1062  };
1063
1064
[1980]1065  /// \ingroup graph_adaptors
[1991]1066  ///
1067  /// \brief A directed graph is made from an undirected graph by an adaptor
[1980]1068  ///
[2087]1069  /// This adaptor gives a direction for each uedge in the undirected
1070  /// graph. The direction of the edges stored in the
1071  /// DirectionMap. This map is a bool map on the undirected edges. If
1072  /// the uedge is mapped to true then the direction of the directed
1073  /// edge will be the same as the default direction of the uedge. The
1074  /// edges can be easily reverted by the \ref
1075  /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the
1076  /// adaptor.
1077  ///
1078  /// It can be used to solve orientation problems on directed graphs.
1079  /// By example how can we orient an undirected graph to get the minimum
1080  /// number of strongly connected components. If we orient the edges with
1081  /// the dfs algorithm out from the source then we will get such an
1082  /// orientation.
1083  ///
1084  /// We use the \ref DfsVisitor "visitor" interface of the
1085  /// \ref DfsVisit "dfs" algorithm:
1086  ///\code
1087  /// template <typename DirMap>
1088  /// class OrientVisitor : public DfsVisitor<UGraph> {
1089  /// public:
1090  ///
1091  ///   OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
1092  ///     : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
1093  ///
1094  ///   void discover(const Edge& edge) {
1095  ///     _processed.set(edge, true);
1096  ///     _dirMap.set(edge, _ugraph.direction(edge));
1097  ///   }
1098  ///
1099  ///   void examine(const Edge& edge) {
1100  ///     if (_processed[edge]) return;
1101  ///     _processed.set(edge, true);
1102  ///     _dirMap.set(edge, _ugraph.direction(edge));
1103  ///   } 
1104  ///
1105  /// private:
1106  ///   const UGraph& _ugraph; 
1107  ///   DirMap& _dirMap;
1108  ///   UGraph::UEdgeMap<bool> _processed;
1109  /// };
1110  ///\endcode
1111  ///
1112  /// And now we can use the orientation:
1113  ///\code
1114  /// UGraph::UEdgeMap<bool> dmap(ugraph);
1115  ///
1116  /// typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
1117  /// Visitor visitor(ugraph, dmap);
1118  ///
1119  /// DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
1120  ///
1121  /// dfs.run();
1122  ///
1123  /// typedef DirUGraphAdaptor<UGraph> DGraph;
1124  /// DGraph dgraph(ugraph, dmap);
1125  ///
1126  /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
1127  ///              countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");
1128  ///\endcode
1129  ///
1130  /// The number of the bi-connected components is a lower bound for
1131  /// the number of the strongly connected components in the directed
1132  /// graph because if we contract the bi-connected components to
1133  /// nodes we will get a tree therefore we cannot orient edges in
1134  /// both direction between bi-connected components. In the other way
1135  /// the algorithm will orient one component to be strongly
1136  /// connected. The two relations proof that the assertion will
1137  /// be always true and the found solution is optimal.
1138  ///
1139  /// \sa DirUGraphAdaptorBase
1140  /// \sa dirUGraphAdaptor
[1980]1141  template<typename _Graph,
1142           typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
1143  class DirUGraphAdaptor :
[1979]1144    public GraphAdaptorExtender<
[1980]1145    DirUGraphAdaptorBase<_Graph, DirectionMap> > {
[1979]1146  public:
1147    typedef _Graph Graph;
1148    typedef GraphAdaptorExtender<
[1980]1149      DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
[1979]1150  protected:
[1980]1151    DirUGraphAdaptor() { }
[1979]1152  public:
[2087]1153   
1154    /// \brief Constructor of the adaptor
1155    ///
1156    /// Constructor of the adaptor
[1980]1157    DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
[1979]1158      setGraph(_graph);
1159      setDirectionMap(_direction_map);
1160    }
1161  };
1162
[2087]1163  /// \brief Just gives back a DirUGraphAdaptor
1164  ///
1165  /// Just gives back a DirUGraphAdaptor
[1979]1166  template<typename UGraph, typename DirectionMap>
[1980]1167  DirUGraphAdaptor<const UGraph, DirectionMap>
1168  dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
1169    return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
[1979]1170  }
1171
1172  template<typename UGraph, typename DirectionMap>
[1980]1173  DirUGraphAdaptor<const UGraph, const DirectionMap>
1174  dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
1175    return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
[1979]1176  }
1177
1178}
1179
1180#endif
Note: See TracBrowser for help on using the repository browser.