Changeset 476:cfe550761745 in lemon0.x
 Timestamp:
 04/29/04 18:25:03 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@633
 Location:
 src/work
 Files:

 6 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/preflow.h
r472 r476 56 56 typename CapMap=typename Graph::template EdgeMap<Num>, 57 57 typename FlowMap=typename Graph::template EdgeMap<Num> > 58 class Preflow {58 class MaxFlow { 59 59 60 60 typedef typename Graph::Node Node; … … 93 93 }; 94 94 95 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,95 MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 96 96 FlowMap& _flow) : 97 97 g(&_G), s(_s), t(_t), capacity(&_capacity), … … 536 536 537 537 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 538 void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )538 void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe ) 539 539 { 540 540 … … 645 645 646 646 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 647 void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase1()647 void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1() 648 648 { 649 649 … … 709 709 710 710 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 711 bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()711 bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath() 712 712 { 713 713 ResGW res_graph(*g, *capacity, *flow); … … 765 765 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 766 766 template<typename MutableGraph> 767 bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()767 bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow() 768 768 { 769 769 typedef MutableGraph MG; … … 882 882 883 883 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 884 bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()884 bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() 885 885 { 886 886 bool _augment=false; 
src/work/marci/bipartite_graph_wrapper_test.cc
r409 r476 12 12 #include <graph_wrapper.h> 13 13 #include <maps.h> 14 #include < edmonds_karp.h>14 #include <preflow.h> 15 15 16 16 using namespace hugo; 
src/work/marci/bipartite_matching_try.cc
r465 r476 13 13 #include <graph_wrapper.h> 14 14 #include <maps.h> 15 #include <edmonds_karp.h>16 15 #include <preflow.h> 17 16 … … 181 180 ts.reset(); 182 181 stGW::EdgeMap<int> pre_flow(stgw); 183 Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >182 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 184 183 pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/); 185 184 pre_flow_test.run(); 
src/work/marci/lg_vs_sg.cc
r465 r476 7 7 #include <smart_graph.h> 8 8 #include <dimacs.h> 9 #include <edmonds_karp.h>10 9 #include <preflow.h> 11 10 #include <time_measure.h> … … 35 34 Timer ts; 36 35 Graph::EdgeMap<int> flow(G); //0 flow 37 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >38 pre_flow_test(G, s, t, cap, flow/*, true*/);39 36 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 40 max_flow_test(G, s, t, cap, flow );37 max_flow_test(G, s, t, cap, flow/*, true*/); 41 38 42 39 std::cout << "ListGraph ..." << std::endl; … … 45 42 std::cout << "preflow ..." << std::endl; 46 43 ts.reset(); 47 pre_flow_test.run();44 max_flow_test.run(); 48 45 std::cout << "elapsed time: " << ts << std::endl; 49 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;46 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 50 47 } 51 48 … … 61 58 } 62 59 63 {64 std::cout << "faster physical blocking flow augmentation ..." << std::endl;65 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);66 ts.reset();67 int i=0;68 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }69 std::cout << "elapsed time: " << ts << std::endl;70 std::cout << "number of augmentation phases: " << i << std::endl;71 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;72 }60 // { 61 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; 62 // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 63 // ts.reset(); 64 // int i=0; 65 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } 66 // std::cout << "elapsed time: " << ts << std::endl; 67 // std::cout << "number of augmentation phases: " << i << std::endl; 68 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 69 // } 73 70 74 71 { … … 109 106 Timer ts; 110 107 Graph::EdgeMap<int> flow(G); //0 flow 111 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >112 pre_flow_test(G, s, t, cap, flow/*, true*/);113 108 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 114 max_flow_test(G, s, t, cap, flow); 109 max_flow_test(G, s, t, cap, flow/*, true*/); 110 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 111 // max_flow_test(G, s, t, cap, flow); 115 112 116 113 std::cout << "SmatrGraph ..." << std::endl; … … 120 117 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 121 118 ts.reset(); 122 pre_flow_test.run();119 max_flow_test.run(); 123 120 std::cout << "elapsed time: " << ts << std::endl; 124 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;121 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 125 122 } 126 123 … … 136 133 } 137 134 138 {139 std::cout << "faster physical blocking flow augmentation ..." << std::endl;140 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);141 ts.reset();142 int i=0;143 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }144 std::cout << "elapsed time: " << ts << std::endl;145 std::cout << "number of augmentation phases: " << i << std::endl;146 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;147 }135 // { 136 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; 137 // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 138 // ts.reset(); 139 // int i=0; 140 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } 141 // std::cout << "elapsed time: " << ts << std::endl; 142 // std::cout << "number of augmentation phases: " << i << std::endl; 143 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 144 // } 148 145 149 146 { 
src/work/marci/makefile
r433 r476 5 5 6 6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo 7 BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try7 BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try 8 8 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda 9 9 
src/work/marci/max_flow_demo.cc
r475 r476 6 6 #include <smart_graph.h> 7 7 #include <dimacs.h> 8 //#include <edmonds_karp.h>9 8 #include <time_measure.h> 10 9 //#include <graph_wrapper.h> … … 71 70 Timer ts; 72 71 Graph::EdgeMap<int> flow(G); //0 flow 73 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 74 pre_flow_test(G, s, t, cap, flow/*, true*/); 75 // Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 76 // pre_flow_ize(G, s, t, cap, flow/*, false*/); 77 // PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 78 // pre_flow_res(G, s, t, cap, flow/*, true*/); 79 //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 80 // max_flow_test(G, s, t, cap, flow); 72 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 73 max_flow_test(G, s, t, cap, flow); 81 74 82 75 { 83 76 std::cout << "preflow ..." << std::endl; 84 77 ts.reset(); 85 pre_flow_test.run();78 max_flow_test.run(); 86 79 std::cout << "elapsed time: " << ts << std::endl; 87 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;80 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 88 81 } 89 82 … … 92 85 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 93 86 ts.reset(); 94 pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);87 max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); 95 88 std::cout << "elapsed time: " << ts << std::endl; 96 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;89 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 97 90 } 98 91 … … 111 104 ts.reset(); 112 105 int i=0; 113 while ( pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }106 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } 114 107 std::cout << "elapsed time: " << ts << std::endl; 115 108 std::cout << "number of augmentation phases: " << i << std::endl; 116 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;109 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 117 110 } 118 111 … … 133 126 ts.reset(); 134 127 int i=0; 135 while ( pre_flow_test.augmentOnBlockingFlow2()) { ++i; }128 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 136 129 std::cout << "elapsed time: " << ts << std::endl; 137 130 std::cout << "number of augmentation phases: " << i << std::endl; 138 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;131 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 139 132 } 140 133 … … 144 137 ts.reset(); 145 138 int i=0; 146 while ( pre_flow_test.augmentOnShortestPath()) { ++i; }139 while (max_flow_test.augmentOnShortestPath()) { ++i; } 147 140 std::cout << "elapsed time: " << ts << std::endl; 148 141 std::cout << "number of augmentation phases: " << i << std::endl; 149 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;142 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 150 143 } 151 144
Note: See TracChangeset
for help on using the changeset viewer.