COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/ugraph_adaptor.h @ 2045:012cd0ca3254

Last change on this file since 2045:012cd0ca3254 was 2042:bdc953f2a449, checked in by Balazs Dezso, 18 years ago

New Algorithm group for matchings

LaTeX formulas
Bug fix => /\f$ will cause parsing error in doxygen

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