1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/benchmark/hcube.cc Mon Jul 19 13:31:47 2004 +0000
1.3 @@ -0,0 +1,149 @@
1.4 +// -*- mode:C++ -*-
1.5 +
1.6 +#include<math.h>
1.7 +#include<hugo/list_graph.h>
1.8 +#include<hugo/smart_graph.h>
1.9 +#include<hugo/dijkstra.h>
1.10 +#include<hugo/time_measure.h>
1.11 +#include<iostream>
1.12 +#include<../work/jacint/max_flow.h>
1.13 +
1.14 +using namespace std;
1.15 +using namespace hugo;
1.16 +
1.17 +///An experimental typedef factory
1.18 +#define GRAPH_TYPEDEF_FACTORY(Graph) \
1.19 + typedef typename Graph:: Node Node;\
1.20 + typedef typename Graph:: NodeIt NodeIn;\
1.21 + typedef typename Graph:: Edge Edge;\
1.22 + typedef typename Graph:: EdgeIt EdgeIt;\
1.23 + typedef typename Graph:: InEdgeIt InEdgeIt;\
1.24 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.25 +
1.26 +#define GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph) \
1.27 + typedef Graph:: Node Node;\
1.28 + typedef Graph:: NodeIt NodeIn;\
1.29 + typedef Graph:: Edge Edge;\
1.30 + typedef Graph:: EdgeIt EdgeIt;\
1.31 + typedef Graph:: InEdgeIt InEdgeIt;\
1.32 + typedef Graph::OutEdgeIt OutEdgeIt;
1.33 +
1.34 +
1.35 +class Primes
1.36 +{
1.37 + vector<int> primes;
1.38 + int n;
1.39 +
1.40 + bool isPrime(int m)
1.41 + {
1.42 + for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false;
1.43 + return true;
1.44 + }
1.45 +public:
1.46 + Primes() : n(1) {}
1.47 +
1.48 + int operator() ()
1.49 + {
1.50 + if(primes.size()==0) {
1.51 + primes.push_back(2);
1.52 + return 2;
1.53 + }
1.54 + else {
1.55 + do n+=2; while(!isPrime(n));
1.56 + primes.push_back(n);
1.57 + return n;
1.58 + }
1.59 + }
1.60 +};
1.61 +
1.62 +template<class Graph>
1.63 +void addHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
1.64 +{
1.65 + GRAPH_TYPEDEF_FACTORY(Graph);
1.66 +
1.67 + vector<int> bits(dim+1);
1.68 + bits[0]=1;
1.69 + for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
1.70 +
1.71 + for(int i=0;i<bits[dim];i++) {
1.72 + nodes.push_back(G.addNode());
1.73 + for(j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
1.74 + }
1.75 +}
1.76 +
1.77 +template<class Graph>
1.78 +void addBiDirHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
1.79 +{
1.80 + GRAPH_TYPEDEF_FACTORY(Graph);
1.81 +
1.82 + vector<int> bits(dim+1);
1.83 + bits[0]=1;
1.84 + for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
1.85 +
1.86 + for(int i=0;i<bits[dim];i++) {
1.87 + nodes.push_back(G.addNode());
1.88 + for(int j=0;j<dim;j++) if(i&bits[j]) {
1.89 + G.addEdge(nodes[i-bits[j]],nodes[i]);
1.90 + G.addEdge(nodes[i],nodes[i-bits[j]]);
1.91 + }
1.92 +
1.93 + }
1.94 +}
1.95 +
1.96 +int main(int argc, char *argv[])
1.97 +{
1.98 + // typedef ListGraph Graph;
1.99 + typedef SmartGraph Graph;
1.100 +
1.101 + ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
1.102 + GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
1.103 +
1.104 + Graph G;
1.105 +
1.106 + Timer T;
1.107 +
1.108 + if(argc!=2) {
1.109 + cout << "Usage: " << argv[0] << " dim\n";
1.110 + return 1;
1.111 + }
1.112 +
1.113 + int dim=atoi(argv[1]);
1.114 +
1.115 + cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
1.116 + << dim*(1<<dim) << " edges):";
1.117 +
1.118 + vector<Node> nodes;
1.119 + addBiDirHiperCube(G,dim,nodes);
1.120 + cout << T;
1.121 + cout << "\nGenerating the lengths: ";
1.122 + T.reset();
1.123 + Graph::EdgeMap<int> map(G);
1.124 + {
1.125 + Primes P;
1.126 + for(int i=0;i<dim*(1<<dim);i++) P();
1.127 +
1.128 + // for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
1.129 + for(int i=0;i<dim*(1<<dim);i++)
1.130 + // map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
1.131 + map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
1.132 + }
1.133 +
1.134 + cout << T;
1.135 + cout << "\nRunning Dijkstra: ";
1.136 + T.reset();
1.137 + {
1.138 + Dijkstra<Graph> Dij(G,map);
1.139 + Dij.run(nodes[0]);
1.140 + }
1.141 + cout << T;
1.142 +// cout << "\nRunning MaxFlow: ";
1.143 +// T.reset();
1.144 +// {
1.145 +// Graph::EdgeMap<int> flow(G);
1.146 +
1.147 +// MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
1.148 +// MF.run(MF.NO_FLOW);
1.149 +// }
1.150 +// cout << T;
1.151 + cout << "\n";
1.152 +}