Changeset 2239:18c24fe93b99 in lemon0.x for benchmark
 Timestamp:
 10/12/06 13:53:31 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2983
 Location:
 benchmark
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

benchmark/edge_lookup_test.h
r2235 r2239 190 190 }; 191 191 192 template<class G>193 class EdgeLookUp4194 {195 public:196 GRAPH_TYPEDEFS(typename G)197 typedef G Graph;198 199 private:200 const Graph &_g;201 typename Graph::template NodeMap<Edge*> _start;202 typename Graph::template NodeMap<Edge*> _end;203 std::vector<Edge> _edges;204 205 class EdgeLess {206 const Graph &g;207 public:208 EdgeLess(const Graph &_g) : g(_g) {}209 bool operator()(Edge a,Edge b) const210 {211 return g.target(a)<g.target(b);212 }213 };214 215 public:216 217 ///Constructor218 EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}219 220 public:221 ///Refresh the data structure at a node.222 void refresh(Node n)223 {224 const int bi = _start[n] = _edges.size();225 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);226 const typename std::vector<Edge>::iterator ei=_edges.end();227 _end[n]=_edges.size();228 std::sort(_edges.begin()+bi,ei,EdgeLess(_g));229 }230 ///Refresh the full data structure.231 void refresh()232 {233 _edges.resize(countEdges(_g));234 int l=0;235 for(NodeIt n(_g);n!=INVALID;++n)236 {237 int ls = l;238 _start[n]=&(_edges[l]);239 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;240 _end[n]=&(_edges[l]);241 std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));242 }243 244 }245 246 ///Find an edge between two nodes.247 248 ///Find an edge between two nodes.249 ///\param s The source node250 ///\param t The target node251 ///\return An edge from \c s to \c t if there exists,252 ///\ref INVALID otherwise.253 254 Edge operator()(Node s, Node t)255 {256 Edge *a=_start[s];257 Edge *b=_end[s];258 while(a!=b)259 {260 Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);261 Node tt = _g.target(*m);262 if(tt==t) return *m;263 else if(tt<t) a=m+1;264 else b=m;265 }266 return INVALID;267 }268 269 ///Find the next edge270 271 ///\warning This function is unimplemented.272 Edge operator()(Node s, Node t, Edge prev)273 {274 return prev==INVALID?(*this)(s,t):INVALID;275 }276 277 };192 // template<class G> 193 // class EdgeLookUp4 194 // { 195 // public: 196 // GRAPH_TYPEDEFS(typename G) 197 // typedef G Graph; 198 199 // private: 200 // const Graph &_g; 201 // typename Graph::template NodeMap<Edge*> _start; 202 // typename Graph::template NodeMap<Edge*> _end; 203 // std::vector<Edge> _edges; 204 205 // class EdgeLess { 206 // const Graph &g; 207 // public: 208 // EdgeLess(const Graph &_g) : g(_g) {} 209 // bool operator()(Edge a,Edge b) const 210 // { 211 // return g.target(a)<g.target(b); 212 // } 213 // }; 214 215 // public: 216 217 // ///Constructor 218 // EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} 219 220 // public: 221 // ///Refresh the data structure at a node. 222 // void refresh(Node n) 223 // { 224 // const int bi = _start[n] = _edges.size(); 225 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e); 226 // const typename std::vector<Edge>::iterator ei=_edges.end(); 227 // _end[n]=_edges.size(); 228 // std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); 229 // } 230 // ///Refresh the full data structure. 231 // void refresh() 232 // { 233 // _edges.resize(countEdges(_g)); 234 // int l=0; 235 // for(NodeIt n(_g);n!=INVALID;++n) 236 // { 237 // int ls = l; 238 // _start[n]=&(_edges[l]); 239 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; 240 // _end[n]=&(_edges[l]); 241 // std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); 242 // } 243 244 // } 245 246 // ///Find an edge between two nodes. 247 248 // ///Find an edge between two nodes. 249 // ///\param s The source node 250 // ///\param t The target node 251 // ///\return An edge from \c s to \c t if there exists, 252 // ///\ref INVALID otherwise. 253 254 // Edge operator()(Node s, Node t) 255 // { 256 // Edge *a=_start[s]; 257 // Edge *b=_end[s]; 258 // while(a!=b) 259 // { 260 // Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc); 261 // Node tt = _g.target(*m); 262 // if(tt==t) return *m; 263 // else if(tt<t) a=m+1; 264 // else b=m; 265 // } 266 // return INVALID; 267 // } 268 269 // ///Find the next edge 270 271 // ///\warning This function is unimplemented. 272 // Edge operator()(Node s, Node t, Edge prev) 273 // { 274 // return prev==INVALID?(*this)(s,t):INVALID; 275 // } 276 277 // }; 278 278 279 279 } 
benchmark/swap_bipartite_bench.cc
r2232 r2239 4 4 5 5 #include <lemon/smart_graph.h> 6 #include <lemon/list_graph.h> 6 7 7 8 #include <lemon/bpugraph_adaptor.h> … … 17 18 18 19 typedef SmartBpUGraph Graph; 20 typedef ListBpUGraph LGraph; 19 21 BPUGRAPH_TYPEDEFS(Graph); 20 22 … … 41 43 42 44 Timer nt(false), st(false); 45 Timer lnt(false), lst(false); 43 46 44 47 for (int i = 0; i < s; ++i) { 45 48 Graph graph; 49 LGraph lgraph; 46 50 vector<Node> aNodes; 47 51 vector<Node> bNodes; 52 vector<LGraph::Node> laNodes; 53 vector<LGraph::Node> lbNodes; 48 54 49 55 for (int i = 0; i < n; ++i) { 50 56 Node node = graph.addANode(); 51 57 aNodes.push_back(node); 58 LGraph::Node lnode = lgraph.addANode(); 59 laNodes.push_back(lnode); 52 60 } 53 61 for (int i = 0; i < m; ++i) { 54 62 Node node = graph.addBNode(); 55 63 bNodes.push_back(node); 64 LGraph::Node lnode = lgraph.addBNode(); 65 lbNodes.push_back(lnode); 56 66 } 57 67 for (int i = 0; i < e; ++i) { 58 Node aNode = aNodes[urandom(n)]; 59 Node bNode = bNodes[urandom(m)]; 68 int a,b; 69 Node aNode = aNodes[a=urandom(n)]; 70 Node bNode = bNodes[b=urandom(m)]; 60 71 graph.addEdge(aNode, bNode); 72 LGraph::Node laNode = laNodes[a]; 73 LGraph::Node lbNode = lbNodes[b]; 74 lgraph.addEdge(laNode, lbNode); 61 75 } 62 76 … … 81 95 st.stop(); 82 96 97 } 98 { 99 MaxBipartiteMatching<LGraph> bpmatch(lgraph); 100 101 lnt.start(); 102 bpmatch.init(); 103 bpmatch.start(); 104 lnt.stop(); 105 83 106 } 84 85 }86 107 87 cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl; 108 { 109 typedef SwapBpUGraphAdaptor<LGraph> SGraph; 110 SGraph sgraph(lgraph); 111 MaxBipartiteMatching<SGraph> bpmatch(sgraph); 112 113 lst.start(); 114 bpmatch.init(); 115 bpmatch.start(); 116 lst.stop(); 117 118 } 119 } 120 121 cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() 122 << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl; 88 123 89 124 }
Note: See TracChangeset
for help on using the changeset viewer.