1.1 --- a/src/benchmark/Makefile.am Mon Jul 19 13:30:20 2004 +0000
1.2 +++ b/src/benchmark/Makefile.am Mon Jul 19 13:31:47 2004 +0000
1.3 @@ -1,5 +1,7 @@
1.4 -AM_CPPFLAGS = -I$(top_srcdir)/src -I$(top_srcdir)/src/work
1.5 +AM_CPPFLAGS = -I$(top_srcdir)/src -I$(top_srcdir)/src/work -I$(top_srcdir)/src/work/marci
1.6
1.7 -noinst_PROGRAMS = graph-bench
1.8 +noinst_PROGRAMS = graph-bench hcube
1.9
1.10 graph_bench_SOURCES = graph-bench.cc
1.11 +
1.12 +hcube_SOURCES = hcube.cc
2.1 --- a/src/benchmark/graph-bench.cc Mon Jul 19 13:30:20 2004 +0000
2.2 +++ b/src/benchmark/graph-bench.cc Mon Jul 19 13:31:47 2004 +0000
2.3 @@ -3,6 +3,7 @@
2.4 #include<hugo/time_measure.h>
2.5 #include<iostream>
2.6 #include<sage_graph.h>
2.7 +#include<vector>
2.8
2.9 using namespace hugo;
2.10
2.11 @@ -48,10 +49,12 @@
2.12
2.13 Graph G;
2.14
2.15 - Node nodes[n];
2.16 + // Node nodes[n];
2.17 + std::vector<Node> nodes(n);
2.18 for(int i=0;i<n;i++) nodes[i]=G.addNode();
2.19
2.20 - Edge equ[rat];
2.21 + //Edge equ[rat];
2.22 + std::vector<Edge> equ(rat);
2.23
2.24 unsigned long long int count;
2.25
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/benchmark/hcube.cc Mon Jul 19 13:31:47 2004 +0000
3.3 @@ -0,0 +1,149 @@
3.4 +// -*- mode:C++ -*-
3.5 +
3.6 +#include<math.h>
3.7 +#include<hugo/list_graph.h>
3.8 +#include<hugo/smart_graph.h>
3.9 +#include<hugo/dijkstra.h>
3.10 +#include<hugo/time_measure.h>
3.11 +#include<iostream>
3.12 +#include<../work/jacint/max_flow.h>
3.13 +
3.14 +using namespace std;
3.15 +using namespace hugo;
3.16 +
3.17 +///An experimental typedef factory
3.18 +#define GRAPH_TYPEDEF_FACTORY(Graph) \
3.19 + typedef typename Graph:: Node Node;\
3.20 + typedef typename Graph:: NodeIt NodeIn;\
3.21 + typedef typename Graph:: Edge Edge;\
3.22 + typedef typename Graph:: EdgeIt EdgeIt;\
3.23 + typedef typename Graph:: InEdgeIt InEdgeIt;\
3.24 + typedef typename Graph::OutEdgeIt OutEdgeIt;
3.25 +
3.26 +#define GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph) \
3.27 + typedef Graph:: Node Node;\
3.28 + typedef Graph:: NodeIt NodeIn;\
3.29 + typedef Graph:: Edge Edge;\
3.30 + typedef Graph:: EdgeIt EdgeIt;\
3.31 + typedef Graph:: InEdgeIt InEdgeIt;\
3.32 + typedef Graph::OutEdgeIt OutEdgeIt;
3.33 +
3.34 +
3.35 +class Primes
3.36 +{
3.37 + vector<int> primes;
3.38 + int n;
3.39 +
3.40 + bool isPrime(int m)
3.41 + {
3.42 + for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false;
3.43 + return true;
3.44 + }
3.45 +public:
3.46 + Primes() : n(1) {}
3.47 +
3.48 + int operator() ()
3.49 + {
3.50 + if(primes.size()==0) {
3.51 + primes.push_back(2);
3.52 + return 2;
3.53 + }
3.54 + else {
3.55 + do n+=2; while(!isPrime(n));
3.56 + primes.push_back(n);
3.57 + return n;
3.58 + }
3.59 + }
3.60 +};
3.61 +
3.62 +template<class Graph>
3.63 +void addHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
3.64 +{
3.65 + GRAPH_TYPEDEF_FACTORY(Graph);
3.66 +
3.67 + vector<int> bits(dim+1);
3.68 + bits[0]=1;
3.69 + for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
3.70 +
3.71 + for(int i=0;i<bits[dim];i++) {
3.72 + nodes.push_back(G.addNode());
3.73 + for(j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
3.74 + }
3.75 +}
3.76 +
3.77 +template<class Graph>
3.78 +void addBiDirHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
3.79 +{
3.80 + GRAPH_TYPEDEF_FACTORY(Graph);
3.81 +
3.82 + vector<int> bits(dim+1);
3.83 + bits[0]=1;
3.84 + for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
3.85 +
3.86 + for(int i=0;i<bits[dim];i++) {
3.87 + nodes.push_back(G.addNode());
3.88 + for(int j=0;j<dim;j++) if(i&bits[j]) {
3.89 + G.addEdge(nodes[i-bits[j]],nodes[i]);
3.90 + G.addEdge(nodes[i],nodes[i-bits[j]]);
3.91 + }
3.92 +
3.93 + }
3.94 +}
3.95 +
3.96 +int main(int argc, char *argv[])
3.97 +{
3.98 + // typedef ListGraph Graph;
3.99 + typedef SmartGraph Graph;
3.100 +
3.101 + ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
3.102 + GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
3.103 +
3.104 + Graph G;
3.105 +
3.106 + Timer T;
3.107 +
3.108 + if(argc!=2) {
3.109 + cout << "Usage: " << argv[0] << " dim\n";
3.110 + return 1;
3.111 + }
3.112 +
3.113 + int dim=atoi(argv[1]);
3.114 +
3.115 + cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
3.116 + << dim*(1<<dim) << " edges):";
3.117 +
3.118 + vector<Node> nodes;
3.119 + addBiDirHiperCube(G,dim,nodes);
3.120 + cout << T;
3.121 + cout << "\nGenerating the lengths: ";
3.122 + T.reset();
3.123 + Graph::EdgeMap<int> map(G);
3.124 + {
3.125 + Primes P;
3.126 + for(int i=0;i<dim*(1<<dim);i++) P();
3.127 +
3.128 + // for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
3.129 + for(int i=0;i<dim*(1<<dim);i++)
3.130 + // map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
3.131 + map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
3.132 + }
3.133 +
3.134 + cout << T;
3.135 + cout << "\nRunning Dijkstra: ";
3.136 + T.reset();
3.137 + {
3.138 + Dijkstra<Graph> Dij(G,map);
3.139 + Dij.run(nodes[0]);
3.140 + }
3.141 + cout << T;
3.142 +// cout << "\nRunning MaxFlow: ";
3.143 +// T.reset();
3.144 +// {
3.145 +// Graph::EdgeMap<int> flow(G);
3.146 +
3.147 +// MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
3.148 +// MF.run(MF.NO_FLOW);
3.149 +// }
3.150 +// cout << T;
3.151 + cout << "\n";
3.152 +}