COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/ugraph_adaptor.h @ 2031:080d51024ac5

Last change on this file since 2031:080d51024ac5 was 2031:080d51024ac5, checked in by Balazs Dezso, 14 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

File size: 34.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_UGRAPH_ADAPTOR_H
20#define LEMON_UGRAPH_ADAPTOR_H
21
22///\ingroup graph_adaptors
23///\file
24///\brief Several graph adaptors.
25///
26///This file contains several useful ugraph adaptor functions.
27///
28///\author Balazs Dezso
29
30#include <lemon/bits/invalid.h>
31#include <lemon/maps.h>
32
33#include <lemon/bits/graph_adaptor_extender.h>
34
35#include <lemon/bits/traits.h>
36
37#include <iostream>
38
39namespace lemon {
40
41  /// \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    Graph& getGraph() { return *graph; }
68    const Graph& getGraph() const { return *graph; }
69
70  public:
71    UGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
72 
73    typedef typename Graph::Node Node;
74    typedef typename Graph::Edge Edge;
75    typedef typename Graph::UEdge UEdge;
76   
77    void first(Node& i) const { graph->first(i); }
78    void first(Edge& i) const { graph->first(i); }
79    void first(UEdge& i) const { graph->first(i); }
80    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
81    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
82    void firstInc(UEdge &i, bool &d, const Node &n) const {
83      graph->firstInc(i, d, n);
84    }
85
86    void next(Node& i) const { graph->next(i); }
87    void next(Edge& i) const { graph->next(i); }
88    void next(UEdge& i) const { graph->next(i); }
89    void nextIn(Edge& i) const { graph->nextIn(i); }
90    void nextOut(Edge& i) const { graph->nextOut(i); }
91    void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
92
93    Node source(const UEdge& e) const { return graph->source(e); }
94    Node target(const UEdge& e) const { return graph->target(e); }
95
96    Node source(const Edge& e) const { return graph->source(e); }
97    Node target(const Edge& e) const { return graph->target(e); }
98
99    typedef NodeNumTagIndicator<Graph> NodeNumTag;
100    int nodeNum() const { return graph->nodeNum(); }
101   
102    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
103    int edgeNum() const { return graph->edgeNum(); }
104    int uEdgeNum() const { return graph->uEdgeNum(); }
105
106    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
107    Edge findEdge(const Node& source, const Node& target,
108                  const Edge& prev = INVALID) {
109      return graph->findEdge(source, target, prev);
110    }
111    UEdge findUEdge(const Node& source, const Node& target,
112                    const UEdge& prev = INVALID) {
113      return graph->findUEdge(source, target, prev);
114    }
115 
116    Node addNode() const { return graph->addNode(); }
117    UEdge addEdge(const Node& source, const Node& target) const {
118      return graph->addEdge(source, target);
119    }
120
121    void erase(const Node& i) const { graph->erase(i); }
122    void erase(const UEdge& i) const { graph->erase(i); }
123 
124    void clear() const { graph->clear(); }
125   
126    bool direction(const Edge& e) const { return graph->direction(e); }
127    Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
128
129    int id(const Node& v) const { return graph->id(v); }
130    int id(const Edge& e) const { return graph->id(e); }
131    int id(const UEdge& e) const { return graph->id(e); }
132
133    Node fromNodeId(int id) const {
134      return graph->fromNodeId(id);
135    }
136
137    Edge fromEdgeId(int id) const {
138      return graph->fromEdgeId(id);
139    }
140
141    UEdge fromUEdgeId(int id) const {
142      return graph->fromUEdgeId(id);
143    }
144
145    int maxNodeId() const {
146      return graph->maxNodeId();
147    }
148
149    int maxEdgeId() const {
150      return graph->maxEdgeId();
151    }
152
153    int maxUEdgeId() const {
154      return graph->maxEdgeId();
155    }
156
157    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
158
159    NodeNotifier& getNotifier(Node) const {
160      return graph->getNotifier(Node());
161    }
162
163    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
164
165    EdgeNotifier& getNotifier(Edge) const {
166      return graph->getNotifier(Edge());
167    }
168
169    typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
170
171    UEdgeNotifier& getNotifier(UEdge) const {
172      return graph->getNotifier(UEdge());
173    }
174
175    template <typename _Value>
176    class NodeMap : public Graph::template NodeMap<_Value> {
177    public:
178      typedef typename Graph::template NodeMap<_Value> Parent;
179      explicit NodeMap(const UGraphAdaptorBase<Graph>& ga)
180        : Parent(*ga.graph) {}
181      NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
182        : Parent(*ga.graph, value) {}
183
184      NodeMap& operator=(const NodeMap& cmap) {
185        return operator=<NodeMap>(cmap);
186      }
187
188      template <typename CMap>
189      NodeMap& operator=(const CMap& cmap) {
190        Parent::operator=(cmap);
191        return *this;
192      }
193
194    };
195
196    template <typename _Value>
197    class EdgeMap : public Graph::template EdgeMap<_Value> {
198    public:
199      typedef typename Graph::template EdgeMap<_Value> Parent;
200      explicit EdgeMap(const UGraphAdaptorBase<Graph>& ga)
201        : Parent(*ga.graph) {}
202      EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
203        : Parent(*ga.graph, value) {}
204
205      EdgeMap& operator=(const EdgeMap& cmap) {
206        return operator=<EdgeMap>(cmap);
207      }
208
209      template <typename CMap>
210      EdgeMap& operator=(const CMap& cmap) {
211        Parent::operator=(cmap);
212        return *this;
213      }
214    };
215
216    template <typename _Value>
217    class UEdgeMap : public Graph::template UEdgeMap<_Value> {
218    public:
219      typedef typename Graph::template UEdgeMap<_Value> Parent;
220      explicit UEdgeMap(const UGraphAdaptorBase<Graph>& ga)
221        : Parent(*ga.graph) {}
222      UEdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
223        : Parent(*ga.graph, value) {}
224
225      UEdgeMap& operator=(const UEdgeMap& cmap) {
226        return operator=<UEdgeMap>(cmap);
227      }
228
229      template <typename CMap>
230      UEdgeMap& operator=(const CMap& cmap) {
231        Parent::operator=(cmap);
232        return *this;
233      }
234    };
235
236  };
237
238  /// \ingroup graph_adaptors
239  template <typename _UGraph>
240  class UGraphAdaptor
241    : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > {
242  public:
243    typedef _UGraph Graph;
244    typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;
245  protected:
246    UGraphAdaptor() : Parent() {}
247
248  public:
249    explicit UGraphAdaptor(Graph& _graph) { setGraph(_graph); }
250  };
251
252  template <typename _UGraph, typename NodeFilterMap,
253            typename UEdgeFilterMap, bool checked = true>
254  class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {
255  public:
256    typedef _UGraph Graph;
257    typedef SubUGraphAdaptorBase Adaptor;
258    typedef UGraphAdaptorBase<_UGraph> Parent;
259  protected:
260
261    NodeFilterMap* node_filter_map;
262    UEdgeFilterMap* uedge_filter_map;
263
264    SubUGraphAdaptorBase()
265      : Parent(), node_filter_map(0), uedge_filter_map(0) { }
266
267    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
268      node_filter_map=&_node_filter_map;
269    }
270    void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
271      uedge_filter_map=&_uedge_filter_map;
272    }
273
274  public:
275
276    typedef typename Parent::Node Node;
277    typedef typename Parent::Edge Edge;
278    typedef typename Parent::UEdge UEdge;
279
280    void first(Node& i) const {
281      Parent::first(i);
282      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
283    }
284
285    void first(Edge& i) const {
286      Parent::first(i);
287      while (i!=INVALID && (!(*uedge_filter_map)[i]
288             || !(*node_filter_map)[Parent::source(i)]
289             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
290    }
291
292    void first(UEdge& i) const {
293      Parent::first(i);
294      while (i!=INVALID && (!(*uedge_filter_map)[i]
295             || !(*node_filter_map)[Parent::source(i)]
296             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
297    }
298
299    void firstIn(Edge& i, const Node& n) const {
300      Parent::firstIn(i, n);
301      while (i!=INVALID && (!(*uedge_filter_map)[i]
302             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
303    }
304
305    void firstOut(Edge& i, const Node& n) const {
306      Parent::firstOut(i, n);
307      while (i!=INVALID && (!(*uedge_filter_map)[i]
308             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
309    }
310
311    void firstInc(UEdge& i, bool& d, const Node& n) const {
312      Parent::firstInc(i, d, n);
313      while (i!=INVALID && (!(*uedge_filter_map)[i]
314            || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d);
315    }
316
317    void next(Node& i) const {
318      Parent::next(i);
319      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
320    }
321
322    void next(Edge& i) const {
323      Parent::next(i);
324      while (i!=INVALID && (!(*uedge_filter_map)[i]
325             || !(*node_filter_map)[Parent::source(i)]
326             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
327    }
328
329    void next(UEdge& i) const {
330      Parent::next(i);
331      while (i!=INVALID && (!(*uedge_filter_map)[i]
332             || !(*node_filter_map)[Parent::source(i)]
333             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
334    }
335
336    void nextIn(Edge& i) const {
337      Parent::nextIn(i);
338      while (i!=INVALID && (!(*uedge_filter_map)[i]
339             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
340    }
341
342    void nextOut(Edge& i) const {
343      Parent::nextOut(i);
344      while (i!=INVALID && (!(*uedge_filter_map)[i]
345             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
346    }
347
348    void nextInc(UEdge& i, bool& d) const {
349      Parent::nextInc(i, d);
350      while (i!=INVALID && (!(*uedge_filter_map)[i]
351            || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d);
352    }
353
354    ///\e
355
356    /// This function hides \c n in the graph, i.e. the iteration
357    /// jumps over it. This is done by simply setting the value of \c n 
358    /// to be false in the corresponding node-map.
359    void hide(const Node& n) const { node_filter_map->set(n, false); }
360
361    ///\e
362
363    /// This function hides \c e in the graph, i.e. the iteration
364    /// jumps over it. This is done by simply setting the value of \c e 
365    /// to be false in the corresponding edge-map.
366    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
367
368    ///\e
369
370    /// The value of \c n is set to be true in the node-map which stores
371    /// hide information. If \c n was hidden previuosly, then it is shown
372    /// again
373     void unHide(const Node& n) const { node_filter_map->set(n, true); }
374
375    ///\e
376
377    /// The value of \c e is set to be true in the edge-map which stores
378    /// hide information. If \c e was hidden previuosly, then it is shown
379    /// again
380    void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
381
382    /// Returns true if \c n is hidden.
383   
384    ///\e
385    ///
386    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
387
388    /// Returns true if \c n is hidden.
389   
390    ///\e
391    ///
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& source, const Node& target,
399                  const Edge& prev = INVALID) {
400      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
401        return INVALID;
402      }
403      Edge edge = Parent::findEdge(source, target, prev);
404      while (edge != INVALID && !(*uedge_filter_map)[edge]) {
405        edge = Parent::findEdge(source, target, edge);
406      }
407      return edge;
408    }
409    UEdge findUEdge(const Node& source, const Node& target,
410                  const UEdge& prev = INVALID) {
411      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
412        return INVALID;
413      }
414      UEdge uedge = Parent::findUEdge(source, target, prev);
415      while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
416        uedge = Parent::findUEdge(source, target, 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& graph)
432        : Parent(graph) {}
433      NodeMap(const Graph& graph, const _Value& value)
434        : Parent(graph, value) {}
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& graph)
458        : Parent(graph) {}
459      EdgeMap(const Graph& graph, const _Value& value)
460        : Parent(graph, value) {}
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& graph)
484        : Parent(graph) {}
485      UEdgeMap(const Graph& graph, const _Value& value)
486        : Parent(graph, value) {}
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    ///\e
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    ///\e
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 edge-map.
595    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
596
597    ///\e
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    ///\e
605
606    /// The value of \c e is set to be true in the edge-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    /// Returns true if \c n is hidden.
612   
613    ///\e
614    ///
615    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
616
617    /// Returns true if \c n is hidden.
618   
619    ///\e
620    ///
621    bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
622
623    typedef False NodeNumTag;
624    typedef False EdgeNumTag;
625
626    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
627    Edge findEdge(const Node& source, const Node& target,
628                  const Edge& prev = INVALID) {
629      Edge edge = Parent::findEdge(source, target, prev);
630      while (edge != INVALID && !(*uedge_filter_map)[edge]) {
631        edge = Parent::findEdge(source, target, edge);
632      }
633      return edge;
634    }
635    UEdge findUEdge(const Node& source, const Node& target,
636                  const UEdge& prev = INVALID) {
637      UEdge uedge = Parent::findUEdge(source, target, prev);
638      while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
639        uedge = Parent::findUEdge(source, target, uedge);
640      }
641      return uedge;
642    }
643
644    template <typename _Value>
645    class NodeMap
646      : public SubMapExtender<Adaptor,
647                              typename Parent::template NodeMap<_Value> >
648    {
649    public:
650      typedef Adaptor Graph;
651      typedef SubMapExtender<Adaptor, typename Parent::
652                             template NodeMap<_Value> > Parent;
653   
654      NodeMap(const Graph& graph)
655        : Parent(graph) {}
656      NodeMap(const Graph& graph, const _Value& value)
657        : Parent(graph, value) {}
658   
659      NodeMap& operator=(const NodeMap& cmap) {
660        return operator=<NodeMap>(cmap);
661      }
662   
663      template <typename CMap>
664      NodeMap& operator=(const CMap& cmap) {
665        Parent::operator=(cmap);
666        return *this;
667      }
668    };
669
670    template <typename _Value>
671    class EdgeMap
672      : public SubMapExtender<Adaptor,
673                              typename Parent::template EdgeMap<_Value> >
674    {
675    public:
676      typedef Adaptor Graph;
677      typedef SubMapExtender<Adaptor, typename Parent::
678                             template EdgeMap<_Value> > Parent;
679   
680      EdgeMap(const Graph& graph)
681        : Parent(graph) {}
682      EdgeMap(const Graph& graph, const _Value& value)
683        : Parent(graph, value) {}
684   
685      EdgeMap& operator=(const EdgeMap& cmap) {
686        return operator=<EdgeMap>(cmap);
687      }
688   
689      template <typename CMap>
690      EdgeMap& operator=(const CMap& cmap) {
691        Parent::operator=(cmap);
692        return *this;
693      }
694    };
695
696    template <typename _Value>
697    class UEdgeMap
698      : public SubMapExtender<Adaptor,
699                              typename Parent::template UEdgeMap<_Value> >
700    {
701    public:
702      typedef Adaptor Graph;
703      typedef SubMapExtender<Adaptor, typename Parent::
704                             template UEdgeMap<_Value> > Parent;
705   
706      UEdgeMap(const Graph& graph)
707        : Parent(graph) {}
708      UEdgeMap(const Graph& graph, const _Value& value)
709        : Parent(graph, value) {}
710   
711      UEdgeMap& operator=(const UEdgeMap& cmap) {
712        return operator=<UEdgeMap>(cmap);
713      }
714   
715      template <typename CMap>
716      UEdgeMap& operator=(const CMap& cmap) {
717        Parent::operator=(cmap);
718        return *this;
719      }
720    };
721  };
722
723  /// \ingroup graph_adaptors
724  ///
725  /// \brief A graph adaptor for hiding nodes and edges from an undirected
726  /// graph.
727  ///
728  /// SubUGraphAdaptor shows the undirected graph with filtered node-set and
729  /// edge-set. If the \c checked parameter is true then it filters the edgeset
730  /// to do not get invalid edges without source or target.
731  ///
732  /// If the \c checked template parameter is false then we have to note that
733  /// the node-iterator cares only the filter on the node-set, and the
734  /// edge-iterator cares only the filter on the edge-set.
735  /// This way the edge-map
736  /// should filter all edges which's source or target is filtered by the
737  /// node-filter.
738  ///
739  /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
740  /// \c Graph::Node that is why \c g.id(n) can be applied.
741  ///
742  template<typename _UGraph, typename NodeFilterMap,
743           typename UEdgeFilterMap, bool checked = true>
744  class SubUGraphAdaptor :
745    public UGraphAdaptorExtender<
746    SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
747  public:
748    typedef _UGraph Graph;
749    typedef UGraphAdaptorExtender<
750      SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
751  protected:
752    SubUGraphAdaptor() { }
753  public:
754    SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,
755                    UEdgeFilterMap& _uedge_filter_map) {
756      setGraph(_graph);
757      setNodeFilterMap(_node_filter_map);
758      setUEdgeFilterMap(_uedge_filter_map);
759    }
760  };
761
762  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
763  SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
764  subUGraphAdaptor(const UGraph& graph,
765                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
766    return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
767      (graph, nfm, efm);
768  }
769
770  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
771  SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
772  subUGraphAdaptor(const UGraph& graph,
773                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
774    return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
775      (graph, nfm, efm);
776  }
777
778  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
779  SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
780  subUGraphAdaptor(const UGraph& graph,
781                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
782    return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
783      (graph, nfm, efm);
784  }
785
786  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
787  SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
788  subUGraphAdaptor(const UGraph& graph,
789                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
790    return SubUGraphAdaptor<const UGraph, const NodeFilterMap,
791      const EdgeFilterMap>(graph, nfm, efm);
792  }
793
794  /// \ingroup graph_adaptors
795  ///
796  /// \brief An adaptor for hiding nodes from an undirected graph.
797  ///
798  /// An adaptor for hiding nodes from an undirected graph.
799  /// This adaptor specializes SubUGraphAdaptor in the way that only
800  /// the node-set
801  /// can be filtered. In usual case the checked parameter is true, we get the
802  /// induced subgraph. But if the checked parameter is false then we can only
803  /// filter only isolated nodes.
804  template<typename _UGraph, typename NodeFilterMap, bool checked = true>
805  class NodeSubUGraphAdaptor :
806    public SubUGraphAdaptor<_UGraph, NodeFilterMap,
807                            ConstMap<typename _UGraph::UEdge, bool>, checked> {
808  public:
809    typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
810                             ConstMap<typename _UGraph::UEdge, bool> > Parent;
811    typedef _UGraph Graph;
812  protected:
813    ConstMap<typename _UGraph::UEdge, bool> const_true_map;
814
815    NodeSubUGraphAdaptor() : const_true_map(true) {
816      Parent::setUEdgeFilterMap(const_true_map);
817    }
818
819  public:
820    NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
821      Parent(), const_true_map(true) {
822      Parent::setGraph(_graph);
823      Parent::setNodeFilterMap(_node_filter_map);
824      Parent::setUEdgeFilterMap(const_true_map);
825    }
826  };
827
828  template<typename UGraph, typename NodeFilterMap>
829  NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
830  nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
831    return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
832  }
833
834  template<typename UGraph, typename NodeFilterMap>
835  NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
836  nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
837    return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
838  }
839
840  /// \brief An adaptor for hiding undirected edges from an undirected graph.
841  ///
842  /// \warning Graph adaptors are in even more experimental state
843  /// than the other parts of the lib. Use them at you own risk.
844  ///
845  /// An adaptor for hiding undirected edges from an undirected graph.
846  /// This adaptor specializes SubUGraphAdaptor in the way that
847  /// only the edge-set
848  /// can be filtered.
849  template<typename _UGraph, typename UEdgeFilterMap>
850  class EdgeSubUGraphAdaptor :
851    public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
852                            UEdgeFilterMap, false> {
853  public:
854    typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
855                             UEdgeFilterMap, false> Parent;
856    typedef _UGraph Graph;
857  protected:
858    ConstMap<typename Graph::Node, bool> const_true_map;
859
860    EdgeSubUGraphAdaptor() : const_true_map(true) {
861      Parent::setNodeFilterMap(const_true_map);
862    }
863
864  public:
865
866    EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
867      Parent(), const_true_map(true) {
868      Parent::setGraph(_graph);
869      Parent::setNodeFilterMap(const_true_map);
870      Parent::setUEdgeFilterMap(_uedge_filter_map);
871    }
872
873  };
874
875  template<typename UGraph, typename EdgeFilterMap>
876  EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
877  edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
878    return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
879  }
880
881  template<typename UGraph, typename EdgeFilterMap>
882  EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
883  edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
884    return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
885  }
886
887  template <typename _UGraph, typename _DirectionMap>
888  class DirUGraphAdaptorBase {
889  public:
890   
891    typedef _UGraph Graph;
892    typedef _DirectionMap DirectionMap;
893
894    typedef typename _UGraph::Node Node;
895    typedef typename _UGraph::UEdge Edge;
896   
897    void reverseEdge(const Edge& edge) {
898      direction->set(edge, !(*direction)[edge]);
899    }
900
901    void first(Node& i) const { graph->first(i); }
902    void first(Edge& i) const { graph->first(i); }
903    void firstIn(Edge& i, const Node& n) const {
904      bool d;
905      graph->firstInc(i, d, n);
906      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
907    }
908    void firstOut(Edge& i, const Node& n ) const {
909      bool d;
910      graph->firstInc(i, d, n);
911      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
912    }
913
914    void next(Node& i) const { graph->next(i); }
915    void next(Edge& i) const { graph->next(i); }
916    void nextIn(Edge& i) const {
917      bool d = !(*direction)[i];
918      graph->nextInc(i, d);
919      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
920    }
921    void nextOut(Edge& i) const {
922      bool d = (*direction)[i];
923      graph->nextInc(i, d);
924      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
925    }
926
927    Node source(const Edge& e) const {
928      return (*direction)[e] ? graph->source(e) : graph->target(e);
929    }
930    Node target(const Edge& e) const {
931      return (*direction)[e] ? graph->target(e) : graph->source(e);
932    }
933
934    typedef NodeNumTagIndicator<Graph> NodeNumTag;
935    int nodeNum() const { return graph->nodeNum(); }
936   
937    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
938    int edgeNum() const { return graph->uEdgeNum(); }
939
940    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
941    Edge findEdge(const Node& source, const Node& target,
942                  const Edge& prev = INVALID) {
943      Edge edge = prev;
944      bool d = edge == INVALID ? true : (*direction)[edge];
945      if (d) {
946        edge = graph->findUEdge(source, target, edge);
947        while (edge != INVALID && !(*direction)[edge]) {
948          graph->findUEdge(source, target, edge);
949        }
950        if (edge != INVALID) return edge;
951      }
952      graph->findUEdge(target, source, edge);
953      while (edge != INVALID && (*direction)[edge]) {
954        graph->findUEdge(source, target, edge);
955      }
956      return edge;
957    }
958 
959    Node addNode() const {
960      return Node(graph->addNode());
961    }
962
963    Edge addEdge(const Node& source, const Node& target) const {
964      Edge edge = graph->addEdge(source, target);
965      (*direction)[edge] = graph->source(edge) == source;
966      return edge;
967    }
968
969    void erase(const Node& i) const { graph->erase(i); }
970    void erase(const Edge& i) const { graph->erase(i); }
971 
972    void clear() const { graph->clear(); }
973   
974    int id(const Node& v) const { return graph->id(v); }
975    int id(const Edge& e) const { return graph->id(e); }
976
977    int maxNodeId() const {
978      return graph->maxNodeId();
979    }
980
981    int maxEdgeId() const {
982      return graph->maxEdgeId();
983    }
984
985    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
986
987    NodeNotifier& getNotifier(Node) const {
988      return graph->getNotifier(Node());
989    }
990
991    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
992
993    EdgeNotifier& getNotifier(Edge) const {
994      return graph->getNotifier(Edge());
995    }
996
997    template <typename _Value>
998    class NodeMap : public _UGraph::template NodeMap<_Value> {
999    public:
1000
1001      typedef typename _UGraph::template NodeMap<_Value> Parent;
1002
1003      explicit NodeMap(const DirUGraphAdaptorBase& ga)
1004        : Parent(*ga.graph) {}
1005
1006      NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
1007        : Parent(*ga.graph, value) {}
1008
1009      NodeMap& operator=(const NodeMap& cmap) {
1010        return operator=<NodeMap>(cmap);
1011      }
1012
1013      template <typename CMap>
1014      NodeMap& operator=(const CMap& cmap) {
1015        Parent::operator=(cmap);
1016        return *this;
1017      }
1018
1019    };
1020
1021    template <typename _Value>
1022    class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
1023    public:
1024
1025      typedef typename _UGraph::template UEdgeMap<_Value> Parent;
1026
1027      explicit EdgeMap(const DirUGraphAdaptorBase& ga)
1028        : Parent(*ga.graph) { }
1029
1030      EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
1031        : Parent(*ga.graph, value) { }
1032
1033      EdgeMap& operator=(const EdgeMap& cmap) {
1034        return operator=<EdgeMap>(cmap);
1035      }
1036
1037      template <typename CMap>
1038      EdgeMap& operator=(const CMap& cmap) {
1039        Parent::operator=(cmap);
1040        return *this;
1041      }
1042    };
1043
1044   
1045
1046  protected:
1047    Graph* graph;
1048    DirectionMap* direction;
1049
1050    void setDirectionMap(DirectionMap& _direction) {
1051      direction = &_direction;
1052    }
1053
1054    void setGraph(Graph& _graph) {
1055      graph = &_graph;
1056    }
1057
1058  };
1059
1060
1061  /// \ingroup graph_adaptors
1062  ///
1063  /// \brief A directed graph is made from an undirected graph by an adaptor
1064  ///
1065  /// This adaptor gives a direction for each uedge in the undirected graph.
1066  /// The direction of the edges stored in the DirectionMap. This map is
1067  /// a bool map on the undirected edges. If the uedge is mapped to true
1068  /// then the direction of the directed edge will be the same as the
1069  /// default direction of the uedge. The edges can be easily reverted
1070  /// by the reverseEdge member in the adaptor. 
1071  template<typename _Graph,
1072           typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
1073  class DirUGraphAdaptor :
1074    public GraphAdaptorExtender<
1075    DirUGraphAdaptorBase<_Graph, DirectionMap> > {
1076  public:
1077    typedef _Graph Graph;
1078    typedef GraphAdaptorExtender<
1079      DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1080  protected:
1081    DirUGraphAdaptor() { }
1082  public:
1083    DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
1084      setGraph(_graph);
1085      setDirectionMap(_direction_map);
1086    }
1087  };
1088
1089  template<typename UGraph, typename DirectionMap>
1090  DirUGraphAdaptor<const UGraph, DirectionMap>
1091  dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
1092    return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
1093  }
1094
1095  template<typename UGraph, typename DirectionMap>
1096  DirUGraphAdaptor<const UGraph, const DirectionMap>
1097  dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
1098    return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
1099  }
1100
1101}
1102
1103#endif
Note: See TracBrowser for help on using the repository browser.