A new implementation of UndirGraphWrapper, accordig to the undirected concepts
authormarci
Sat, 23 Apr 2005 16:59:49 +0000
changeset 138379b68a337f9f
parent 1382 2c925c18d130
child 1384 0c4091eeda15
A new implementation of UndirGraphWrapper, accordig to the undirected concepts
src/lemon/graph_wrapper.h
src/test/graph_wrapper_test.cc
     1.1 --- a/src/lemon/graph_wrapper.h	Fri Apr 22 17:53:26 2005 +0000
     1.2 +++ b/src/lemon/graph_wrapper.h	Sat Apr 23 16:59:49 2005 +0000
     1.3 @@ -28,6 +28,7 @@
     1.4  #include <lemon/invalid.h>
     1.5  #include <lemon/maps.h>
     1.6  #include <lemon/bits/iterable_graph_extender.h>
     1.7 +#include <lemon/bits/undir_graph_extender.h>
     1.8  #include <iostream>
     1.9  
    1.10  namespace lemon {
    1.11 @@ -151,11 +152,11 @@
    1.12      typedef typename Parent::Node Node;
    1.13      typedef typename Parent::Edge Edge;
    1.14  
    1.15 -    using Parent::first;
    1.16 +    //    using Parent::first;
    1.17      void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
    1.18      void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
    1.19  
    1.20 -    using Parent::next;
    1.21 +    //    using Parent::next;
    1.22      void nextIn(Edge& i) const { Parent::nextOut(i); }
    1.23      void nextOut(Edge& i) const { Parent::nextIn(i); }
    1.24  
    1.25 @@ -565,91 +566,97 @@
    1.26      }
    1.27    };
    1.28  
    1.29 +  template <typename _Graph>
    1.30 +  class UndirGraphWrapperBase : 
    1.31 +    public UndirGraphExtender<GraphWrapperBase<_Graph> > {
    1.32 +  public:
    1.33 +    typedef _Graph Graph;
    1.34 +    typedef UndirGraphExtender<GraphWrapperBase<_Graph> > Parent;
    1.35 +  protected:
    1.36 +    UndirGraphWrapperBase() : Parent() { }
    1.37 +  public:
    1.38 +    typedef typename Parent::UndirEdge UndirEdge;
    1.39 +    typedef typename Parent::Edge Edge;
    1.40 +    
    1.41 +    /// \bug Why cant an edge say that it is forward or not??? 
    1.42 +    /// By this, a pointer to the graph have to be stored
    1.43 +    /// The implementation
    1.44 +    template <typename T>
    1.45 +    class EdgeMap {
    1.46 +    protected:
    1.47 +      const UndirGraphWrapperBase<_Graph>* g;
    1.48 +      template <typename TT> friend class EdgeMap;
    1.49 +      typename _Graph::template EdgeMap<T> forward_map, backward_map; 
    1.50 +    public:
    1.51 +      typedef T Value;
    1.52 +      typedef Edge Key;
    1.53 +      
    1.54 +      EdgeMap(const UndirGraphWrapperBase<_Graph>& _g) : g(&_g), 
    1.55 +	forward_map(*(g->graph)), backward_map(*(g->graph)) { }
    1.56  
    1.57 -  template<typename Graph>
    1.58 -  class UndirGraphWrapper : public GraphWrapper<Graph> {
    1.59 -  public:
    1.60 -    typedef GraphWrapper<Graph> Parent; 
    1.61 -  protected:
    1.62 -    UndirGraphWrapper() : GraphWrapper<Graph>() { }
    1.63 -    
    1.64 -  public:
    1.65 -    typedef typename GraphWrapper<Graph>::Node Node;
    1.66 -    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    1.67 -    typedef typename GraphWrapper<Graph>::Edge Edge;
    1.68 -    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
    1.69 +      EdgeMap(const UndirGraphWrapperBase<_Graph>& _g, T a) : g(&_g), 
    1.70 +	forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
    1.71 +      
    1.72 +      void set(Edge e, T a) { 
    1.73 +	if (g->forward(e)) 
    1.74 +	  forward_map.set(e, a); 
    1.75 +	else 
    1.76 +	  backward_map.set(e, a); 
    1.77 +      }
    1.78  
    1.79 -    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
    1.80 -
    1.81 -    class OutEdgeIt {
    1.82 -      friend class UndirGraphWrapper<Graph>;
    1.83 -      bool out_or_in; //true iff out
    1.84 -      typename Graph::OutEdgeIt out;
    1.85 -      typename Graph::InEdgeIt in;
    1.86 -    public:
    1.87 -      OutEdgeIt() { }
    1.88 -      OutEdgeIt(const Invalid& i) : Edge(i) { }
    1.89 -      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
    1.90 -	out_or_in=true; _G.graph->first(out, _n);
    1.91 -	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);	}
    1.92 -      } 
    1.93 -      operator Edge() const { 
    1.94 -	if (out_or_in) return Edge(out); else return Edge(in); 
    1.95 +      T operator[](Edge e) const { 
    1.96 +	if (g->forward(e)) 
    1.97 +	  return forward_map[e]; 
    1.98 +	else 
    1.99 +	  return backward_map[e]; 
   1.100        }
   1.101      };
   1.102 +        
   1.103 +    template <typename T>
   1.104 +    class UndirEdgeMap {
   1.105 +      template <typename TT> friend class UndirEdgeMap;
   1.106 +      typename _Graph::template EdgeMap<T> map; 
   1.107 +    public:
   1.108 +      typedef T Value;
   1.109 +      typedef UndirEdge Key;
   1.110 +      
   1.111 +      UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g) : 
   1.112 +	map(*(g.graph)) { }
   1.113  
   1.114 -    typedef OutEdgeIt InEdgeIt; 
   1.115 +      UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g, T a) : 
   1.116 +	map(*(g.graph), a) { }
   1.117 +      
   1.118 +      void set(UndirEdge e, T a) { 
   1.119 +	map.set(e, a); 
   1.120 +      }
   1.121  
   1.122 -    using GraphWrapper<Graph>::first;
   1.123 -    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   1.124 -      i=OutEdgeIt(*this, p); return i;
   1.125 +      T operator[](UndirEdge e) const { 
   1.126 +	return map[e]; 
   1.127 +      }
   1.128 +    };
   1.129 +      
   1.130 +  };
   1.131 +
   1.132 +  /// \brief An undirected graph is made from a directed graph by a wrapper
   1.133 +  ///
   1.134 +  /// Undocumented, untested!!!
   1.135 +  /// If somebody knows nice demo application, let's polulate it.
   1.136 +  /// 
   1.137 +  /// \author Marton Makai
   1.138 +  template<typename _Graph>
   1.139 +  class UndirGraphWrapper : 
   1.140 +    public IterableUndirGraphExtender<
   1.141 +    UndirGraphWrapperBase<_Graph> > {
   1.142 +  public:
   1.143 +    typedef _Graph Graph;
   1.144 +    typedef IterableUndirGraphExtender<
   1.145 +      UndirGraphWrapperBase<_Graph> > Parent;
   1.146 +  protected:
   1.147 +    UndirGraphWrapper() { }
   1.148 +  public:
   1.149 +    UndirGraphWrapper(_Graph& _graph) { 
   1.150 +      setGraph(_graph);
   1.151      }
   1.152 -
   1.153 -    using GraphWrapper<Graph>::next;
   1.154 -
   1.155 -    OutEdgeIt& next(OutEdgeIt& e) const {
   1.156 -      if (e.out_or_in) {
   1.157 -	typename Graph::Node n=this->graph->source(e.out);
   1.158 -	this->graph->next(e.out);
   1.159 -	if (!this->graph->valid(e.out)) { 
   1.160 -	  e.out_or_in=false; this->graph->first(e.in, n); }
   1.161 -      } else {
   1.162 -	this->graph->next(e.in);
   1.163 -      }
   1.164 -      return e;
   1.165 -    }
   1.166 -
   1.167 -    Node aNode(const OutEdgeIt& e) const { 
   1.168 -      if (e.out_or_in) return this->graph->source(e); else 
   1.169 -	return this->graph->target(e); }
   1.170 -    Node bNode(const OutEdgeIt& e) const { 
   1.171 -      if (e.out_or_in) return this->graph->target(e); else 
   1.172 -	return this->graph->source(e); }
   1.173 -
   1.174 -    //    KEEP_MAPS(Parent, UndirGraphWrapper);
   1.175 -
   1.176 -  };
   1.177 -  
   1.178 -//   /// \brief An undirected graph template.
   1.179 -//   ///
   1.180 -//   ///\warning Graph wrappers are in even more experimental state than the other
   1.181 -//   ///parts of the lib. Use them at your own risk.
   1.182 -//   ///
   1.183 -//   /// An undirected graph template.
   1.184 -//   /// This class works as an undirected graph and a directed graph of 
   1.185 -//   /// class \c Graph is used for the physical storage.
   1.186 -//   /// \ingroup graphs
   1.187 -  template<typename Graph>
   1.188 -  class UndirGraph : public UndirGraphWrapper<Graph> {
   1.189 -    typedef UndirGraphWrapper<Graph> Parent;
   1.190 -  protected:
   1.191 -    Graph gr;
   1.192 -  public:
   1.193 -    UndirGraph() : UndirGraphWrapper<Graph>() { 
   1.194 -      Parent::setGraph(gr); 
   1.195 -    }
   1.196 -
   1.197 -    //    KEEP_MAPS(Parent, UndirGraph);
   1.198    };
   1.199  
   1.200    
     2.1 --- a/src/test/graph_wrapper_test.cc	Fri Apr 22 17:53:26 2005 +0000
     2.2 +++ b/src/test/graph_wrapper_test.cc	Sat Apr 23 16:59:49 2005 +0000
     2.3 @@ -19,6 +19,7 @@
     2.4  
     2.5  #include<lemon/smart_graph.h>
     2.6  #include<lemon/concept/graph.h>
     2.7 +#include<lemon/concept/undir_graph.h>
     2.8  
     2.9  #include<lemon/list_graph.h>
    2.10  #include<lemon/full_graph.h>
    2.11 @@ -62,6 +63,11 @@
    2.12  
    2.13      checkConcept<StaticGraph, ErasingFirstGraphWrapper<Graph, 
    2.14        Graph::NodeMap<Graph::Edge> > >(); 
    2.15 +
    2.16 +    /// \bug why does not compile with StaticGraph
    2.17 +    checkConcept<BaseIterableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
    2.18 +    checkConcept<IterableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
    2.19 +    checkConcept<MappableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
    2.20    }
    2.21    std::cout << __FILE__ ": All tests passed.\n";
    2.22