COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/ugraph_adaptor.h @ 2022:0f3367da6104

Last change on this file since 2022:0f3367da6104 was 1993:2115143eceea, checked in by Balazs Dezso, 18 years ago

utility, invalid and traits moved to bits

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/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
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.