COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/ugraph_adaptor.h @ 1980:a954b780e3ab

Last change on this file since 1980:a954b780e3ab was 1980:a954b780e3ab, checked in by Balazs Dezso, 14 years ago

Renaming to be convient to the naming of the adaptors
Concept checking of the ugraph adaptors

File size: 27.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/invalid.h>
31#include <lemon/maps.h>
32
33#include <lemon/bits/graph_adaptor_extender.h>
34
35#include <lemon/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  /// \warning Graph adaptors are in even more experimental state than the
46  /// other parts of the lib. Use them at you own risk.
47  ///
48  /// This is the base type for most of LEMON graph adaptors.
49  /// This class implements a trivial graph adaptor i.e. it only wraps the
50  /// functions and types of the graph. The purpose of this class is to
51  /// make easier implementing graph adaptors. E.g. if an adaptor is
52  /// considered which differs from the wrapped graph only in some of its
53  /// functions or types, then it can be derived from GraphAdaptor, and only
54  /// the differences should be implemented.
55  ///
56  /// \author Balazs Dezso
57  template<typename _UGraph>
58  class UGraphAdaptorBase {
59  public:
60    typedef _UGraph Graph;
61    typedef Graph ParentGraph;
62
63  protected:
64    Graph* graph;
65
66    UGraphAdaptorBase() : graph(0) {}
67
68    void setGraph(Graph& _graph) { graph=&_graph; }
69
70    Graph& getGraph() { return *graph; }
71    const Graph& getGraph() const { return *graph; }
72
73  public:
74    UGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
75 
76    typedef typename Graph::Node Node;
77    typedef typename Graph::Edge Edge;
78    typedef typename Graph::UEdge UEdge;
79   
80    void first(Node& i) const { graph->first(i); }
81    void first(Edge& i) const { graph->first(i); }
82    void first(UEdge& i) const { graph->first(i); }
83    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
84    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
85    void firstInc(UEdge &i, bool &d, const Node &n) const {
86      graph->firstInc(i, d, n);
87    }
88
89    void next(Node& i) const { graph->next(i); }
90    void next(Edge& i) const { graph->next(i); }
91    void next(UEdge& i) const { graph->next(i); }
92    void nextIn(Edge& i) const { graph->nextIn(i); }
93    void nextOut(Edge& i) const { graph->nextOut(i); }
94    void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
95
96
97    Node source(const UEdge& e) const { return graph->source(e); }
98    Node target(const UEdge& e) const { return graph->target(e); }
99
100    Node source(const Edge& e) const { return graph->source(e); }
101    Node target(const Edge& e) const { return graph->target(e); }
102
103    typedef NodeNumTagIndicator<Graph> NodeNumTag;
104    int nodeNum() const { return graph->nodeNum(); }
105   
106    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
107    int edgeNum() const { return graph->edgeNum(); }
108
109    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
110    Edge findEdge(const Node& source, const Node& target,
111                  const Edge& prev = INVALID) {
112      return graph->findEdge(source, target, prev);
113    }
114
115    UEdge findUEdge(const Node& source, const Node& target,
116                    const UEdge& prev = INVALID) {
117      return graph->findUEdge(source, target, prev);
118    }
119 
120    Node addNode() const { return graph->addNode(); }
121    UEdge addEdge(const Node& source, const Node& target) const {
122      return graph->addEdge(source, target);
123    }
124
125    void erase(const Node& i) const { graph->erase(i); }
126    void erase(const Edge& i) const { graph->erase(i); }
127 
128    void clear() const { graph->clear(); }
129   
130    int id(const Node& v) const { return graph->id(v); }
131    int id(const UEdge& e) const { return graph->id(e); }
132
133    bool direction(const Edge& e) const { return graph->direction(e); }
134    Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
135    Edge direct(const UEdge& e, const Node& n) const {
136      return graph->direct(e, n);
137    }
138
139    Node oppositeNode(const Node& n, const Edge& e) const {
140      return graph->oppositeNode(n, e);
141    }
142
143    Edge oppositeEdge(const Edge& e) const {
144      return graph->oppositeEdge(e);
145    }
146
147
148    template <typename _Value>
149    class NodeMap : public Graph::template NodeMap<_Value> {
150    public:
151      typedef typename Graph::template NodeMap<_Value> Parent;
152      explicit NodeMap(const UGraphAdaptorBase<Graph>& ga)
153        : Parent(*ga.graph) {}
154      NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
155        : Parent(*ga.graph, value) {}
156
157      NodeMap& operator=(const NodeMap& cmap) {
158        return operator=<NodeMap>(cmap);
159      }
160
161      template <typename CMap>
162      NodeMap& operator=(const CMap& cmap) {
163        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
164        const typename Parent::Graph* graph = Parent::getGraph();
165        Node it;
166        for (graph->first(it); it != INVALID; graph->next(it)) {
167          Parent::set(it, cmap[it]);
168        }
169        return *this;
170      }
171    };
172
173    template <typename _Value>
174    class EdgeMap : public Graph::template EdgeMap<_Value> {
175    public:
176      typedef typename Graph::template EdgeMap<_Value> Parent;
177      explicit EdgeMap(const UGraphAdaptorBase<Graph>& ga)
178        : Parent(*ga.graph) {}
179      EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
180        : Parent(*ga.graph, value) {}
181
182      EdgeMap& operator=(const EdgeMap& cmap) {
183        return operator=<EdgeMap>(cmap);
184      }
185
186      template <typename CMap>
187      EdgeMap& operator=(const CMap& cmap) {
188        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
189        const typename Parent::Graph* graph = Parent::getGraph();
190        Edge it;
191        for (graph->first(it); it != INVALID; graph->next(it)) {
192          Parent::set(it, cmap[it]);
193        }
194        return *this;
195      }
196    };
197
198    template <typename _Value>
199    class UEdgeMap : public Graph::template UEdgeMap<_Value> {
200    public:
201      typedef typename Graph::template UEdgeMap<_Value> Parent;
202      explicit UEdgeMap(const UGraphAdaptorBase<Graph>& ga)
203        : Parent(*ga.graph) {}
204      UEdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
205        : Parent(*ga.graph, value) {}
206
207      UEdgeMap& operator=(const UEdgeMap& cmap) {
208        return operator=<UEdgeMap>(cmap);
209      }
210
211      template <typename CMap>
212      UEdgeMap& operator=(const CMap& cmap) {
213        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
214        const typename Parent::Graph* graph = Parent::getGraph();
215        UEdge it;
216        for (graph->first(it); it != INVALID; graph->next(it)) {
217          Parent::set(it, cmap[it]);
218        }
219        return *this;
220      }
221    };
222
223  };
224
225  /// \ingroup graph_adaptors
226  template <typename _UGraph>
227  class UGraphAdaptor
228    : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > {
229  public:
230    typedef _UGraph Graph;
231    typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;
232  protected:
233    UGraphAdaptor() : Parent() {}
234
235  public:
236    explicit UGraphAdaptor(Graph& _graph) { setGraph(_graph); }
237  };
238
239  template <typename _UGraph, typename NodeFilterMap,
240            typename UEdgeFilterMap, bool checked = true>
241  class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {
242  public:
243    typedef _UGraph Graph;
244    typedef UGraphAdaptorBase<_UGraph> Parent;
245  protected:
246
247    NodeFilterMap* node_filter_map;
248    UEdgeFilterMap* uedge_filter_map;
249
250    SubUGraphAdaptorBase()
251      : Parent(), node_filter_map(0), uedge_filter_map(0) { }
252
253    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
254      node_filter_map=&_node_filter_map;
255    }
256    void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
257      uedge_filter_map=&_uedge_filter_map;
258    }
259
260  public:
261
262    typedef typename Parent::Node Node;
263    typedef typename Parent::Edge Edge;
264    typedef typename Parent::UEdge UEdge;
265
266    void first(Node& i) const {
267      Parent::first(i);
268      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
269    }
270
271    void first(Edge& i) const {
272      Parent::first(i);
273      while (i!=INVALID && (!(*uedge_filter_map)[i]
274             || !(*node_filter_map)[Parent::source(i)]
275             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
276    }
277
278    void first(UEdge& i) const {
279      Parent::first(i);
280      while (i!=INVALID && (!(*uedge_filter_map)[i]
281             || !(*node_filter_map)[Parent::source(i)]
282             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
283    }
284
285    void firstIn(Edge& i, const Node& n) const {
286      Parent::firstIn(i, n);
287      while (i!=INVALID && (!(*uedge_filter_map)[i]
288             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
289    }
290
291    void firstOut(Edge& i, const Node& n) const {
292      Parent::firstOut(i, n);
293      while (i!=INVALID && (!(*uedge_filter_map)[i]
294             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
295    }
296
297    void firstInc(UEdge& i, bool& d, const Node& n) const {
298      Parent::firstInc(i, d, n);
299      while (i!=INVALID && (!(*uedge_filter_map)[i]
300            || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d);
301    }
302
303    void next(Node& i) const {
304      Parent::next(i);
305      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
306    }
307
308    void next(Edge& i) const {
309      Parent::next(i);
310      while (i!=INVALID && (!(*uedge_filter_map)[i]
311             || !(*node_filter_map)[Parent::source(i)]
312             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
313    }
314
315    void next(UEdge& i) const {
316      Parent::next(i);
317      while (i!=INVALID && (!(*uedge_filter_map)[i]
318             || !(*node_filter_map)[Parent::source(i)]
319             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
320    }
321
322    void nextIn(Edge& i) const {
323      Parent::nextIn(i);
324      while (i!=INVALID && (!(*uedge_filter_map)[i]
325             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
326    }
327
328    void nextOut(Edge& i) const {
329      Parent::nextOut(i);
330      while (i!=INVALID && (!(*uedge_filter_map)[i]
331             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
332    }
333
334    void nextInc(UEdge& i, bool& d) const {
335      Parent::nextInc(i, d);
336      while (i!=INVALID && (!(*uedge_filter_map)[i]
337            || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d);
338    }
339
340    ///\e
341
342    /// This function hides \c n in the graph, i.e. the iteration
343    /// jumps over it. This is done by simply setting the value of \c n 
344    /// to be false in the corresponding node-map.
345    void hide(const Node& n) const { node_filter_map->set(n, false); }
346
347    ///\e
348
349    /// This function hides \c e in the graph, i.e. the iteration
350    /// jumps over it. This is done by simply setting the value of \c e 
351    /// to be false in the corresponding edge-map.
352    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
353
354    ///\e
355
356    /// The value of \c n is set to be true in the node-map which stores
357    /// hide information. If \c n was hidden previuosly, then it is shown
358    /// again
359     void unHide(const Node& n) const { node_filter_map->set(n, true); }
360
361    ///\e
362
363    /// The value of \c e is set to be true in the edge-map which stores
364    /// hide information. If \c e was hidden previuosly, then it is shown
365    /// again
366    void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
367
368    /// Returns true if \c n is hidden.
369   
370    ///\e
371    ///
372    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
373
374    /// Returns true if \c n is hidden.
375   
376    ///\e
377    ///
378    bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
379
380    typedef False NodeNumTag;
381    typedef False EdgeNumTag;
382  };
383
384  template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
385  class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false>
386    : public UGraphAdaptorBase<_UGraph> {
387  public:
388    typedef _UGraph Graph;
389    typedef UGraphAdaptorBase<_UGraph> Parent;
390  protected:
391    NodeFilterMap* node_filter_map;
392    UEdgeFilterMap* uedge_filter_map;
393    SubUGraphAdaptorBase() : Parent(),
394                            node_filter_map(0), uedge_filter_map(0) { }
395
396    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
397      node_filter_map=&_node_filter_map;
398    }
399    void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
400      uedge_filter_map=&_uedge_filter_map;
401    }
402
403  public:
404
405    typedef typename Parent::Node Node;
406    typedef typename Parent::Edge Edge;
407    typedef typename Parent::UEdge UEdge;
408
409    void first(Node& i) const {
410      Parent::first(i);
411      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
412    }
413
414    void first(Edge& i) const {
415      Parent::first(i);
416      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
417    }
418
419    void first(UEdge& i) const {
420      Parent::first(i);
421      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
422    }
423
424    void firstIn(Edge& i, const Node& n) const {
425      Parent::firstIn(i, n);
426      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
427    }
428
429    void firstOut(Edge& i, const Node& n) const {
430      Parent::firstOut(i, n);
431      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
432    }
433
434    void firstInc(UEdge& i, bool& d, const Node& n) const {
435      Parent::firstInc(i, d, n);
436      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
437    }
438
439    void next(Node& i) const {
440      Parent::next(i);
441      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
442    }
443    void next(Edge& i) const {
444      Parent::next(i);
445      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
446    }
447    void next(UEdge& i) const {
448      Parent::next(i);
449      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
450    }
451    void nextIn(Edge& i) const {
452      Parent::nextIn(i);
453      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
454    }
455
456    void nextOut(Edge& i) const {
457      Parent::nextOut(i);
458      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
459    }
460    void nextInc(UEdge& i, bool& d) const {
461      Parent::nextInc(i, d);
462      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
463    }
464
465    ///\e
466
467    /// This function hides \c n in the graph, i.e. the iteration
468    /// jumps over it. This is done by simply setting the value of \c n 
469    /// to be false in the corresponding node-map.
470    void hide(const Node& n) const { node_filter_map->set(n, false); }
471
472    ///\e
473
474    /// This function hides \c e in the graph, i.e. the iteration
475    /// jumps over it. This is done by simply setting the value of \c e 
476    /// to be false in the corresponding edge-map.
477    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
478
479    ///\e
480
481    /// The value of \c n is set to be true in the node-map which stores
482    /// hide information. If \c n was hidden previuosly, then it is shown
483    /// again
484     void unHide(const Node& n) const { node_filter_map->set(n, true); }
485
486    ///\e
487
488    /// The value of \c e is set to be true in the edge-map which stores
489    /// hide information. If \c e was hidden previuosly, then it is shown
490    /// again
491    void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
492
493    /// Returns true if \c n is hidden.
494   
495    ///\e
496    ///
497    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
498
499    /// Returns true if \c n is hidden.
500   
501    ///\e
502    ///
503    bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
504
505    typedef False NodeNumTag;
506    typedef False EdgeNumTag;
507  };
508
509  /// \ingroup graph_adaptors
510  ///
511  /// \brief A graph adaptor for hiding nodes and edges from an undirected
512  /// graph.
513  ///
514  /// SubUGraphAdaptor shows the undirected graph with filtered node-set and
515  /// edge-set. If the \c checked parameter is true then it filters the edgeset
516  /// to do not get invalid edges without source or target.
517  ///
518  /// If the \c checked template parameter is false then we have to note that
519  /// the node-iterator cares only the filter on the node-set, and the
520  /// edge-iterator cares only the filter on the edge-set.
521  /// This way the edge-map
522  /// should filter all edges which's source or target is filtered by the
523  /// node-filter.
524  ///
525  /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
526  /// \c Graph::Node that is why \c g.id(n) can be applied.
527  ///
528  template<typename _UGraph, typename NodeFilterMap,
529           typename UEdgeFilterMap, bool checked = true>
530  class SubUGraphAdaptor :
531    public UGraphAdaptorExtender<
532    SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
533  public:
534    typedef _UGraph Graph;
535    typedef UGraphAdaptorExtender<
536      SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
537  protected:
538    SubUGraphAdaptor() { }
539  public:
540    SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,
541                    UEdgeFilterMap& _uedge_filter_map) {
542      setGraph(_graph);
543      setNodeFilterMap(_node_filter_map);
544      setUEdgeFilterMap(_uedge_filter_map);
545    }
546  };
547
548  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
549  SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
550  subUGraphAdaptor(const UGraph& graph,
551                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
552    return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
553      (graph, nfm, efm);
554  }
555
556  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
557  SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
558  subUGraphAdaptor(const UGraph& graph,
559                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
560    return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
561      (graph, nfm, efm);
562  }
563
564  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
565  SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
566  subUGraphAdaptor(const UGraph& graph,
567                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
568    return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
569      (graph, nfm, efm);
570  }
571
572  template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
573  SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
574  subUGraphAdaptor(const UGraph& graph,
575                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
576    return SubUGraphAdaptor<const UGraph, const NodeFilterMap,
577      const EdgeFilterMap>(graph, nfm, efm);
578  }
579
580  /// \ingroup graph_adaptors
581  ///
582  /// \brief An adaptor for hiding nodes from an undirected graph.
583  ///
584  ///
585  /// An adaptor for hiding nodes from an undirected graph.
586  /// This adaptor specializes SubUGraphAdaptor in the way that only
587  /// the node-set
588  /// can be filtered. In usual case the checked parameter is true, we get the
589  /// induced subgraph. But if the checked parameter is false then we can only
590  /// filter only isolated nodes.
591  template<typename _UGraph, typename NodeFilterMap, bool checked = true>
592  class NodeSubUGraphAdaptor :
593    public SubUGraphAdaptor<_UGraph, NodeFilterMap,
594                            ConstMap<typename _UGraph::UEdge, bool>, checked> {
595  public:
596    typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
597                             ConstMap<typename _UGraph::UEdge, bool> > Parent;
598    typedef _UGraph Graph;
599  protected:
600    ConstMap<typename _UGraph::Edge, bool> const_true_map;
601  public:
602    NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
603      Parent(), const_true_map(true) {
604      Parent::setGraph(_graph);
605      Parent::setNodeFilterMap(_node_filter_map);
606      Parent::setUEdgeFilterMap(const_true_map);
607    }
608  };
609
610  template<typename UGraph, typename NodeFilterMap>
611  NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
612  nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
613    return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
614  }
615
616  template<typename UGraph, typename NodeFilterMap>
617  NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
618  nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
619    return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
620  }
621
622
623  /// \brief An adaptor for hiding undirected edges from an undirected graph.
624  ///
625  /// \warning Graph adaptors are in even more experimental state
626  /// than the other parts of the lib. Use them at you own risk.
627  ///
628  /// An adaptor for hiding undirected edges from an undirected graph.
629  /// This adaptor specializes SubUGraphAdaptor in the way that
630  /// only the edge-set
631  /// can be filtered.
632  template<typename _UGraph, typename UEdgeFilterMap>
633  class EdgeSubUGraphAdaptor :
634    public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
635                            UEdgeFilterMap, false> {
636  public:
637    typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
638                             UEdgeFilterMap, false> Parent;
639    typedef _UGraph Graph;
640  protected:
641    ConstMap<typename Graph::Node, bool> const_true_map;
642  public:
643    EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
644      Parent(), const_true_map(true) {
645      Parent::setGraph(_graph);
646      Parent::setNodeFilterMap(const_true_map);
647      Parent::setUEdgeFilterMap(_uedge_filter_map);
648    }
649  };
650
651  template<typename UGraph, typename EdgeFilterMap>
652  EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
653  edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
654    return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
655  }
656
657  template<typename UGraph, typename EdgeFilterMap>
658  EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
659  edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
660    return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
661  }
662
663  template <typename _UGraph, typename _DirectionMap>
664  class DirUGraphAdaptorBase {
665  public:
666   
667    typedef _UGraph Graph;
668    typedef _DirectionMap DirectionMap;
669
670    typedef typename _UGraph::Node Node;
671    typedef typename _UGraph::UEdge Edge;
672   
673    void first(Node& i) const { graph->first(i); }
674    void first(Edge& i) const { graph->first(i); }
675    void firstIn(Edge& i, const Node& n) const {
676      bool d;
677      graph->firstInc(i, d, n);
678      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
679    }
680    void firstOut(Edge& i, const Node& n ) const {
681      bool d;
682      graph->firstInc(i, d, n);
683      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
684    }
685
686    void next(Node& i) const { graph->next(i); }
687    void next(Edge& i) const { graph->next(i); }
688    void nextIn(Edge& i) const {
689      bool d = !(*direction)[i];
690      graph->nextInc(i, d);
691      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
692    }
693    void nextOut(Edge& i) const {
694      bool d = (*direction)[i];
695      graph->nextInc(i, d);
696      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
697    }
698
699    Node source(const Edge& e) const {
700      return (*direction)[e] ? graph->source(e) : graph->target(e);
701    }
702    Node target(const Edge& e) const {
703      return (*direction)[e] ? graph->target(e) : graph->source(e);
704    }
705
706    typedef NodeNumTagIndicator<Graph> NodeNumTag;
707    int nodeNum() const { return graph->nodeNum(); }
708   
709    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
710    int edgeNum() const { return graph->uEdgeNum(); }
711
712    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
713    Edge findEdge(const Node& source, const Node& target,
714                  const Edge& prev = INVALID) {
715      Edge edge = prev;
716      bool d = edge == INVALID ? true : (*direction)[edge];
717      if (d) {
718        edge = graph->findUEdge(source, target, edge);
719        while (edge != INVALID && !(*direction)[edge]) {
720          graph->findUEdge(source, target, edge);
721        }
722        if (edge != INVALID) return edge;
723      }
724      graph->findUEdge(target, source, edge);
725      while (edge != INVALID && (*direction)[edge]) {
726        graph->findUEdge(source, target, edge);
727      }
728      return edge;
729    }
730 
731    Node addNode() const {
732      return Node(graph->addNode());
733    }
734
735    Edge addEdge(const Node& source, const Node& target) const {
736      Edge edge = graph->addEdge(source, target);
737      (*direction)[edge] = graph->source(edge) == source;
738      return edge;
739    }
740
741    void erase(const Node& i) const { graph->erase(i); }
742    void erase(const Edge& i) const { graph->erase(i); }
743 
744    void clear() const { graph->clear(); }
745   
746    int id(const Node& v) const { return graph->id(v); }
747    int id(const Edge& e) const { return graph->id(e); }
748
749    void reverseEdge(const Edge& edge) {
750      direction->set(edge, !(*direction)[edge]);
751    }
752
753    template <typename _Value>
754    class NodeMap : public _UGraph::template NodeMap<_Value> {
755    public:
756      typedef typename _UGraph::template NodeMap<_Value> Parent;
757      explicit NodeMap(const DirUGraphAdaptorBase& ga)
758        : Parent(*ga.graph) { }
759      NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
760        : Parent(*ga.graph, value) { }
761    };
762
763    template <typename _Value>
764    class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
765    public:
766      typedef typename _UGraph::template UEdgeMap<_Value> Parent;
767      explicit EdgeMap(const DirUGraphAdaptorBase& ga)
768        : Parent(*ga.graph) { }
769      EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
770        : Parent(*ga.graph, value) { }
771    };
772
773   
774
775  protected:
776    Graph* graph;
777    DirectionMap* direction;
778
779    void setDirectionMap(DirectionMap& _direction) {
780      direction = &_direction;
781    }
782
783    void setGraph(Graph& _graph) {
784      graph = &_graph;
785    }
786
787  };
788
789
790  /// \ingroup graph_adaptors
791  /// \brief A directed graph is made from a undirected graph by an adaptor
792  ///
793  /// This adaptor gives a direction for each uedge in the undirected graph.
794  /// The direction of the edges stored in the DirectionMap. This map is
795  /// a bool map on the undirected edges. If the uedge is mapped to true
796  /// then the direction of the directed edge will be the same as the
797  /// default direction of the uedge. The edges can be easily reverted
798  /// by the reverseEdge member in the adaptor. 
799  template<typename _Graph,
800           typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
801  class DirUGraphAdaptor :
802    public GraphAdaptorExtender<
803    DirUGraphAdaptorBase<_Graph, DirectionMap> > {
804  public:
805    typedef _Graph Graph;
806    typedef GraphAdaptorExtender<
807      DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
808  protected:
809    DirUGraphAdaptor() { }
810  public:
811    DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
812      setGraph(_graph);
813      setDirectionMap(_direction_map);
814    }
815  };
816
817  template<typename UGraph, typename DirectionMap>
818  DirUGraphAdaptor<const UGraph, DirectionMap>
819  dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
820    return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
821  }
822
823  template<typename UGraph, typename DirectionMap>
824  DirUGraphAdaptor<const UGraph, const DirectionMap>
825  dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
826    return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
827  }
828
829}
830
831#endif
Note: See TracBrowser for help on using the repository browser.