COIN-OR::LEMON - Graph Library

Changeset 715:665689d86225 in lemon-0.x


Ignore:
Timestamp:
07/20/04 16:31:24 (20 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@967
Message:

trying if without stl stack we are faster

Location:
src/work/jacint
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/makefile

    r535 r715  
    1 BINARIES = max_matching
    2 INCLUDEDIRS= -I../../include -I.. -I../{klao,marci,jacint,alpar,johanna,akos}
     1BINARIES = max_flow_test
     2INCLUDEDIRS= -I../../include -I../.. -I.. -I../{klao,marci,jacint,alpar,johanna,akos}
    33include ../makefile
  • src/work/jacint/max_flow_test.cc

    r588 r715  
    11#include <iostream>
    22
    3 #include <list_graph.h>
    4 #include <dimacs.h>
     3#include <hugo/list_graph.h>
     4#include <hugo/dimacs.h>
    55#include <max_flow.h>
    6 #include <time_measure.h>
     6#include <max_flow_no_stack.h>
     7#include <hugo/time_measure.h>
    78
    89using namespace hugo;
     
    2627           << std::endl<<std::endl;
    2728
    28   Graph::EdgeMap<int> flow(G,0);
    29   MaxFlow<Graph, int> max_flow_test(G, s, t, cap, flow);
     29  Graph::EdgeMap<int> flowstack(G,0);
     30  MaxFlow<Graph, int> max_flow_test(G, s, t, cap, flowstack);
    3031  ts.reset();
    3132  max_flow_test.run();
    32   std::cout << "Elapsed time of run(): " << std::endl
     33  std::cout << "Elapsed time of run() with stl stack: " << std::endl
     34            <<ts << std::endl;
     35
     36  Graph::EdgeMap<int> flow(G,0);
     37  MaxFlowNoStack<Graph, int> max_flow_test_no_stack(G, s, t, cap, flow);
     38  ts.reset();
     39  max_flow_test_no_stack.run();
     40  std::cout << "Elapsed time of run() without stack: " << std::endl
    3341            <<ts << std::endl;
    3442 
    3543  Graph::NodeMap<bool> mincut(G);
    36   max_flow_test.minMinCut(mincut);
     44  max_flow_test_no_stack.minMinCut(mincut);
    3745  int min_min_cut_value=0;
    3846  EdgeIt e;
     
    4250
    4351  Graph::NodeMap<bool> cut(G);
    44   max_flow_test.minCut(cut);
     52  max_flow_test_no_stack.minCut(cut);
    4553  int min_cut_value=0;
    4654  for(G.first(e); G.valid(e); G.next(e)) {
     
    5058
    5159  Graph::NodeMap<bool> maxcut(G);
    52   max_flow_test.maxMinCut(maxcut);
     60  max_flow_test_no_stack.maxMinCut(maxcut);
    5361  int max_min_cut_value=0;
    5462  for(G.first(e); G.valid(e); G.next(e)) {
     
    5765      }
    5866
    59   std::cout << "\n Checking the result: " <<std::endl; 
    60   std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;
     67  std::cout << "\n Checking the result without stack: " <<std::endl; 
     68  std::cout << "Flow value: "<< max_flow_test_no_stack.flowValue() << std::endl;
    6169  std::cout << "Min cut value: "<< min_cut_value << std::endl;
    6270  std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
     
    6472    std::endl;
    6573
    66   if ( max_flow_test.flowValue() == min_cut_value &&
     74  if ( max_flow_test_no_stack.flowValue() == min_cut_value &&
    6775       min_cut_value == min_min_cut_value &&
    6876       min_min_cut_value == max_min_cut_value )
    6977    std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; 
    7078
    71 
     79  /*
    7280
    7381  Graph::EdgeMap<int> flow2(G,0);
     
    153161       min_min_cut_value3 == max_min_cut_value3 )
    154162    std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; 
     163  */
    155164 
    156165  return 0;
Note: See TracChangeset for help on using the changeset viewer.