COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/ugraph_adaptor.h @ 1991:d7442141d9ef

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

The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor?, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor? is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor?<UndirGraphAdaptor?<Graph>>.

The ResGraphAdaptor? is based on this composition.

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