1.1 --- a/benchmark/edge_lookup_test.h Thu Oct 12 11:09:17 2006 +0000
1.2 +++ b/benchmark/edge_lookup_test.h Thu Oct 12 11:53:31 2006 +0000
1.3 @@ -189,92 +189,92 @@
1.4
1.5 };
1.6
1.7 - template<class G>
1.8 - class EdgeLookUp4
1.9 - {
1.10 - public:
1.11 - GRAPH_TYPEDEFS(typename G)
1.12 - typedef G Graph;
1.13 +// template<class G>
1.14 +// class EdgeLookUp4
1.15 +// {
1.16 +// public:
1.17 +// GRAPH_TYPEDEFS(typename G)
1.18 +// typedef G Graph;
1.19
1.20 - private:
1.21 - const Graph &_g;
1.22 - typename Graph::template NodeMap<Edge*> _start;
1.23 - typename Graph::template NodeMap<Edge*> _end;
1.24 - std::vector<Edge> _edges;
1.25 +// private:
1.26 +// const Graph &_g;
1.27 +// typename Graph::template NodeMap<Edge*> _start;
1.28 +// typename Graph::template NodeMap<Edge*> _end;
1.29 +// std::vector<Edge> _edges;
1.30
1.31 - class EdgeLess {
1.32 - const Graph &g;
1.33 - public:
1.34 - EdgeLess(const Graph &_g) : g(_g) {}
1.35 - bool operator()(Edge a,Edge b) const
1.36 - {
1.37 - return g.target(a)<g.target(b);
1.38 - }
1.39 - };
1.40 +// class EdgeLess {
1.41 +// const Graph &g;
1.42 +// public:
1.43 +// EdgeLess(const Graph &_g) : g(_g) {}
1.44 +// bool operator()(Edge a,Edge b) const
1.45 +// {
1.46 +// return g.target(a)<g.target(b);
1.47 +// }
1.48 +// };
1.49
1.50 - public:
1.51 +// public:
1.52
1.53 - ///Constructor
1.54 - EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.55 +// ///Constructor
1.56 +// EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.57
1.58 - public:
1.59 - ///Refresh the data structure at a node.
1.60 - void refresh(Node n)
1.61 - {
1.62 - const int bi = _start[n] = _edges.size();
1.63 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.64 - const typename std::vector<Edge>::iterator ei=_edges.end();
1.65 - _end[n]=_edges.size();
1.66 - std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.67 - }
1.68 - ///Refresh the full data structure.
1.69 - void refresh()
1.70 - {
1.71 - _edges.resize(countEdges(_g));
1.72 - int l=0;
1.73 - for(NodeIt n(_g);n!=INVALID;++n)
1.74 - {
1.75 - int ls = l;
1.76 - _start[n]=&(_edges[l]);
1.77 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.78 - _end[n]=&(_edges[l]);
1.79 - std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.80 - }
1.81 +// public:
1.82 +// ///Refresh the data structure at a node.
1.83 +// void refresh(Node n)
1.84 +// {
1.85 +// const int bi = _start[n] = _edges.size();
1.86 +// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.87 +// const typename std::vector<Edge>::iterator ei=_edges.end();
1.88 +// _end[n]=_edges.size();
1.89 +// std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.90 +// }
1.91 +// ///Refresh the full data structure.
1.92 +// void refresh()
1.93 +// {
1.94 +// _edges.resize(countEdges(_g));
1.95 +// int l=0;
1.96 +// for(NodeIt n(_g);n!=INVALID;++n)
1.97 +// {
1.98 +// int ls = l;
1.99 +// _start[n]=&(_edges[l]);
1.100 +// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.101 +// _end[n]=&(_edges[l]);
1.102 +// std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.103 +// }
1.104
1.105 - }
1.106 +// }
1.107
1.108 - ///Find an edge between two nodes.
1.109 +// ///Find an edge between two nodes.
1.110
1.111 - ///Find an edge between two nodes.
1.112 - ///\param s The source node
1.113 - ///\param t The target node
1.114 - ///\return An edge from \c s to \c t if there exists,
1.115 - ///\ref INVALID otherwise.
1.116 +// ///Find an edge between two nodes.
1.117 +// ///\param s The source node
1.118 +// ///\param t The target node
1.119 +// ///\return An edge from \c s to \c t if there exists,
1.120 +// ///\ref INVALID otherwise.
1.121
1.122 - Edge operator()(Node s, Node t)
1.123 - {
1.124 - Edge *a=_start[s];
1.125 - Edge *b=_end[s];
1.126 - while(a!=b)
1.127 - {
1.128 - Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
1.129 - Node tt = _g.target(*m);
1.130 - if(tt==t) return *m;
1.131 - else if(tt<t) a=m+1;
1.132 - else b=m;
1.133 - }
1.134 - return INVALID;
1.135 - }
1.136 +// Edge operator()(Node s, Node t)
1.137 +// {
1.138 +// Edge *a=_start[s];
1.139 +// Edge *b=_end[s];
1.140 +// while(a!=b)
1.141 +// {
1.142 +// Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
1.143 +// Node tt = _g.target(*m);
1.144 +// if(tt==t) return *m;
1.145 +// else if(tt<t) a=m+1;
1.146 +// else b=m;
1.147 +// }
1.148 +// return INVALID;
1.149 +// }
1.150
1.151 - ///Find the next edge
1.152 +// ///Find the next edge
1.153
1.154 - ///\warning This function is unimplemented.
1.155 - Edge operator()(Node s, Node t, Edge prev)
1.156 - {
1.157 - return prev==INVALID?(*this)(s,t):INVALID;
1.158 - }
1.159 +// ///\warning This function is unimplemented.
1.160 +// Edge operator()(Node s, Node t, Edge prev)
1.161 +// {
1.162 +// return prev==INVALID?(*this)(s,t):INVALID;
1.163 +// }
1.164
1.165 - };
1.166 +// };
1.167
1.168 }
1.169
2.1 --- a/benchmark/swap_bipartite_bench.cc Thu Oct 12 11:09:17 2006 +0000
2.2 +++ b/benchmark/swap_bipartite_bench.cc Thu Oct 12 11:53:31 2006 +0000
2.3 @@ -3,6 +3,7 @@
2.4 #include <sstream>
2.5
2.6 #include <lemon/smart_graph.h>
2.7 +#include <lemon/list_graph.h>
2.8
2.9 #include <lemon/bpugraph_adaptor.h>
2.10 #include <lemon/bipartite_matching.h>
2.11 @@ -16,6 +17,7 @@
2.12 using namespace lemon;
2.13
2.14 typedef SmartBpUGraph Graph;
2.15 +typedef ListBpUGraph LGraph;
2.16 BPUGRAPH_TYPEDEFS(Graph);
2.17
2.18 int _urandom_init() {
2.19 @@ -40,24 +42,36 @@
2.20 int s = 100;
2.21
2.22 Timer nt(false), st(false);
2.23 + Timer lnt(false), lst(false);
2.24
2.25 for (int i = 0; i < s; ++i) {
2.26 Graph graph;
2.27 + LGraph lgraph;
2.28 vector<Node> aNodes;
2.29 vector<Node> bNodes;
2.30 + vector<LGraph::Node> laNodes;
2.31 + vector<LGraph::Node> lbNodes;
2.32
2.33 for (int i = 0; i < n; ++i) {
2.34 Node node = graph.addANode();
2.35 aNodes.push_back(node);
2.36 + LGraph::Node lnode = lgraph.addANode();
2.37 + laNodes.push_back(lnode);
2.38 }
2.39 for (int i = 0; i < m; ++i) {
2.40 Node node = graph.addBNode();
2.41 bNodes.push_back(node);
2.42 + LGraph::Node lnode = lgraph.addBNode();
2.43 + lbNodes.push_back(lnode);
2.44 }
2.45 for (int i = 0; i < e; ++i) {
2.46 - Node aNode = aNodes[urandom(n)];
2.47 - Node bNode = bNodes[urandom(m)];
2.48 + int a,b;
2.49 + Node aNode = aNodes[a=urandom(n)];
2.50 + Node bNode = bNodes[b=urandom(m)];
2.51 graph.addEdge(aNode, bNode);
2.52 + LGraph::Node laNode = laNodes[a];
2.53 + LGraph::Node lbNode = lbNodes[b];
2.54 + lgraph.addEdge(laNode, lbNode);
2.55 }
2.56
2.57 {
2.58 @@ -80,11 +94,32 @@
2.59 bpmatch.start();
2.60 st.stop();
2.61
2.62 + }
2.63 + {
2.64 + MaxBipartiteMatching<LGraph> bpmatch(lgraph);
2.65 +
2.66 + lnt.start();
2.67 + bpmatch.init();
2.68 + bpmatch.start();
2.69 + lnt.stop();
2.70 +
2.71 }
2.72 -
2.73 - }
2.74
2.75 - cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;
2.76 + {
2.77 + typedef SwapBpUGraphAdaptor<LGraph> SGraph;
2.78 + SGraph sgraph(lgraph);
2.79 + MaxBipartiteMatching<SGraph> bpmatch(sgraph);
2.80 +
2.81 + lst.start();
2.82 + bpmatch.init();
2.83 + bpmatch.start();
2.84 + lst.stop();
2.85 +
2.86 + }
2.87 + }
2.88 +
2.89 + cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime()
2.90 + << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl;
2.91
2.92 }
2.93