COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
05/19/04 18:06:57 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@846
Message:

max_flow.h: status flags for actMinCut
leda_graph_wrapper.h: NodeMapWrapper?, EdgeMapWrapper?

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/max_flow_demo.cc

    r642 r646  
    7373  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    7474    max_flow_test(g, s, t, cap, flow);
     75  Graph::NodeMap<bool> cut(g);
    7576
    7677  {
     
    8081    std::cout << "elapsed time: " << ts << std::endl;
    8182    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     83    max_flow_test.actMinCut(cut);
     84
     85    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     86      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     87        std::cout << "Slackness does not hold!" << std::endl;
     88      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     89        std::cout << "Slackness does not hold!" << std::endl;
     90    }
    8291  }
    8392
     
    8998    std::cout << "elapsed time: " << ts << std::endl;
    9099    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     100
     101    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     102      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     103        std::cout << "Slackness does not hold!" << std::endl;
     104      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     105        std::cout << "Slackness does not hold!" << std::endl;
     106    }
    91107  }
    92108
     
    109125    std::cout << "number of augmentation phases: " << i << std::endl;
    110126    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     127
     128    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     129      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     130        std::cout << "Slackness does not hold!" << std::endl;
     131      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     132        std::cout << "Slackness does not hold!" << std::endl;
     133    }
    111134  }
    112135
     
    131154    std::cout << "number of augmentation phases: " << i << std::endl;
    132155    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     156
     157    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     158      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     159        std::cout << "Slackness does not hold!" << std::endl;
     160      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     161        std::cout << "Slackness does not hold!" << std::endl;
     162    }
    133163  }
    134164
     
    142172    std::cout << "number of augmentation phases: " << i << std::endl;
    143173    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    144   }
    145 
     174
     175    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     176      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     177        std::cout << "Slackness does not hold!" << std::endl;
     178      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     179        std::cout << "Slackness does not hold!" << std::endl;
     180    }
     181  }
     182
     183  {
     184    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
     185    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     186    ts.reset();
     187    int i=0;
     188    while (max_flow_test.augmentOnShortestPath2()) { ++i; }
     189    std::cout << "elapsed time: " << ts << std::endl;
     190    std::cout << "number of augmentation phases: " << i << std::endl;
     191    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     192
     193    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     194      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     195        std::cout << "Slackness does not hold!" << std::endl;
     196      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     197        std::cout << "Slackness does not hold!" << std::endl;
     198    }
     199  }
    146200
    147201  return 0;
Note: See TracChangeset for help on using the changeset viewer.