Changeset 1383:79b68a337f9f in lemon-0.x

Timestamp:

04/23/05 18:59:49 (19 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1836

Message:

A new implementation of UndirGraphWrapper?, accordig to the undirected concepts

Location:

src

Files:

• lemon/graph_wrapper.h (modified) (3 diffs)
• test/graph_wrapper_test.cc (modified) (2 diffs)

src/lemon/graph_wrapper.h

@@ -29 +29 @@
 #include <lemon/maps.h>
 #include <lemon/bits/iterable_graph_extender.h>
+#include <lemon/bits/undir_graph_extender.h>
 #include <iostream>
 
@@ -152 +153 @@
     typedef typename Parent::Edge Edge;
 
-    using Parent::first;
+    //    using Parent::first;
     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
 
-    using Parent::next;
+    //    using Parent::next;
     void nextIn(Edge& i) const { Parent::nextOut(i); }
     void nextOut(Edge& i) const { Parent::nextIn(i); }
@@ -566 +567 @@
   };
 
-
-  template<typename Graph>
-  class UndirGraphWrapper : public GraphWrapper<Graph> {
-  public:
-    typedef GraphWrapper<Graph> Parent; 
-  protected:
-    UndirGraphWrapper() : GraphWrapper<Graph>() { }
+  template <typename _Graph>
+  class UndirGraphWrapperBase : 
+    public UndirGraphExtender<GraphWrapperBase<_Graph> > {
+  public:
+    typedef _Graph Graph;
+    typedef UndirGraphExtender<GraphWrapperBase<_Graph> > Parent;
+  protected:
+    UndirGraphWrapperBase() : Parent() { }
+  public:
+    typedef typename Parent::UndirEdge UndirEdge;
+    typedef typename Parent::Edge Edge;
     
-  public:
-    typedef typename GraphWrapper<Graph>::Node Node;
-    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
-    typedef typename GraphWrapper<Graph>::Edge Edge;
-    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
-
-    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
-
-    class OutEdgeIt {
-      friend class UndirGraphWrapper<Graph>;
-      bool out_or_in; //true iff out
-      typename Graph::OutEdgeIt out;
-      typename Graph::InEdgeIt in;
+    /// \bug Why cant an edge say that it is forward or not??? 
+    /// By this, a pointer to the graph have to be stored
+    /// The implementation
+    template <typename T>
+    class EdgeMap {
+    protected:
+      const UndirGraphWrapperBase<_Graph>* g;
+      template <typename TT> friend class EdgeMap;
+      typename _Graph::template EdgeMap<T> forward_map, backward_map; 
     public:
-      OutEdgeIt() { }
-      OutEdgeIt(const Invalid& i) : Edge(i) { }
-      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
-        out_or_in=true; _G.graph->first(out, _n);
-        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
-      } 
-      operator Edge() const { 
-        if (out_or_in) return Edge(out); else return Edge(in); 
+      typedef T Value;
+      typedef Edge Key;
+      
+      EdgeMap(const UndirGraphWrapperBase<_Graph>& _g) : g(&_g), 
+        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
+
+      EdgeMap(const UndirGraphWrapperBase<_Graph>& _g, T a) : g(&_g), 
+        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
+      
+      void set(Edge e, T a) { 
+        if (g->forward(e)) 
+          forward_map.set(e, a); 
+        else 
+          backward_map.set(e, a); 
+      }
+
+      T operator[](Edge e) const { 
+        if (g->forward(e)) 
+          return forward_map[e]; 
+        else 
+          return backward_map[e]; 
       }
     };
-
-    typedef OutEdgeIt InEdgeIt; 
-
-    using GraphWrapper<Graph>::first;
-    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
-      i=OutEdgeIt(*this, p); return i;
-    }
-
-    using GraphWrapper<Graph>::next;
-
-    OutEdgeIt& next(OutEdgeIt& e) const {
-      if (e.out_or_in) {
-        typename Graph::Node n=this->graph->source(e.out);
-        this->graph->next(e.out);
-        if (!this->graph->valid(e.out)) { 
-          e.out_or_in=false; this->graph->first(e.in, n); }
-      } else {
-        this->graph->next(e.in);
-      }
-      return e;
-    }
-
-    Node aNode(const OutEdgeIt& e) const { 
-      if (e.out_or_in) return this->graph->source(e); else 
-        return this->graph->target(e); }
-    Node bNode(const OutEdgeIt& e) const { 
-      if (e.out_or_in) return this->graph->target(e); else 
-        return this->graph->source(e); }
-
-    //    KEEP_MAPS(Parent, UndirGraphWrapper);
-
-  };
-  
-//   /// \brief An undirected graph template.
-//   ///
-//   ///\warning Graph wrappers are in even more experimental state than the other
-//   ///parts of the lib. Use them at your own risk.
-//   ///
-//   /// An undirected graph template.
-//   /// This class works as an undirected graph and a directed graph of 
-//   /// class \c Graph is used for the physical storage.
-//   /// \ingroup graphs
-  template<typename Graph>
-  class UndirGraph : public UndirGraphWrapper<Graph> {
-    typedef UndirGraphWrapper<Graph> Parent;
-  protected:
-    Graph gr;
-  public:
-    UndirGraph() : UndirGraphWrapper<Graph>() { 
-      Parent::setGraph(gr); 
-    }
-
-    //    KEEP_MAPS(Parent, UndirGraph);
+        
+    template <typename T>
+    class UndirEdgeMap {
+      template <typename TT> friend class UndirEdgeMap;
+      typename _Graph::template EdgeMap<T> map; 
+    public:
+      typedef T Value;
+      typedef UndirEdge Key;
+      
+      UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g) : 
+        map(*(g.graph)) { }
+
+      UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g, T a) : 
+        map(*(g.graph), a) { }
+      
+      void set(UndirEdge e, T a) { 
+        map.set(e, a); 
+      }
+
+      T operator[](UndirEdge e) const { 
+        return map[e]; 
+      }
+    };
+      
+  };
+
+  /// \brief An undirected graph is made from a directed graph by a wrapper
+  ///
+  /// Undocumented, untested!!!
+  /// If somebody knows nice demo application, let's polulate it.
+  /// 
+  /// \author Marton Makai
+  template<typename _Graph>
+  class UndirGraphWrapper : 
+    public IterableUndirGraphExtender<
+    UndirGraphWrapperBase<_Graph> > {
+  public:
+    typedef _Graph Graph;
+    typedef IterableUndirGraphExtender<
+      UndirGraphWrapperBase<_Graph> > Parent;
+  protected:
+    UndirGraphWrapper() { }
+  public:
+    UndirGraphWrapper(_Graph& _graph) { 
+      setGraph(_graph);
+    }
   };
 

src/test/graph_wrapper_test.cc

@@ -20 +20 @@
 #include<lemon/smart_graph.h>
 #include<lemon/concept/graph.h>
+#include<lemon/concept/undir_graph.h>
 
 #include<lemon/list_graph.h>
@@ -63 +64 @@
     checkConcept<StaticGraph, ErasingFirstGraphWrapper<Graph, 
       Graph::NodeMap<Graph::Edge> > >(); 
+
+    /// \bug why does not compile with StaticGraph
+    checkConcept<BaseIterableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
+    checkConcept<IterableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
+    checkConcept<MappableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
   }
   std::cout << __FILE__ ": All tests passed.\n";