Changeset 2239:18c24fe93b99 in lemon-0.x for benchmark

Timestamp:

10/12/06 13:53:31 (18 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

Turn off 32bit specific tests.

Location:

benchmark

Files:

• edge_lookup_test.h (modified) (1 diff)
• swap_bipartite_bench.cc (modified) (4 diffs)

benchmark/edge_lookup_test.h

@@ -190 +190 @@
   };
 
-  template<class G>
-  class EdgeLookUp4
-  {
-  public:
-    GRAPH_TYPEDEFS(typename G)
-    typedef G Graph;
-
-  private:
-    const Graph &_g;
-    typename Graph::template NodeMap<Edge*> _start;
-    typename Graph::template NodeMap<Edge*> _end;
-    std::vector<Edge> _edges;
-    
-    class EdgeLess {
-      const Graph &g;
-    public:
-      EdgeLess(const Graph &_g) : g(_g) {}
-      bool operator()(Edge a,Edge b) const 
-      {
-        return g.target(a)<g.target(b);
-      }
-    };
-    
-  public:
-    
-    ///Constructor
-    EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
-    
-  public:
-    ///Refresh the data structure at a node.
-    void refresh(Node n) 
-    {
-      const int bi = _start[n] = _edges.size();
-      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
-      const typename std::vector<Edge>::iterator ei=_edges.end();
-      _end[n]=_edges.size();
-      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
-    }
-    ///Refresh the full data structure.
-    void refresh() 
-    {
-      _edges.resize(countEdges(_g));
-      int l=0;
-      for(NodeIt n(_g);n!=INVALID;++n)
-        {
-          int ls = l;
-          _start[n]=&(_edges[l]);       
-          for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
-          _end[n]=&(_edges[l]);
-          std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
-        }
-      
-    }
-    
-    ///Find an edge between two nodes.
-    
-    ///Find an edge between two nodes.
-    ///\param s The source node
-    ///\param t The target node
-    ///\return An edge from \c s to \c t if there exists,
-    ///\ref INVALID otherwise.
-
-    Edge operator()(Node s, Node t) 
-    {
-      Edge *a=_start[s];
-      Edge *b=_end[s];
-      while(a!=b) 
-        {
-          Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
-          Node tt = _g.target(*m);
-          if(tt==t) return *m;
-          else if(tt<t) a=m+1;
-          else b=m;
-        }
-      return INVALID;
-    }
-
-    ///Find the next edge
-      
-      ///\warning This function is unimplemented.
-    Edge operator()(Node s, Node t, Edge prev) 
-    {
-      return prev==INVALID?(*this)(s,t):INVALID;
-    }
-      
-  };
+//   template<class G>
+//   class EdgeLookUp4
+//   {
+//   public:
+//     GRAPH_TYPEDEFS(typename G)
+//     typedef G Graph;
+
+//   private:
+//     const Graph &_g;
+//     typename Graph::template NodeMap<Edge*> _start;
+//     typename Graph::template NodeMap<Edge*> _end;
+//     std::vector<Edge> _edges;
+    
+//     class EdgeLess {
+//       const Graph &g;
+//     public:
+//       EdgeLess(const Graph &_g) : g(_g) {}
+//       bool operator()(Edge a,Edge b) const 
+//       {
+//      return g.target(a)<g.target(b);
+//       }
+//     };
+    
+//   public:
+    
+//     ///Constructor
+//     EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
+    
+//   public:
+//     ///Refresh the data structure at a node.
+//     void refresh(Node n) 
+//     {
+//       const int bi = _start[n] = _edges.size();
+//       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
+//       const typename std::vector<Edge>::iterator ei=_edges.end();
+//       _end[n]=_edges.size();
+//       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
+//     }
+//     ///Refresh the full data structure.
+//     void refresh() 
+//     {
+//       _edges.resize(countEdges(_g));
+//       int l=0;
+//       for(NodeIt n(_g);n!=INVALID;++n)
+//      {
+//        int ls = l;
+//        _start[n]=&(_edges[l]);       
+//        for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
+//        _end[n]=&(_edges[l]);
+//        std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
+//      }
+      
+//     }
+    
+//     ///Find an edge between two nodes.
+    
+//     ///Find an edge between two nodes.
+//     ///\param s The source node
+//     ///\param t The target node
+//     ///\return An edge from \c s to \c t if there exists,
+//     ///\ref INVALID otherwise.
+
+//     Edge operator()(Node s, Node t) 
+//     {
+//       Edge *a=_start[s];
+//       Edge *b=_end[s];
+//       while(a!=b) 
+//      {
+//        Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
+//        Node tt = _g.target(*m);
+//        if(tt==t) return *m;
+//        else if(tt<t) a=m+1;
+//        else b=m;
+//      }
+//       return INVALID;
+//     }
+
+//     ///Find the next edge
+      
+//       ///\warning This function is unimplemented.
+//     Edge operator()(Node s, Node t, Edge prev) 
+//     {
+//       return prev==INVALID?(*this)(s,t):INVALID;
+//     }
+      
+//   };
 
 }

benchmark/swap_bipartite_bench.cc

@@ -4 +4 @@
 
 #include <lemon/smart_graph.h>
+#include <lemon/list_graph.h>
 
 #include <lemon/bpugraph_adaptor.h>
@@ -17 +18 @@
 
 typedef SmartBpUGraph Graph;
+typedef ListBpUGraph LGraph;
 BPUGRAPH_TYPEDEFS(Graph);
 
@@ -41 +43 @@
     
     Timer nt(false), st(false);
+    Timer lnt(false), lst(false);
     
     for (int i = 0; i < s; ++i) {
       Graph graph;
+      LGraph lgraph;
       vector<Node> aNodes;
       vector<Node> bNodes;  
+      vector<LGraph::Node> laNodes;
+      vector<LGraph::Node> lbNodes;  
       
       for (int i = 0; i < n; ++i) {
         Node node = graph.addANode();
         aNodes.push_back(node);
+        LGraph::Node lnode = lgraph.addANode();
+        laNodes.push_back(lnode);
       }
       for (int i = 0; i < m; ++i) {
         Node node = graph.addBNode();
         bNodes.push_back(node);
+        LGraph::Node lnode = lgraph.addBNode();
+        lbNodes.push_back(lnode);
       }
       for (int i = 0; i < e; ++i) {
-        Node aNode = aNodes[urandom(n)];
-        Node bNode = bNodes[urandom(m)];
+        int a,b;
+        Node aNode = aNodes[a=urandom(n)];
+        Node bNode = bNodes[b=urandom(m)];
         graph.addEdge(aNode, bNode);
+        LGraph::Node laNode = laNodes[a];
+        LGraph::Node lbNode = lbNodes[b];
+        lgraph.addEdge(laNode, lbNode);
       }
 
@@ -81 +95 @@
         st.stop();
         
+      }                 
+      {
+        MaxBipartiteMatching<LGraph> bpmatch(lgraph);
+        
+        lnt.start();
+        bpmatch.init();
+        bpmatch.start();
+        lnt.stop();
+        
       }
-                  
-    }
 
-    cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;
+      {
+        typedef SwapBpUGraphAdaptor<LGraph> SGraph;
+        SGraph sgraph(lgraph);
+        MaxBipartiteMatching<SGraph> bpmatch(sgraph);
+
+        lst.start();
+        bpmatch.init();
+        bpmatch.start();
+        lst.stop();
+        
+      }
+     }
+
+    cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime()
+         << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl;
 
   }