alpar@906: /* -*- C++ -*- alpar@921: * src/test/preflow_test.cc - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: jacint@833: #include klao@858: #include klao@858: jacint@833: #include "test_tools.h" alpar@921: #include alpar@921: #include alpar@921: #include klao@959: #include klao@959: #include alpar@855: alpar@921: using namespace lemon; jacint@833: jacint@833: void check_Preflow() jacint@833: { jacint@833: typedef int VType; klao@959: typedef concept::StaticGraph Graph; jacint@833: jacint@833: typedef Graph::Node Node; jacint@833: typedef Graph::Edge Edge; klao@959: typedef concept::ReadMap CapMap; klao@959: typedef concept::ReadWriteMap FlowMap; klao@959: typedef concept::ReadWriteMap CutMap; jacint@833: jacint@833: typedef Preflow PType; jacint@833: marci@940: Graph g; jacint@833: Node n; jacint@833: CapMap cap; jacint@833: FlowMap flow; jacint@833: CutMap cut; jacint@833: marci@940: PType preflow_test(g,n,n,cap,flow); jacint@833: jacint@833: preflow_test.run(); jacint@833: preflow_test.flowValue(); alpar@1222: preflow_test.source(n); alpar@1222: preflow_test.flowMap(flow); jacint@833: jacint@833: preflow_test.phase1(PType::NO_FLOW); jacint@833: preflow_test.minCut(cut); jacint@833: jacint@833: preflow_test.phase2(); alpar@1222: preflow_test.target(n); alpar@1222: preflow_test.capacityMap(cap); jacint@833: preflow_test.minMinCut(cut); jacint@833: preflow_test.maxMinCut(cut); jacint@833: } jacint@833: marci@940: int cut_value ( SmartGraph& g, SmartGraph::NodeMap& cut, jacint@833: SmartGraph::EdgeMap& cap) { jacint@833: jacint@833: int c=0; marci@940: for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) { alpar@986: if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; jacint@833: } jacint@833: return c; jacint@833: } jacint@833: jacint@833: int main() { jacint@833: jacint@833: typedef SmartGraph Graph; jacint@833: alpar@842: typedef Graph::Node Node; jacint@833: typedef Graph::NodeIt NodeIt; jacint@833: typedef Graph::EdgeIt EdgeIt; jacint@833: typedef Graph::EdgeMap CapMap; jacint@833: typedef Graph::EdgeMap FlowMap; jacint@833: typedef Graph::NodeMap CutMap; jacint@833: jacint@833: typedef Preflow PType; jacint@833: klao@859: std::string f_name; alpar@1215: if( getenv("srcdir") ) alpar@1215: f_name = std::string(getenv("srcdir")); alpar@1215: else f_name = "."; alpar@1215: f_name += "/preflow_graph.dim"; alpar@855: klao@858: std::ifstream file(f_name.c_str()); alpar@855: klao@858: check(file, "Input file '" << f_name << "' not found."); jacint@833: marci@940: Graph g; alpar@842: Node s, t; marci@940: CapMap cap(g); marci@940: readDimacs(file, g, cap, s, t); jacint@833: marci@940: FlowMap flow(g,0); jacint@887: jacint@833: jacint@887: marci@940: PType preflow_test(g, s, t, cap, flow); jacint@833: preflow_test.run(PType::ZERO_FLOW); jacint@887: marci@940: CutMap min_cut(g,false); marci@940: preflow_test.minCut(min_cut); marci@940: int min_cut_value=cut_value(g,min_cut,cap); jacint@833: marci@940: CutMap min_min_cut(g,false); marci@940: preflow_test.minMinCut(min_min_cut); marci@940: int min_min_cut_value=cut_value(g,min_min_cut,cap); jacint@833: marci@940: CutMap max_min_cut(g,false); marci@940: preflow_test.maxMinCut(max_min_cut); marci@940: int max_min_cut_value=cut_value(g,max_min_cut,cap); jacint@833: jacint@833: check(preflow_test.flowValue() == min_cut_value && jacint@833: min_cut_value == min_min_cut_value && jacint@833: min_min_cut_value == max_min_cut_value, jacint@833: "The max flow value is not equal to the three min cut values."); jacint@833: jacint@833: int flow_value=preflow_test.flowValue(); jacint@833: jacint@833: jacint@887: marci@940: for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; alpar@1222: preflow_test.capacityMap(cap); alpar@842: jacint@833: preflow_test.phase1(PType::PRE_FLOW); jacint@833: marci@940: CutMap min_cut1(g,false); marci@940: preflow_test.minCut(min_cut1); marci@940: min_cut_value=cut_value(g,min_cut1,cap); jacint@833: jacint@833: check(preflow_test.flowValue() == min_cut_value && jacint@833: min_cut_value == 2*flow_value, jacint@833: "The max flow value or the min cut value is wrong."); jacint@833: jacint@833: preflow_test.phase2(); jacint@833: marci@940: CutMap min_cut2(g,false); marci@940: preflow_test.minCut(min_cut2); marci@940: min_cut_value=cut_value(g,min_cut2,cap); jacint@833: marci@940: CutMap min_min_cut2(g,false); marci@940: preflow_test.minMinCut(min_min_cut2); marci@940: min_min_cut_value=cut_value(g,min_min_cut2,cap); jacint@833: marci@940: preflow_test.maxMinCut(max_min_cut); marci@940: max_min_cut_value=cut_value(g,max_min_cut,cap); jacint@833: jacint@833: check(preflow_test.flowValue() == min_cut_value && jacint@833: min_cut_value == min_min_cut_value && jacint@833: min_min_cut_value == max_min_cut_value && jacint@833: min_cut_value == 2*flow_value, jacint@833: "The max flow value or the three min cut values were not doubled"); jacint@833: jacint@887: jacint@887: marci@940: EdgeIt e(g); jacint@887: for( int i=1; i==10; ++i ) { jacint@887: flow.set(e,0); jacint@833: ++e; jacint@833: } jacint@833: alpar@1222: preflow_test.flowMap(flow); jacint@887: marci@940: NodeIt tmp1(g,s); jacint@887: ++tmp1; jacint@887: if ( tmp1 != INVALID ) s=tmp1; jacint@887: marci@940: NodeIt tmp2(g,t); jacint@887: ++tmp2; jacint@887: if ( tmp2 != INVALID ) t=tmp2; jacint@887: alpar@1222: preflow_test.source(s); alpar@1222: preflow_test.target(t); jacint@887: jacint@833: preflow_test.run(); jacint@833: marci@940: CutMap min_cut3(g,false); marci@940: preflow_test.minCut(min_cut3); marci@940: min_cut_value=cut_value(g,min_cut3,cap); jacint@833: marci@940: CutMap min_min_cut3(g,false); marci@940: preflow_test.minMinCut(min_min_cut3); marci@940: min_min_cut_value=cut_value(g,min_min_cut3,cap); jacint@833: marci@940: preflow_test.maxMinCut(max_min_cut); marci@940: max_min_cut_value=cut_value(g,max_min_cut,cap); jacint@833: jacint@833: check(preflow_test.flowValue() == min_cut_value && jacint@833: min_cut_value == min_min_cut_value && jacint@833: min_min_cut_value == max_min_cut_value, jacint@833: "The max flow value or the three min cut values are incorrect."); jacint@833: }