1 #include <iostream> |
1 #include <iostream> |
2 #include <vector> |
2 #include <vector> |
3 #include <string> |
3 #include <string> |
4 |
4 |
5 #include "marci_list_graph.hh" |
5 #include "list_graph.hh" |
6 #include "marci_graph_traits.hh" |
6 #include "marci_graph_traits.hh" |
7 #include "marci_property_vector.hh" |
7 //#include "marci_property_vector.hh" |
8 #include "preflow_push.hh" |
8 #include "preflow_push.hh" |
9 |
9 |
10 using namespace marci; |
10 using namespace marci; |
11 |
11 |
12 |
12 |
13 int main (int, char*[]) |
13 int main (int, char*[]) |
14 { |
14 { |
15 typedef graph_traits<list_graph>::node_iterator node_iterator; |
|
16 typedef graph_traits<list_graph>::edge_iterator edge_iterator; |
|
17 typedef graph_traits<list_graph>::each_node_iterator each_node_iterator; |
|
18 typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator; |
|
19 typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator; |
|
20 typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator; |
|
21 typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator; |
|
22 |
15 |
23 list_graph flow_test; |
|
24 |
|
25 |
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 |
|
27 //Marci példája |
|
28 ListGraph flowG; |
|
29 |
|
30 NodeIt s=flowG.addNode(); |
|
31 NodeIt v1=flowG.addNode(); |
|
32 NodeIt v2=flowG.addNode(); |
|
33 NodeIt v3=flowG.addNode(); |
|
34 NodeIt v4=flowG.addNode(); |
|
35 NodeIt t=flowG.addNode(); |
|
36 |
|
37 |
|
38 EdgeIt s_v1=flowG.addEdge(s, v1); |
|
39 EdgeIt s_v2=flowG.addEdge(s, v2); |
|
40 EdgeIt v1_v2=flowG.addEdge(v1, v2); |
|
41 EdgeIt v2_v1=flowG.addEdge(v2, v1); |
|
42 EdgeIt v1_v3=flowG.addEdge(v1, v3); |
|
43 EdgeIt v3_v2=flowG.addEdge(v3, v2); |
|
44 EdgeIt v2_v4=flowG.addEdge(v2, v4); |
|
45 EdgeIt v4_v3=flowG.addEdge(v4, v3); |
|
46 EdgeIt v3_t=flowG.addEdge(v3, t); |
|
47 EdgeIt v4_t=flowG.addEdge(v4, t); |
|
48 |
|
49 ListGraph::EdgeMap<int> cap(flowG); |
|
50 |
|
51 cap.set(s_v1, 16); |
|
52 cap.set(s_v2, 13); |
|
53 cap.set(v1_v2, 10); |
|
54 cap.set(v2_v1, 4); |
|
55 cap.set(v1_v3, 12); |
|
56 cap.set(v3_v2, 9); |
|
57 cap.set(v2_v4, 14); |
|
58 cap.set(v4_v3, 7); |
|
59 cap.set(v3_t, 20); |
|
60 cap.set(v4_t, 4); |
|
61 |
|
62 |
|
63 |
|
64 |
|
65 |
|
66 |
|
67 |
|
68 /* |
26 //Ahuja könyv példája |
69 //Ahuja könyv példája |
27 node_iterator s=flow_test.add_node(); |
70 node_iterator s=flow_test.add_node(); |
28 node_iterator v2=flow_test.add_node(); |
71 NodeIt v2=flow_test.add_node(); |
29 node_iterator v3=flow_test.add_node(); |
72 NodeIt v3=flow_test.add_node(); |
30 node_iterator v4=flow_test.add_node(); |
73 NodeIt v4=flow_test.add_node(); |
31 node_iterator v5=flow_test.add_node(); |
74 NodeIt v5=flow_test.add_node(); |
32 node_iterator t=flow_test.add_node(); |
75 NodeIt t=flow_test.add_node(); |
33 |
76 |
34 node_property_vector<list_graph, std::string> node_name(flow_test); |
77 node_property_vector<list_graph, std::string> node_name(flow_test); |
35 node_name.put(s, "s"); |
78 node_name.put(s, "s"); |
36 node_name.put(v2, "v2"); |
79 node_name.put(v2, "v2"); |
37 node_name.put(v3, "v3"); |
80 node_name.put(v3, "v3"); |
68 |
111 |
69 //Kis modositas |
112 //Kis modositas |
70 //edge_iterator t_s=flow_test.add_edge(t, s); |
113 //edge_iterator t_s=flow_test.add_edge(t, s); |
71 //cap.put(t_s, 20); |
114 //cap.put(t_s, 20); |
72 |
115 |
73 |
116 */ |
74 /* |
|
75 //Marci példája |
|
76 node_iterator s=flow_test.add_node(); |
|
77 node_iterator v1=flow_test.add_node(); |
|
78 node_iterator v2=flow_test.add_node(); |
|
79 node_iterator v3=flow_test.add_node(); |
|
80 node_iterator v4=flow_test.add_node(); |
|
81 node_iterator t=flow_test.add_node(); |
|
82 |
|
83 node_property_vector<list_graph, std::string> node_name(flow_test); |
|
84 node_name.put(s, "s"); |
|
85 node_name.put(v1, "v1"); |
|
86 node_name.put(v2, "v2"); |
|
87 node_name.put(v3, "v3"); |
|
88 node_name.put(v4, "v4"); |
|
89 node_name.put(t, "t"); |
|
90 |
117 |
91 edge_iterator s_v1=flow_test.add_edge(s, v1); |
118 |
92 edge_iterator s_v2=flow_test.add_edge(s, v2); |
119 |
93 edge_iterator v1_v2=flow_test.add_edge(v1, v2); |
|
94 edge_iterator v2_v1=flow_test.add_edge(v2, v1); |
|
95 edge_iterator v1_v3=flow_test.add_edge(v1, v3); |
|
96 edge_iterator v3_v2=flow_test.add_edge(v3, v2); |
|
97 edge_iterator v2_v4=flow_test.add_edge(v2, v4); |
|
98 edge_iterator v4_v3=flow_test.add_edge(v4, v3); |
|
99 edge_iterator v3_t=flow_test.add_edge(v3, t); |
|
100 edge_iterator v4_t=flow_test.add_edge(v4, t); |
|
101 |
|
102 edge_property_vector<list_graph, int> cap(flow_test); |
|
103 cap.put(s_v1, 16); |
|
104 cap.put(s_v2, 13); |
|
105 cap.put(v1_v2, 10); |
|
106 cap.put(v2_v1, 4); |
|
107 cap.put(v1_v3, 12); |
|
108 cap.put(v3_v2, 9); |
|
109 cap.put(v2_v4, 14); |
|
110 cap.put(v4_v3, 7); |
|
111 cap.put(v3_t, 20); |
|
112 cap.put(v4_t, 4); |
|
113 */ |
|
114 /*Egyszerű példa |
120 /*Egyszerű példa |
115 node_iterator s=flow_test.add_node(); |
121 NodeIt s=flow_test.add_node(); |
116 node_iterator v1=flow_test.add_node(); |
122 NodeIt v1=flow_test.add_node(); |
117 node_iterator v2=flow_test.add_node(); |
123 NodeIt v2=flow_test.add_node(); |
118 node_iterator t=flow_test.add_node(); |
124 NodeIt t=flow_test.add_node(); |
119 |
125 |
120 node_property_vector<list_graph, std::string> node_name(flow_test); |
126 node_property_vector<list_graph, std::string> node_name(flow_test); |
121 node_name.put(s, "s"); |
127 node_name.put(s, "s"); |
122 node_name.put(v1, "v1"); |
128 node_name.put(v1, "v1"); |
123 node_name.put(v2, "v2"); |
129 node_name.put(v2, "v2"); |
133 cap.put(v1_v2, 10); |
139 cap.put(v1_v2, 10); |
134 cap.put(v2_t, 4); |
140 cap.put(v2_t, 4); |
135 */ |
141 */ |
136 |
142 |
137 std::cout << "preflow-push algorithm test..." << std::endl; |
143 std::cout << "preflow-push algorithm test..." << std::endl; |
|
144 |
|
145 /* |
138 std::cout << "on directed graph graph" << std::endl; //<< flow_test; |
146 std::cout << "on directed graph graph" << std::endl; //<< flow_test; |
139 std::cout << "names and capacity values" << std::endl; |
147 std::cout << "names and capacity values" << std::endl; |
140 for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { |
148 for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) { |
141 std::cout << node_name.get(i) << ": "; |
149 std::cout << node_name.get(i) << ": "; |
142 std::cout << "out edges: "; |
150 std::cout << "out edges: "; |
143 for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) |
151 for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) |
144 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
152 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
145 std::cout << "in edges: "; |
153 std::cout << "in edges: "; |
146 for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) |
154 for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) |
147 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
155 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
148 std::cout << std::endl; |
156 std::cout << std::endl; |
149 } |
157 } |
150 |
158 */ |
151 |
159 |
152 //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { |
160 //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) { |
153 // std::cout << i << " "; |
161 // std::cout << i << " "; |
154 //} |
162 //} |
155 |
163 |
156 preflow_push<list_graph, int> preflow_push_test(flow_test, s, t, cap); |
164 preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap); |
157 cout << preflow_push_test.run()<<endl; |
165 cout << preflow_push_test.run()<<endl; |
158 |
166 |
159 //cap.put(v5_t, 9); |
167 //cap.put(v5_t, 9); |
160 //cout << preflow_push_test.run()<<endl; |
168 //cout << preflow_push_test.run()<<endl; |
161 |
169 |