Changeset 78:ecc1171307be in lemon0.x for src/work/jacint/flow_test.cc
 Timestamp:
 02/16/04 17:15:58 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@101
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/flow_test.cc
r72 r78 3 3 #include <string> 4 4 5 #include <marci_list_graph.hh> 6 #include <marci_graph_traits.hh> 7 #include <marci_property_vector.hh> 8 #include <preflow_push_hl.hh> 9 #include <preflow_push_max_flow.hh> 10 #include <reverse_bfs.hh> 11 //#include <dijkstra.hh> 5 #include <list_graph.hh> 6 #include <preflow_push_hl.h> 7 #include <preflow_push_max_flow.h> 8 #include <reverse_bfs.h> 9 //#include <dijkstra.h> 12 10 13 11 using namespace marci; … … 16 14 int main (int, char*[]) 17 15 { 18 typedef graph_traits<list_graph>::node_iterator node_iterator; 19 typedef graph_traits<list_graph>::edge_iterator edge_iterator; 20 typedef graph_traits<list_graph>::each_node_iterator each_node_iterator; 21 typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator; 22 typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator; 23 typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator; 24 typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator; 25 26 list_graph flow_test; 16 typedef ListGraph::NodeIt NodeIt; 17 typedef ListGraph::EdgeIt EdgeIt; 18 typedef ListGraph::EachNodeIt EachNodeIt; 19 typedef ListGraph::EachEdgeIt EachEdgeIt; 20 typedef ListGraph::OutEdgeIt OutEdgeIt; 21 typedef ListGraph::InEdgeIt InEdgeIt; 22 23 ListGraph flow_test; 27 24 28 25 //Ahuja könyv példája, maxflowvalue=13 29 node_iterator s=flow_test.add_node();30 node_iterator v1=flow_test.add_node();31 node_iterator v2=flow_test.add_node();32 node_iterator v3=flow_test.add_node();33 node_iterator v4=flow_test.add_node();34 node_iterator v5=flow_test.add_node();35 node_iterator t=flow_test.add_node();36 37 node_property_vector<list_graph, std::string> node_name(flow_test);38 node_name.put(s, "s");39 node_name.put(v1, "v1");40 node_name.put(v2, "v2");41 node_name.put(v3, "v3");42 node_name.put(v4, "v4");43 node_name.put(v5, "v5");44 node_name.put(t, "t");45 46 edge_iterator s_v1=flow_test.add_edge(s, v1);47 edge_iterator s_v2=flow_test.add_edge(s, v2);48 edge_iterator s_v3=flow_test.add_edge(s, v3);49 edge_iterator v2_v4=flow_test.add_edge(v2, v4);50 edge_iterator v2_v5=flow_test.add_edge(v2, v5);51 edge_iterator v3_v5=flow_test.add_edge(v3, v5);52 edge_iterator v4_t=flow_test.add_edge(v4, t);53 edge_iterator v5_t=flow_test.add_edge(v5, t);54 edge_iterator v2_s=flow_test.add_edge(v2, s);55 56 edge_property_vector<list_graph,int> cap(flow_test);57 cap. put(s_v1, 0);58 cap. put(s_v2, 10);59 cap. put(s_v3, 10);60 cap. put(v2_v4, 5);61 cap. put(v2_v5, 8);62 cap. put(v3_v5, 5);63 cap. put(v4_t, 8);64 cap. put(v5_t, 8);65 cap. put(v2_s, 0);26 NodeIt s=flow_test.addNode(); 27 NodeIt v1=flow_test.addNode(); 28 NodeIt v2=flow_test.addNode(); 29 NodeIt v3=flow_test.addNode(); 30 NodeIt v4=flow_test.addNode(); 31 NodeIt v5=flow_test.addNode(); 32 NodeIt t=flow_test.addNode(); 33 34 ListGraph::NodeMap<std::string> Node_name(flow_test); 35 Node_name.set(s, "s"); 36 Node_name.set(v1, "v1"); 37 Node_name.set(v2, "v2"); 38 Node_name.set(v3, "v3"); 39 Node_name.set(v4, "v4"); 40 Node_name.set(v5, "v5"); 41 Node_name.set(t, "t"); 42 43 EdgeIt s_v1=flow_test.addEdge(s, v1); 44 EdgeIt s_v2=flow_test.addEdge(s, v2); 45 EdgeIt s_v3=flow_test.addEdge(s, v3); 46 EdgeIt v2_v4=flow_test.addEdge(v2, v4); 47 EdgeIt v2_v5=flow_test.addEdge(v2, v5); 48 EdgeIt v3_v5=flow_test.addEdge(v3, v5); 49 EdgeIt v4_t=flow_test.addEdge(v4, t); 50 EdgeIt v5_t=flow_test.addEdge(v5, t); 51 EdgeIt v2_s=flow_test.addEdge(v2, s); 52 53 ListGraph::EdgeMap<int> cap(flow_test); 54 cap.set(s_v1, 0); 55 cap.set(s_v2, 10); 56 cap.set(s_v3, 10); 57 cap.set(v2_v4, 5); 58 cap.set(v2_v5, 8); 59 cap.set(v3_v5, 5); 60 cap.set(v4_t, 8); 61 cap.set(v5_t, 8); 62 cap.set(v2_s, 0); 66 63 67 64 68 65 69 66 //Marci példája, maxflowvalue=23 70 /* node_iterator s=flow_test.add_node();71 node_iterator v1=flow_test.add_node();72 node_iterator v2=flow_test.add_node();73 node_iterator v3=flow_test.add_node();74 node_iterator v4=flow_test.add_node();75 node_iterator t=flow_test.add_node();76 node_iterator w=flow_test.add_node();77 78 79 node_property_vector<list_graph, std::string> node_name(flow_test);80 node_name.put(s, "s");81 node_name.put(v1, "v1");82 node_name.put(v2, "v2");83 node_name.put(v3, "v3");84 node_name.put(v4, "v4");85 node_name.put(t, "t");86 node_name.put(w, "w");87 88 edge_iterator s_v1=flow_test.add_edge(s, v1);89 edge_iterator s_v2=flow_test.add_edge(s, v2);90 edge_iterator v1_v2=flow_test.add_edge(v1, v2);91 edge_iterator v2_v1=flow_test.add_edge(v2, v1);92 edge_iterator v1_v3=flow_test.add_edge(v1, v3);93 edge_iterator v3_v2=flow_test.add_edge(v3, v2);94 edge_iterator v2_v4=flow_test.add_edge(v2, v4);95 edge_iterator v4_v3=flow_test.add_edge(v4, v3);96 edge_iterator v3_t=flow_test.add_edge(v3, t);97 edge_iterator v4_t=flow_test.add_edge(v4, t);98 edge_iterator v3_v3=flow_test.add_edge(v3, v3);99 edge_iterator s_w=flow_test.add_edge(s, w);100 // edge_iterator v2_s=flow_test.add_edge(v2, s);101 102 103 104 edge_property_vector<list_graph, int> cap(flow_test); //serves as length in dijkstra105 cap. put(s_v1, 16);106 cap. put(s_v2, 13);107 cap. put(v1_v2, 10);108 cap. put(v2_v1, 4);109 cap. put(v1_v3, 12);110 cap. put(v3_v2, 9);111 cap. put(v2_v4, 14);112 cap. put(v4_v3, 7);113 cap. put(v3_t, 20);114 cap. put(v4_t, 4);115 cap. put(v3_v3, 4);116 cap. put(s_w, 4);117 // cap. put(v2_s, 0);67 /* NodeIt s=flow_test.addNode(); 68 NodeIt v1=flow_test.addNode(); 69 NodeIt v2=flow_test.addNode(); 70 NodeIt v3=flow_test.addNode(); 71 NodeIt v4=flow_test.addNode(); 72 NodeIt t=flow_test.addNode(); 73 NodeIt w=flow_test.addNode(); 74 75 76 NodeMap<ListGraph, std::string> Node_name(flow_test); 77 Node_name.set(s, "s"); 78 Node_name.set(v1, "v1"); 79 Node_name.set(v2, "v2"); 80 Node_name.set(v3, "v3"); 81 Node_name.set(v4, "v4"); 82 Node_name.set(t, "t"); 83 Node_name.set(w, "w"); 84 85 EdgeIt s_v1=flow_test.addEdge(s, v1); 86 EdgeIt s_v2=flow_test.addEdge(s, v2); 87 EdgeIt v1_v2=flow_test.addEdge(v1, v2); 88 EdgeIt v2_v1=flow_test.addEdge(v2, v1); 89 EdgeIt v1_v3=flow_test.addEdge(v1, v3); 90 EdgeIt v3_v2=flow_test.addEdge(v3, v2); 91 EdgeIt v2_v4=flow_test.addEdge(v2, v4); 92 EdgeIt v4_v3=flow_test.addEdge(v4, v3); 93 EdgeIt v3_t=flow_test.addEdge(v3, t); 94 EdgeIt v4_t=flow_test.addEdge(v4, t); 95 EdgeIt v3_v3=flow_test.addEdge(v3, v3); 96 EdgeIt s_w=flow_test.addEdge(s, w); 97 // EdgeIt v2_s=flow_test.addEdge(v2, s); 98 99 100 101 EdgeMap<ListGraph, int> cap(flow_test); //serves as length in dijkstra 102 cap.set(s_v1, 16); 103 cap.set(s_v2, 13); 104 cap.set(v1_v2, 10); 105 cap.set(v2_v1, 4); 106 cap.set(v1_v3, 12); 107 cap.set(v3_v2, 9); 108 cap.set(v2_v4, 14); 109 cap.set(v4_v3, 7); 110 cap.set(v3_t, 20); 111 cap.set(v4_t, 4); 112 cap.set(v3_v3, 4); 113 cap.set(s_w, 4); 114 // cap.set(v2_s, 0); 118 115 119 116 */ 120 117 121 118 //pelda 3, maxflowvalue=4 122 /* node_iterator s=flow_test.add_node();123 node_iterator v1=flow_test.add_node();124 node_iterator v2=flow_test.add_node();125 node_iterator t=flow_test.add_node();126 node_iterator w=flow_test.add_node();127 128 node_property_vector<list_graph, std::string> node_name(flow_test);129 node_name.put(s, "s");130 node_name.put(v1, "v1");131 node_name.put(v2, "v2");132 node_name.put(t, "t");133 node_name.put(w, "w");134 135 edge_iterator s_v1=flow_test.add_edge(s, v1);136 edge_iterator v1_v2=flow_test.add_edge(v1, v2);137 edge_iterator v2_t=flow_test.add_edge(v2, t);138 edge_iterator v1_v1=flow_test.add_edge(v1, v1);139 edge_iterator s_w=flow_test.add_edge(s, w);140 141 142 edge_property_vector<list_graph, int> cap(flow_test);119 /* NodeIt s=flow_test.addNode(); 120 NodeIt v1=flow_test.addNode(); 121 NodeIt v2=flow_test.addNode(); 122 NodeIt t=flow_test.addNode(); 123 NodeIt w=flow_test.addNode(); 124 125 NodeMap<ListGraph, std::string> Node_name(flow_test); 126 Node_name.set(s, "s"); 127 Node_name.set(v1, "v1"); 128 Node_name.set(v2, "v2"); 129 Node_name.set(t, "t"); 130 Node_name.set(w, "w"); 131 132 EdgeIt s_v1=flow_test.addEdge(s, v1); 133 EdgeIt v1_v2=flow_test.addEdge(v1, v2); 134 EdgeIt v2_t=flow_test.addEdge(v2, t); 135 EdgeIt v1_v1=flow_test.addEdge(v1, v1); 136 EdgeIt s_w=flow_test.addEdge(s, w); 137 138 139 EdgeMap<ListGraph, int> cap(flow_test); 143 140 144 cap. put(s_v1, 16);145 cap. put(v1_v2, 10);146 cap. put(v2_t, 4);147 cap. put(v1_v1, 3);148 cap. put(s_w, 5);141 cap.set(s_v1, 16); 142 cap.set(v1_v2, 10); 143 cap.set(v2_t, 4); 144 cap.set(v1_v1, 3); 145 cap.set(s_w, 5); 149 146 */ 150 147 … … 154 151 std::cout << "Testing reverse_bfs..." << std::endl; 155 152 156 reverse_bfs< list_graph> bfs_test(flow_test, t);153 reverse_bfs<ListGraph> bfs_test(flow_test, t); 157 154 158 155 bfs_test.run(); 159 156 160 for ( each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {157 for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) { 161 158 std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl; 162 159 } … … 168 165 std::cout << "Testing preflow_push_hl..." << std::endl; 169 166 170 preflow_push_hl< list_graph, int> preflow_push_test(flow_test, s, t, cap);167 preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap); 171 168 172 169 preflow_push_test.run(); … … 174 171 std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl; 175 172 176 std::cout<< "The flow on edge sv1 is "<< preflow_push_test.flowonedge(s_v1) << "."<<std::endl;177 178 edge_property_vector<list_graph,int> flow=preflow_push_test.allflow();179 for ( each_edge_iterator e=flow_test.first_edge(); e.valid(); ++e) {180 std::cout <<"Flow on edge " << flow_test.tail(e) <<"" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;173 std::cout<< "The flow on Edge sv1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl; 174 175 ListGraph::EdgeMap<int> flow=preflow_push_test.allflow(); 176 for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) { 177 std::cout <<"Flow on Edge " << flow_test.tail(e) <<"" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl; 181 178 } 182 179 183 180 std::cout << "A minimum cut: " <<std::endl; 184 node_property_vector<list_graph,bool> mincut=preflow_push_test.mincut();185 186 for ( each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {187 if (mincut.get(v)) std::cout << node_name.get(v)<< " ";181 ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut(); 182 183 for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) { 184 if (mincut.get(v)) std::cout <<Node_name.get(v)<< " "; 188 185 } 189 186 … … 195 192 std::cout << "Testing preflow_push_max_flow..." << std::endl; 196 193 197 preflow_push_max_flow< list_graph, int> max_flow_test(flow_test, s, t, cap);194 preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap); 198 195 199 196 max_flow_test.run(); … … 202 199 203 200 std::cout << "A minimum cut: " <<std::endl; 204 node_property_vector<list_graph,bool> mincut2=max_flow_test.mincut();205 206 for ( each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {207 if (mincut2.get(v)) std::cout << node_name.get(v)<< " ";201 ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut(); 202 203 for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) { 204 if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " "; 208 205 } 209 206 … … 214 211 std::cout << "Testing dijkstra..." << std::endl; 215 212 216 node_iteratorroot=v2;217 218 dijkstra< list_graph, int> dijkstra_test(flow_test, root, cap);213 NodeIt root=v2; 214 215 dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap); 219 216 220 217 dijkstra_test.run(); 221 218 222 for ( each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {219 for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) { 223 220 if (dijkstra_test.reach(w)) { 224 221 std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w); 225 222 if (dijkstra_test.pred(w).valid()) { 226 std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <<std::endl;223 std::cout <<", a shortest path from the root ends with Edge " << dijkstra_test.pred(w) <<std::endl; 227 224 } else { 228 225 std::cout <<", this is the root."<<std::endl; }
Note: See TracChangeset
for help on using the changeset viewer.