COIN-OR::LEMON - Graph Library

Changeset 718:75d36edc6bc4 in lemon-0.x


Ignore:
Timestamp:
07/21/04 09:03:20 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@970
Message:

Ready to run the first test series.

Location:
src/benchmark
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • src/benchmark/bench_tools.h

    r711 r718  
    44
    55#include<vector>
     6#include<iostream>
     7
     8#include<hugo/time_measure.h>
    69
    710///An experimental typedef factory
     
    2427
    2528///A primitive primtest
     29
     30///\bug 2 is not a prime according to this function!
    2631bool isPrim(int n)
    2732{
     
    7075};
    7176
     77inline void PrintTime(char *ID,hugo::Timer &T)
     78{
     79  hugo::TimeStamp S(T);
     80  std::cout << ID << ' ' << S.getUserTime() << ' '
     81            << S.getSystemTime() << ' ' << S.getRealTime() << std::endl;
     82}
     83
     84 
    7285
    7386#endif
  • src/benchmark/graph-bench.cc

    r711 r718  
    11#include<math.h>
    22#include<hugo/list_graph.h>
    3 #include<hugo/time_measure.h>
    4 #include<iostream>
    53
    64#include"bench_tools.h"
     
    2927  std::vector<Edge> equ(rat);
    3028 
    31   unsigned long long int count;
     29  long long int count;
    3230 
    3331  for(count=0;count<rat;count++) {
     
    3937    equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
    4038  }
    41   std::cout << "Added " << count
    42             << " ( " << n << "^2 * " << rat << " ) edges\n";
     39//   std::cout << "Added " << count
     40//          << " ( " << n << "^2 * " << rat << " ) edges\n";
     41
     42
    4343  //  for(int i=0;1;i++) ;
    4444}
     
    4646int main()
    4747{
    48   std::cout << "START: n="  << nextPrim(1000) << " rat="
    49             << nextPrim(300) << " p=" << nextPrim(100) << '\n';
    5048  hugo::Timer T;
    5149  makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
    52   std::cout << T  << '\n';
    53   std::cout << "START: n="  << nextPrim(1000) << " rat="
    54             << nextPrim(300) << " p=" << nextPrim(100) << '\n';
     50 
     51  PrintTime("BIG",T);
    5552  T.reset();
    5653  makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
    57   std::cout << T  << '\n';
     54
     55  PrintTime("SMALL",T);
    5856}
  • src/benchmark/hcube.cc

    r711 r718  
    55#include<hugo/smart_graph.h>
    66#include<hugo/dijkstra.h>
    7 #include<hugo/time_measure.h>
    8 #include<iostream>
    9 //#include<../work/jacint/max_flow.h>
     7#include<../work/jacint/max_flow_no_stack.h>
    108#include"bench_tools.h"
    119
     
    2422  for(int i=0;i<bits[dim];i++) {
    2523    nodes.push_back(G.addNode());
    26     for(j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
     24    for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
    2725  }
    2826}
     
    4745}
    4846
     47inline int numOfOnes(int n,int dim)
     48{
     49  int s=0;
     50  for(int i=0;i<dim;i++) {
     51    s+=n%2;
     52    n>>=1;
     53  }
     54  return s;
     55}
     56
     57inline int numOfZeros(int n,int dim)
     58{
     59  int s=dim;
     60  for(int i=0;i<dim;i++) {
     61    s-=n&1;
     62    n>>=1;
     63  }
     64  return s;
     65}
     66
    4967int main(int argc, char *argv[])
    5068{
     
    6684  int dim=atoi(argv[1]);
    6785 
    68   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
    69        << dim*(1<<dim) << " edges):";
     86//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
     87//        << dim*(1<<dim) << " edges):";
    7088
     89  T.reset();
    7190  vector<Node> nodes;
    7291  addBiDirHiperCube(G,dim,nodes);
    73   cout << T;
    74   cout << "\nGenerating the lengths: ";
     92
     93  PrintTime("GENGRAPH",T);
     94
    7595  T.reset();
    7696  Graph::EdgeMap<int> map(G);
     
    83103      //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
    84104      map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
     105 
     106//     for(int i=0;i<(1<<dim);i++) {
     107//       int mul= (1<<(numOfZeros(i,dim)/4));
     108//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
     109//      map[e]*=mul;
     110//     }
    85111  }
    86112 
    87   cout << T;
    88   cout << "\nRunning Dijkstra: ";
     113  PrintTime("GENLENGTHS",T);
     114
    89115  T.reset();
    90116  {
     
    92118    Dij.run(nodes[0]);
    93119  }
    94   cout << T;
    95 //   cout << "\nRunning MaxFlow: ";
    96 //   T.reset();
    97 //   {
    98 //    Graph::EdgeMap<int> flow(G);
     120  PrintTime("DIJKSTRA",T);
     121
     122  T.reset();
     123  {
     124   Graph::EdgeMap<int> flow(G);
    99125   
    100 //     MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
    101 //     MF.run(MF.NO_FLOW);
    102 //   }
    103 //   cout << T;
    104   cout << "\n";
     126    MaxFlowNoStack<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
     127    MF.run(MF.NO_FLOW);
     128  }
     129  PrintTime("PREFLOW",T);
     130
    105131}
Note: See TracChangeset for help on using the changeset viewer.