COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/ugraph_adaptor.h @ 1979:c2992fd74dad

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

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

File size: 25.7 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  /// \warning Graph adaptors are in even more experimental state than the
515  /// other parts of the lib. Use them at you own risk.
516  ///
517  /// SubUGraphAdaptor shows the undirected graph with filtered node-set and
518  /// edge-set. If the \c checked parameter is true then it filters the edgeset
519  /// to do not get invalid edges without source or target.
520  ///
521  /// If the \c checked template parameter is false then we have to note that
522  /// the node-iterator cares only the filter on the node-set, and the
523  /// edge-iterator cares only the filter on the edge-set.
524  /// This way the edge-map
525  /// should filter all edges which's source or target is filtered by the
526  /// node-filter.
527  ///
528  /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
529  /// \c Graph::Node that is why \c g.id(n) can be applied.
530  ///
531  /// For examples see also the documentation of NodeSubUGraphAdaptor and
532  /// EdgeSubUGraphAdaptor.
533  ///
534  /// \author Marton Makai
535
536  template<typename _UGraph, typename NodeFilterMap,
537           typename UEdgeFilterMap, bool checked = true>
538  class SubUGraphAdaptor :
539    public UGraphAdaptorExtender<
540    SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
541  public:
542    typedef _UGraph Graph;
543    typedef UGraphAdaptorExtender<
544      SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
545  protected:
546    SubUGraphAdaptor() { }
547  public:
548    SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,
549                    UEdgeFilterMap& _uedge_filter_map) {
550      setGraph(_graph);
551      setNodeFilterMap(_node_filter_map);
552      setUEdgeFilterMap(_uedge_filter_map);
553    }
554  };
555
556  /// \ingroup graph_adaptors
557  ///
558  /// \brief An adaptor for hiding nodes from an undorected graph.
559  ///
560  /// \warning Graph adaptors are in even more experimental state
561  /// than the other
562  /// parts of the lib. Use them at you own risk.
563  ///
564  /// An adaptor for hiding nodes from an undirected graph.
565  /// This adaptor specializes SubUGraphAdaptor in the way that only
566  /// the node-set
567  /// can be filtered. In usual case the checked parameter is true, we get the
568  /// induced subgraph. But if the checked parameter is false then we can only
569  /// filter only isolated nodes.
570  /// \author Marton Makai
571  template<typename _UGraph, typename NodeFilterMap, bool checked = true>
572  class NodeSubUGraphAdaptor :
573    public SubUGraphAdaptor<_UGraph, NodeFilterMap,
574                            ConstMap<typename _UGraph::UEdge, bool>, checked> {
575  public:
576    typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
577                             ConstMap<typename _UGraph::UEdge, bool> > Parent;
578    typedef _UGraph Graph;
579  protected:
580    ConstMap<typename _UGraph::Edge, bool> const_true_map;
581  public:
582    NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
583      Parent(), const_true_map(true) {
584      Parent::setGraph(_graph);
585      Parent::setNodeFilterMap(_node_filter_map);
586      Parent::setUEdgeFilterMap(const_true_map);
587    }
588  };
589
590  template<typename UGraph, typename NodeFilterMap>
591  NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
592  nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
593    return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
594  }
595
596  template<typename UGraph, typename NodeFilterMap>
597  NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
598  nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
599    return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
600  }
601
602
603  /// \brief An adaptor for hiding undirected edges from an undirected graph.
604  ///
605  /// \warning Graph adaptors are in even more experimental state
606  /// than the other parts of the lib. Use them at you own risk.
607  ///
608  /// An adaptor for hiding undirected edges from an undirected graph.
609  /// This adaptor specializes SubUGraphAdaptor in the way that
610  /// only the edge-set
611  /// can be filtered.
612  ///
613  ///\author Marton Makai
614  template<typename _UGraph, typename UEdgeFilterMap>
615  class EdgeSubUGraphAdaptor :
616    public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
617                            UEdgeFilterMap, false> {
618  public:
619    typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
620                             UEdgeFilterMap, false> Parent;
621    typedef _UGraph Graph;
622  protected:
623    ConstMap<typename Graph::Node, bool> const_true_map;
624  public:
625    EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
626      Parent(), const_true_map(true) {
627      Parent::setGraph(_graph);
628      Parent::setNodeFilterMap(const_true_map);
629      Parent::setUEdgeFilterMap(_uedge_filter_map);
630    }
631  };
632
633  template<typename UGraph, typename EdgeFilterMap>
634  EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
635  edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
636    return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
637  }
638
639  template<typename UGraph, typename EdgeFilterMap>
640  EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
641  edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
642    return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
643  }
644
645  template <typename _UGraph, typename _DirectionMap>
646  class DirectUGraphAdaptorBase {
647  public:
648   
649    typedef _UGraph Graph;
650    typedef _DirectionMap DirectionMap;
651
652    typedef typename _UGraph::Node Node;
653    typedef typename _UGraph::UEdge Edge;
654   
655    void first(Node& i) const { graph->first(i); }
656    void first(Edge& i) const { graph->first(i); }
657    void firstIn(Edge& i, const Node& n) const {
658      bool d;
659      graph->firstInc(i, d, n);
660      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
661    }
662    void firstOut(Edge& i, const Node& n ) const {
663      bool d;
664      graph->firstInc(i, d, n);
665      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
666    }
667
668    void next(Node& i) const { graph->next(i); }
669    void next(Edge& i) const { graph->next(i); }
670    void nextIn(Edge& i) const {
671      bool d = !(*direction)[i];
672      graph->nextInc(i, d);
673      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
674    }
675    void nextOut(Edge& i) const {
676      bool d = (*direction)[i];
677      graph->nextInc(i, d);
678      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
679    }
680
681    Node source(const Edge& e) const {
682      return (*direction)[e] ? graph->source(e) : graph->target(e);
683    }
684    Node target(const Edge& e) const {
685      return (*direction)[e] ? graph->target(e) : graph->source(e);
686    }
687
688    typedef NodeNumTagIndicator<Graph> NodeNumTag;
689    int nodeNum() const { return graph->nodeNum(); }
690   
691    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
692    int edgeNum() const { return graph->uEdgeNum(); }
693
694    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
695    Edge findEdge(const Node& source, const Node& target,
696                  const Edge& prev = INVALID) {
697      Edge edge = prev;
698      bool d = edge == INVALID ? true : (*direction)[edge];
699      if (d) {
700        edge = graph->findUEdge(source, target, edge);
701        while (edge != INVALID && !(*direction)[edge]) {
702          graph->findUEdge(source, target, edge);
703        }
704        if (edge != INVALID) return edge;
705      }
706      graph->findUEdge(target, source, edge);
707      while (edge != INVALID && (*direction)[edge]) {
708        graph->findUEdge(source, target, edge);
709      }
710      return edge;
711    }
712 
713    Node addNode() const {
714      return Node(graph->addNode());
715    }
716
717    Edge addEdge(const Node& source, const Node& target) const {
718      Edge edge = graph->addEdge(source, target);
719      (*direction)[edge] = graph->source(edge) == source;
720      return edge;
721    }
722
723    void erase(const Node& i) const { graph->erase(i); }
724    void erase(const Edge& i) const { graph->erase(i); }
725 
726    void clear() const { graph->clear(); }
727   
728    int id(const Node& v) const { return graph->id(v); }
729    int id(const Edge& e) const { return graph->id(e); }
730
731    void reverseEdge(const Edge& edge) {
732      direction->set(edge, !(*direction)[edge]);
733    }
734
735    template <typename _Value>
736    class NodeMap : public _UGraph::template NodeMap<_Value> {
737    public:
738      typedef typename _UGraph::template NodeMap<_Value> Parent;
739      explicit NodeMap(const DirectUGraphAdaptorBase& ga)
740        : Parent(*ga.graph) { }
741      NodeMap(const DirectUGraphAdaptorBase& ga, const _Value& value)
742        : Parent(*ga.graph, value) { }
743    };
744
745    template <typename _Value>
746    class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
747    public:
748      typedef typename _UGraph::template EdgeMap<_Value> Parent;
749      explicit EdgeMap(const DirectUGraphAdaptorBase& ga)
750        : Parent(*ga.graph) { }
751      EdgeMap(const DirectUGraphAdaptorBase& ga, const _Value& value)
752        : Parent(*ga.graph, value) { }
753    };
754
755   
756
757  protected:
758    Graph* graph;
759    DirectionMap* direction;
760
761    void setDirectionMap(DirectionMap& _direction) {
762      direction = &_direction;
763    }
764
765    void setGraph(Graph& _graph) {
766      graph = &_graph;
767    }
768
769  };
770
771
772  template<typename _Graph, typename DirectionMap>
773  class DirectUGraphAdaptor :
774    public GraphAdaptorExtender<
775    DirectUGraphAdaptorBase<_Graph, DirectionMap> > {
776  public:
777    typedef _Graph Graph;
778    typedef GraphAdaptorExtender<
779      DirectUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
780  protected:
781    DirectUGraphAdaptor() { }
782  public:
783    DirectUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
784      setGraph(_graph);
785      setDirectionMap(_direction_map);
786    }
787  };
788
789  template<typename UGraph, typename DirectionMap>
790  DirectUGraphAdaptor<const UGraph, DirectionMap>
791  directUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
792    return DirectUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
793  }
794
795  template<typename UGraph, typename DirectionMap>
796  DirectUGraphAdaptor<const UGraph, const DirectionMap>
797  directUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
798    return DirectUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
799  }
800
801}
802
803#endif
Note: See TracBrowser for help on using the repository browser.