Changeset 331:f5461f8bc59b in lemon0.x for src/work/athos/pf_demo.cc
 Timestamp:
 04/15/04 19:03:44 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@449
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/pf_demo.cc
r201 r331 3 3 #include <string> 4 4 5 #include "list_graph.h h"6 #include "marci_graph_traits.hh"5 #include "list_graph.h" 6 //#include "marci_graph_traits.hh" 7 7 //#include "marci_property_vector.hh" 8 8 #include "preflow_push.hh" … … 14 14 { 15 15 16 17 typedef ListGraph::NodeIt NodeIt; 18 typedef ListGraph::EdgeIt EdgeIt; 19 /* 20 typedef ListGraph::EachNodeIt EachNodeIt; 21 typedef ListGraph::EachEdgeIt EachEdgeIt; 22 typedef ListGraph::OutEdgeIt OutEdgeIt; 23 typedef ListGraph::InEdgeIt InEdgeIt; 24 typedef ListGraph::SymEdgeIt SymEdgeIt; 25 */ 26 ListGraph flowG; 16 typedef ListGraph::Node Node; 17 typedef ListGraph::Edge Edge; 18 19 ListGraph graph; 27 20 28 21 /* … … 30 23 31 24 32 NodeIt s= flowG.addNode();33 NodeIt v1= flowG.addNode();34 NodeIt v2= flowG.addNode();35 NodeIt v3= flowG.addNode();36 NodeIt v4= flowG.addNode();37 NodeIt t= flowG.addNode();25 NodeIt s=graph.addNode(); 26 NodeIt v1=graph.addNode(); 27 NodeIt v2=graph.addNode(); 28 NodeIt v3=graph.addNode(); 29 NodeIt v4=graph.addNode(); 30 NodeIt t=graph.addNode(); 38 31 39 32 40 EdgeIt s_v1= flowG.addEdge(s, v1);41 EdgeIt s_v2= flowG.addEdge(s, v2);42 EdgeIt v1_v2= flowG.addEdge(v1, v2);43 EdgeIt v2_v1= flowG.addEdge(v2, v1);44 EdgeIt v1_v3= flowG.addEdge(v1, v3);45 EdgeIt v3_v2= flowG.addEdge(v3, v2);46 EdgeIt v2_v4= flowG.addEdge(v2, v4);47 EdgeIt v4_v3= flowG.addEdge(v4, v3);48 EdgeIt v3_t= flowG.addEdge(v3, t);49 EdgeIt v4_t= flowG.addEdge(v4, t);33 EdgeIt s_v1=graph.addEdge(s, v1); 34 EdgeIt s_v2=graph.addEdge(s, v2); 35 EdgeIt v1_v2=graph.addEdge(v1, v2); 36 EdgeIt v2_v1=graph.addEdge(v2, v1); 37 EdgeIt v1_v3=graph.addEdge(v1, v3); 38 EdgeIt v3_v2=graph.addEdge(v3, v2); 39 EdgeIt v2_v4=graph.addEdge(v2, v4); 40 EdgeIt v4_v3=graph.addEdge(v4, v3); 41 EdgeIt v3_t=graph.addEdge(v3, t); 42 EdgeIt v4_t=graph.addEdge(v4, t); 50 43 51 ListGraph::EdgeMap<int> cap(flowG);44 ListGraph::EdgeMap<int> length(graph); 52 45 53 cap.set(s_v1, 16);54 cap.set(s_v2, 13);55 cap.set(v1_v2, 10);56 cap.set(v2_v1, 4);57 cap.set(v1_v3, 12);58 cap.set(v3_v2, 9);59 cap.set(v2_v4, 14);60 cap.set(v4_v3, 7);61 cap.set(v3_t, 20);62 cap.set(v4_t, 4);46 length.set(s_v1, 16); 47 length.set(s_v2, 13); 48 length.set(v1_v2, 10); 49 length.set(v2_v1, 4); 50 length.set(v1_v3, 12); 51 length.set(v3_v2, 9); 52 length.set(v2_v4, 14); 53 length.set(v4_v3, 7); 54 length.set(v3_t, 20); 55 length.set(v4_t, 4); 63 56 */ 64 57 … … 66 59 //Ahuja könyv példája 67 60 68 Node It s=flowG.addNode();69 Node It v2=flowG.addNode();70 Node It v3=flowG.addNode();71 Node It v4=flowG.addNode();72 Node It v5=flowG.addNode();73 Node It t=flowG.addNode();61 Node s=graph.addNode(); 62 Node v2=graph.addNode(); 63 Node v3=graph.addNode(); 64 Node v4=graph.addNode(); 65 Node v5=graph.addNode(); 66 Node t=graph.addNode(); 74 67 75 Edge It s_v2=flowG.addEdge(s, v2);76 Edge It s_v3=flowG.addEdge(s, v3);77 Edge It v2_v4=flowG.addEdge(v2, v4);78 Edge It v2_v5=flowG.addEdge(v2, v5);79 Edge It v3_v5=flowG.addEdge(v3, v5);80 Edge It v4_t=flowG.addEdge(v4, t);81 Edge It v5_t=flowG.addEdge(v5, t);68 Edge s_v2=graph.addEdge(s, v2); 69 Edge s_v3=graph.addEdge(s, v3); 70 Edge v2_v4=graph.addEdge(v2, v4); 71 Edge v2_v5=graph.addEdge(v2, v5); 72 Edge v3_v5=graph.addEdge(v3, v5); 73 Edge v4_t=graph.addEdge(v4, t); 74 Edge v5_t=graph.addEdge(v5, t); 82 75 83 76 //Kis modositas 84 //edge_iterator v2_s= flowG.add_edge(v2, s);77 //edge_iterator v2_s=graph.add_edge(v2, s); 85 78 86 ListGraph::EdgeMap<int> cap(flowG);79 ListGraph::EdgeMap<int> length(graph); 87 80 88 cap.set(s_v2, 10);89 cap.set(s_v3, 10);90 cap.set(v2_v4, 5);91 cap.set(v2_v5, 8);92 cap.set(v3_v5, 5);93 cap.set(v4_t, 8);94 cap.set(v5_t, 8);81 length.set(s_v2, 10); 82 length.set(s_v3, 10); 83 length.set(v2_v4, 5); 84 length.set(v2_v5, 8); 85 length.set(v3_v5, 5); 86 length.set(v4_t, 8); 87 length.set(v5_t, 8); 95 88 96 89 //Kis modositas 97 //cap.put(v2_s, 100); 98 90 //length.put(v2_s, 100); 99 91 100 92 101 93 102 /*Egyszerû példa103 NodeIt s=flow_test.add_node();104 NodeIt v1=flow_test.add_node();105 NodeIt v2=flow_test.add_node();106 NodeIt t=flow_test.add_node();107 108 node_property_vector<list_graph, std::string> node_name(flow_test);109 node_name.put(s, "s");110 node_name.put(v1, "v1");111 node_name.put(v2, "v2");112 node_name.put(t, "t");113 114 edge_iterator s_v1=flow_test.add_edge(s, v1);115 edge_iterator v1_v2=flow_test.add_edge(v1, v2);116 edge_iterator v2_t=flow_test.add_edge(v2, t);117 118 edge_property_vector<list_graph, int> cap(flow_test);119 120 cap.put(s_v1, 16);121 cap.put(v1_v2, 10);122 cap.put(v2_t, 4);123 */124 125 94 std::cout << "preflowpush algorithm test..." << std::endl; 126 95 127 /*128 std::cout << "on directed graph graph" << std::endl; //<< flow_test;129 std::cout << "names and capacity values" << std::endl;130 for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) {131 std::cout << node_name.get(i) << ": ";132 std::cout << "out edges: ";133 for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)134 std::cout << node_name.get(flow_test.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flow_test.head(j)) << " ";135 std::cout << "in edges: ";136 for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)137 std::cout << node_name.get(flow_test.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flow_test.head(j)) << " ";138 std::cout << std::endl;139 }140 */141 96 142 //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) { 143 // std::cout << i << " "; 144 //} 145 146 preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap); 97 preflow_push<ListGraph, int> preflow_push_test(graph, s, t, length); 147 98 cout << preflow_push_test.run()<<endl; 148 99 … … 152 103 return 0; 153 104 } 154 155 156 157 158 159 160 161 162
Note: See TracChangeset
for help on using the changeset viewer.