1.1 --- a/src/work/marci/max_flow_demo.cc	Mon May 17 15:11:05 2004 +0000
     1.2 +++ b/src/work/marci/max_flow_demo.cc	Wed May 19 16:06:57 2004 +0000
     1.3 @@ -72,6 +72,7 @@
     1.4    Graph::EdgeMap<int> flow(g); //0 flow
     1.5    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
     1.6      max_flow_test(g, s, t, cap, flow);
     1.7 +  Graph::NodeMap<bool> cut(g);
     1.8  
     1.9    {
    1.10      std::cout << "preflow ..." << std::endl;
    1.11 @@ -79,6 +80,14 @@
    1.12      max_flow_test.run();
    1.13      std::cout << "elapsed time: " << ts << std::endl;
    1.14      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    1.15 +    max_flow_test.actMinCut(cut);
    1.16 +
    1.17 +    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
    1.18 +      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
    1.19 +	std::cout << "Slackness does not hold!" << std::endl;
    1.20 +      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
    1.21 +	std::cout << "Slackness does not hold!" << std::endl;
    1.22 +    }
    1.23    }
    1.24  
    1.25    {
    1.26 @@ -88,6 +97,13 @@
    1.27      max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
    1.28      std::cout << "elapsed time: " << ts << std::endl;
    1.29      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    1.30 +
    1.31 +    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
    1.32 +      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
    1.33 +	std::cout << "Slackness does not hold!" << std::endl;
    1.34 +      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
    1.35 +	std::cout << "Slackness does not hold!" << std::endl;
    1.36 +    }
    1.37    }
    1.38  
    1.39  //   {
    1.40 @@ -108,6 +124,13 @@
    1.41      std::cout << "elapsed time: " << ts << std::endl;
    1.42      std::cout << "number of augmentation phases: " << i << std::endl; 
    1.43      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    1.44 +
    1.45 +    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
    1.46 +      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
    1.47 +	std::cout << "Slackness does not hold!" << std::endl;
    1.48 +      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
    1.49 +	std::cout << "Slackness does not hold!" << std::endl;
    1.50 +    }
    1.51    }
    1.52  
    1.53  //   {
    1.54 @@ -130,6 +153,13 @@
    1.55      std::cout << "elapsed time: " << ts << std::endl;
    1.56      std::cout << "number of augmentation phases: " << i << std::endl; 
    1.57      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    1.58 +
    1.59 +    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
    1.60 +      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
    1.61 +	std::cout << "Slackness does not hold!" << std::endl;
    1.62 +      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
    1.63 +	std::cout << "Slackness does not hold!" << std::endl;
    1.64 +    }
    1.65    }
    1.66  
    1.67    {
    1.68 @@ -141,8 +171,32 @@
    1.69      std::cout << "elapsed time: " << ts << std::endl;
    1.70      std::cout << "number of augmentation phases: " << i << std::endl; 
    1.71      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    1.72 +
    1.73 +    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
    1.74 +      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
    1.75 +	std::cout << "Slackness does not hold!" << std::endl;
    1.76 +      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
    1.77 +	std::cout << "Slackness does not hold!" << std::endl;
    1.78 +    }
    1.79    }
    1.80  
    1.81 +  {
    1.82 +    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    1.83 +    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    1.84 +    ts.reset();
    1.85 +    int i=0;
    1.86 +    while (max_flow_test.augmentOnShortestPath2()) { ++i; }
    1.87 +    std::cout << "elapsed time: " << ts << std::endl;
    1.88 +    std::cout << "number of augmentation phases: " << i << std::endl; 
    1.89 +    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    1.90 +
    1.91 +    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
    1.92 +      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
    1.93 +	std::cout << "Slackness does not hold!" << std::endl;
    1.94 +      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
    1.95 +	std::cout << "Slackness does not hold!" << std::endl;
    1.96 +    }
    1.97 +  }
    1.98  
    1.99    return 0;
   1.100  }