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, 11 years ago

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

File size: 37.1 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_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 nodeFromId(int ix) const {
129      return graph->nodeFromId(ix);
130    }
131
132    Edge edgeFromId(int ix) const {
133      return graph->edgeFromId(ix);
134    }
135
136    UEdge uEdgeFromId(int ix) const {
137      return graph->uEdgeFromId(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.  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.
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:
807    ConstMap<typename _UGraph::UEdge, bool> const_true_map;
808
809    NodeSubUGraphAdaptor() : const_true_map(true) {
810      Parent::setUEdgeFilterMap(const_true_map);
811    }
812
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
834  /// \ingroup graph_adaptors
835  ///
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;
855
856    EdgeSubUGraphAdaptor() : const_true_map(true) {
857      Parent::setNodeFilterMap(const_true_map);
858    }
859
860  public:
861
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    }
868
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
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
888  template <typename _UGraph, typename _DirectionMap>
889  class DirUGraphAdaptorBase {
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   
898    /// \brief Reverse edge
899    ///
900    /// It reverse the given edge. It simply negate the direction in the map.
901    void reverseEdge(const Edge& edge) {
902      direction->set(edge, !(*direction)[edge]);
903    }
904
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;
945    Edge findEdge(const Node& u, const Node& v,
946                  const Edge& prev = INVALID) {
947      Edge edge = prev;
948      bool d = edge == INVALID ? true : (*direction)[edge];
949      if (d) {
950        edge = graph->findUEdge(u, v, edge);
951        while (edge != INVALID && !(*direction)[edge]) {
952          graph->findUEdge(u, v, edge);
953        }
954        if (edge != INVALID) return edge;
955      }
956      graph->findUEdge(v, u, edge);
957      while (edge != INVALID && (*direction)[edge]) {
958        graph->findUEdge(u, v, edge);
959      }
960      return edge;
961    }
962 
963    Node addNode() const {
964      return Node(graph->addNode());
965    }
966
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);
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
981    int maxNodeId() const {
982      return graph->maxNodeId();
983    }
984
985    int maxEdgeId() const {
986      return graph->maxEdgeId();
987    }
988
989    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
990
991    NodeNotifier& notifier(Node) const {
992      return graph->notifier(Node());
993    }
994
995    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
996
997    EdgeNotifier& notifier(Edge) const {
998      return graph->notifier(Edge());
999    }
1000
1001    template <typename _Value>
1002    class NodeMap : public _UGraph::template NodeMap<_Value> {
1003    public:
1004
1005      typedef typename _UGraph::template NodeMap<_Value> Parent;
1006
1007      explicit NodeMap(const DirUGraphAdaptorBase& ga)
1008        : Parent(*ga.graph) {}
1009
1010      NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
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
1023    };
1024
1025    template <typename _Value>
1026    class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
1027    public:
1028
1029      typedef typename _UGraph::template UEdgeMap<_Value> Parent;
1030
1031      explicit EdgeMap(const DirUGraphAdaptorBase& ga)
1032        : Parent(*ga.graph) { }
1033
1034      EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
1035        : Parent(*ga.graph, value) { }
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      }
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
1065  /// \ingroup graph_adaptors
1066  ///
1067  /// \brief A directed graph is made from an undirected graph by an adaptor
1068  ///
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
1141  template<typename _Graph,
1142           typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
1143  class DirUGraphAdaptor :
1144    public GraphAdaptorExtender<
1145    DirUGraphAdaptorBase<_Graph, DirectionMap> > {
1146  public:
1147    typedef _Graph Graph;
1148    typedef GraphAdaptorExtender<
1149      DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1150  protected:
1151    DirUGraphAdaptor() { }
1152  public:
1153   
1154    /// \brief Constructor of the adaptor
1155    ///
1156    /// Constructor of the adaptor
1157    DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
1158      setGraph(_graph);
1159      setDirectionMap(_direction_map);
1160    }
1161  };
1162
1163  /// \brief Just gives back a DirUGraphAdaptor
1164  ///
1165  /// Just gives back a DirUGraphAdaptor
1166  template<typename UGraph, typename DirectionMap>
1167  DirUGraphAdaptor<const UGraph, DirectionMap>
1168  dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
1169    return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
1170  }
1171
1172  template<typename UGraph, typename DirectionMap>
1173  DirUGraphAdaptor<const UGraph, const DirectionMap>
1174  dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
1175    return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
1176  }
1177
1178}
1179
1180#endif
Note: See TracBrowser for help on using the repository browser.