Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/max_flow_demo.cc
changeset 1208 f486d30e4e7b
parent 921 818510fa3d99
equal deleted inserted replaced
15:a9c0a57530bb 16:1080f66ff7a8 
    45     std::cout << "elapsed time: " << ts << std::endl;
 
    45     std::cout << "elapsed time: " << ts << std::endl;
 
    46     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    46     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    47     max_flow_test.minCut(cut);
 
    47     max_flow_test.minCut(cut);
 
    48 
    48 
    49     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
    49     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
    50       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
    50       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
    51 	std::cout << "Slackness does not hold!" << std::endl;
 
    51 	std::cout << "Slackness does not hold!" << std::endl;
 
    52       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
    52       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
    53 	std::cout << "Slackness does not hold!" << std::endl;
 
    53 	std::cout << "Slackness does not hold!" << std::endl;
 
    54     }
 
    54     }
 
    55   }
 
    55   }
 
    56 
    56 
    57   {
 
    57   {
 
    61     max_flow_test.run(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
 
    61     max_flow_test.run(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
 
    62     std::cout << "elapsed time: " << ts << std::endl;
 
    62     std::cout << "elapsed time: " << ts << std::endl;
 
    63     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    63     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    64 
    64 
    65     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
    65     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
    66       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
    66       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
    67 	std::cout << "Slackness does not hold!" << std::endl;
 
    67 	std::cout << "Slackness does not hold!" << std::endl;
 
    68       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
    68       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
    69 	std::cout << "Slackness does not hold!" << std::endl;
 
    69 	std::cout << "Slackness does not hold!" << std::endl;
 
    70     }
 
    70     }
 
    71   }
 
    71   }
 
    72 
    72 
    73 //   {
 
    73 //   {
 
    88     std::cout << "elapsed time: " << ts << std::endl;
 
    88     std::cout << "elapsed time: " << ts << std::endl;
 
    89     std::cout << "number of augmentation phases: " << i << std::endl; 
    89     std::cout << "number of augmentation phases: " << i << std::endl; 
    90     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
 
    90     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
 
    91 
    91 
    92     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
    92     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
    93       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
    93       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
    94 	std::cout << "Slackness does not hold!" << std::endl;
 
    94 	std::cout << "Slackness does not hold!" << std::endl;
 
    95       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
    95       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
    96 	std::cout << "Slackness does not hold!" << std::endl;
 
    96 	std::cout << "Slackness does not hold!" << std::endl;
 
    97     }
 
    97     }
 
    98   }
 
    98   }
 
    99 
    99 
   100   {
 
   100   {
 
   106     std::cout << "elapsed time: " << ts << std::endl;
 
   106     std::cout << "elapsed time: " << ts << std::endl;
 
   107     std::cout << "number of augmentation phases: " << i << std::endl; 
   107     std::cout << "number of augmentation phases: " << i << std::endl; 
   108     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
 
   108     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
 
   109 
   109 
   110     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
   110     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
   111       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
   111       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
   112 	std::cout << "Slackness does not hold!" << std::endl;
 
   112 	std::cout << "Slackness does not hold!" << std::endl;
 
   113       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
   113       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
   114 	std::cout << "Slackness does not hold!" << std::endl;
 
   114 	std::cout << "Slackness does not hold!" << std::endl;
 
   115     }
 
   115     }
 
   116   }
 
   116   }
 
   117 
   117 
   118   {
 
   118   {
 
   124     std::cout << "elapsed time: " << ts << std::endl;
 
   124     std::cout << "elapsed time: " << ts << std::endl;
 
   125     std::cout << "number of augmentation phases: " << i << std::endl; 
   125     std::cout << "number of augmentation phases: " << i << std::endl; 
   126     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
 
   126     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
 
   127 
   127 
   128     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
   128     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
   129       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
   129       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
   130 	std::cout << "Slackness does not hold!" << std::endl;
 
   130 	std::cout << "Slackness does not hold!" << std::endl;
 
   131       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
   131       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
   132 	std::cout << "Slackness does not hold!" << std::endl;
 
   132 	std::cout << "Slackness does not hold!" << std::endl;
 
   133     }
 
   133     }
 
   134   }
 
   134   }
 
   135 
   135 
   136   {
 
   136   {
 
   142     std::cout << "elapsed time: " << ts << std::endl;
 
   142     std::cout << "elapsed time: " << ts << std::endl;
 
   143     std::cout << "number of augmentation phases: " << i << std::endl; 
   143     std::cout << "number of augmentation phases: " << i << std::endl; 
   144     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
 
   144     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
 
   145 
   145 
   146     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
   146     for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
 
   147       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
   147       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
   148 	std::cout << "Slackness does not hold!" << std::endl;
 
   148 	std::cout << "Slackness does not hold!" << std::endl;
 
   149       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
   149       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
   150 	std::cout << "Slackness does not hold!" << std::endl;
 
   150 	std::cout << "Slackness does not hold!" << std::endl;
 
   151     }
 
   151     }
 
   152   }
 
   152   }
 
   153 
   153 
   154   return 0;
 
   154   return 0;
lemon-0.x