alpar@1956: /* -*- C++ -*-
alpar@1956:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1956:  *
alpar@1956:  * Permission to use, modify and distribute this software is granted
alpar@1956:  * provided that this copyright notice appears in all copies. For
alpar@1956:  * precise terms see the accompanying LICENSE file.
alpar@1956:  *
alpar@1956:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1956:  * express or implied, and with no claim as to its suitability for any
alpar@1956:  * purpose.
alpar@1956:  *
alpar@1956:  */
alpar@708: 
alpar@1632: #include<cmath>
alpar@921: #include<lemon/list_graph.h>
alpar@921: #include<lemon/smart_graph.h>
alpar@921: #include<lemon/dijkstra.h>
alpar@921: #include<lemon/preflow.h>
alpar@729: 
alpar@711: #include"bench_tools.h"
alpar@708: 
alpar@708: using namespace std;
alpar@921: using namespace lemon;
alpar@708: 
alpar@718: inline int numOfOnes(int n,int dim)
alpar@718: {
alpar@718:   int s=0;
alpar@718:   for(int i=0;i<dim;i++) {
alpar@718:     s+=n%2;
alpar@718:     n>>=1;
alpar@718:   }
alpar@718:   return s;
alpar@718: }
alpar@718: 
alpar@718: inline int numOfZeros(int n,int dim)
alpar@718: {
alpar@718:   int s=dim;
alpar@718:   for(int i=0;i<dim;i++) {
alpar@718:     s-=n&1;
alpar@718:     n>>=1;
alpar@718:   }
alpar@718:   return s;
alpar@718: }
alpar@718: 
alpar@708: int main(int argc, char *argv[])
alpar@708: {
alpar@708:   //  typedef ListGraph Graph;
alpar@708:   typedef SmartGraph Graph;
alpar@708: 
alpar@1756:   GRAPH_TYPEDEFS(Graph);
alpar@708: 
alpar@708:   Graph G;
alpar@708:   
alpar@708:   Timer T;
alpar@708:   
alpar@708:   if(argc!=2) {
alpar@708:     cout << "Usage: " << argv[0] << " dim\n";
alpar@708:     return 1;
alpar@708:   }
alpar@708:   
alpar@708:   int dim=atoi(argv[1]);
alpar@708:   
alpar@718: //   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
alpar@718: //        << dim*(1<<dim) << " edges):";
alpar@708: 
alpar@1847:   T.restart();
alpar@708:   vector<Node> nodes;
alpar@1689:   addBiDirHyperCube(G,dim,nodes);
alpar@718: 
alpar@718:   PrintTime("GENGRAPH",T);
alpar@718: 
alpar@1847:   T.restart();
alpar@708:   Graph::EdgeMap<int> map(G);
alpar@729:   for(int i=0;i<5;i++) {
alpar@708:     Primes P;
alpar@708:     for(int i=0;i<dim*(1<<dim);i++) P();
alpar@708:     
alpar@708:     //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
klao@946: 
klao@946:     ///\todo It must have been commented out because of
klao@946:     ///setToId
klao@946: //     Edge te;
klao@946: //     for(int i=0;i<dim*(1<<dim);i++) {
klao@946: //       te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));
klao@946: //       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
klao@946: //       map[te]=P();
klao@946: //     }
alpar@905:     
alpar@718: //     for(int i=0;i<(1<<dim);i++) {
alpar@718: //       int mul= (1<<(numOfZeros(i,dim)/4));
alpar@718: //       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
alpar@718: // 	map[e]*=mul;
alpar@718: //     }
alpar@708:   }
alpar@708:   
alpar@718:   PrintTime("GENLENGTHS",T);
alpar@718: 
alpar@1847:   T.restart();
alpar@708:   {
alpar@708:     Dijkstra<Graph> Dij(G,map);
alpar@729:     for(int i=0;i<10;i++)
alpar@729:       Dij.run(nodes[0]);
alpar@708:   }
alpar@718:   PrintTime("DIJKSTRA",T);
alpar@718: 
alpar@1847:   T.restart();
alpar@718:   {
alpar@718:    Graph::EdgeMap<int> flow(G);
alpar@708:    
alpar@840:     Preflow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
alpar@729:     for(int i=0;i<10;i++)
alpar@729:       MF.run(MF.NO_FLOW);
alpar@718:   }
alpar@718:   PrintTime("PREFLOW",T);
alpar@718: 
alpar@708: }