1 #include <iostream> |
1 #include <iostream> |
2 #include <vector> |
2 #include <vector> |
3 #include <string> |
3 #include <string> |
4 |
4 |
5 #include "list_graph.hh" |
5 #include "list_graph.h" |
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 hugo; |
10 using namespace hugo; |
11 |
11 |
12 |
12 |
13 int main (int, char*[]) |
13 int main (int, char*[]) |
14 { |
14 { |
15 |
15 |
16 |
16 typedef ListGraph::Node Node; |
17 typedef ListGraph::NodeIt NodeIt; |
17 typedef ListGraph::Edge Edge; |
18 typedef ListGraph::EdgeIt EdgeIt; |
18 |
19 /* |
19 ListGraph graph; |
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; |
|
27 |
20 |
28 /* |
21 /* |
29 //Marci példája |
22 //Marci példája |
30 |
23 |
31 |
24 |
32 NodeIt s=flowG.addNode(); |
25 NodeIt s=graph.addNode(); |
33 NodeIt v1=flowG.addNode(); |
26 NodeIt v1=graph.addNode(); |
34 NodeIt v2=flowG.addNode(); |
27 NodeIt v2=graph.addNode(); |
35 NodeIt v3=flowG.addNode(); |
28 NodeIt v3=graph.addNode(); |
36 NodeIt v4=flowG.addNode(); |
29 NodeIt v4=graph.addNode(); |
37 NodeIt t=flowG.addNode(); |
30 NodeIt t=graph.addNode(); |
38 |
31 |
39 |
32 |
40 EdgeIt s_v1=flowG.addEdge(s, v1); |
33 EdgeIt s_v1=graph.addEdge(s, v1); |
41 EdgeIt s_v2=flowG.addEdge(s, v2); |
34 EdgeIt s_v2=graph.addEdge(s, v2); |
42 EdgeIt v1_v2=flowG.addEdge(v1, v2); |
35 EdgeIt v1_v2=graph.addEdge(v1, v2); |
43 EdgeIt v2_v1=flowG.addEdge(v2, v1); |
36 EdgeIt v2_v1=graph.addEdge(v2, v1); |
44 EdgeIt v1_v3=flowG.addEdge(v1, v3); |
37 EdgeIt v1_v3=graph.addEdge(v1, v3); |
45 EdgeIt v3_v2=flowG.addEdge(v3, v2); |
38 EdgeIt v3_v2=graph.addEdge(v3, v2); |
46 EdgeIt v2_v4=flowG.addEdge(v2, v4); |
39 EdgeIt v2_v4=graph.addEdge(v2, v4); |
47 EdgeIt v4_v3=flowG.addEdge(v4, v3); |
40 EdgeIt v4_v3=graph.addEdge(v4, v3); |
48 EdgeIt v3_t=flowG.addEdge(v3, t); |
41 EdgeIt v3_t=graph.addEdge(v3, t); |
49 EdgeIt v4_t=flowG.addEdge(v4, 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); |
46 length.set(s_v1, 16); |
54 cap.set(s_v2, 13); |
47 length.set(s_v2, 13); |
55 cap.set(v1_v2, 10); |
48 length.set(v1_v2, 10); |
56 cap.set(v2_v1, 4); |
49 length.set(v2_v1, 4); |
57 cap.set(v1_v3, 12); |
50 length.set(v1_v3, 12); |
58 cap.set(v3_v2, 9); |
51 length.set(v3_v2, 9); |
59 cap.set(v2_v4, 14); |
52 length.set(v2_v4, 14); |
60 cap.set(v4_v3, 7); |
53 length.set(v4_v3, 7); |
61 cap.set(v3_t, 20); |
54 length.set(v3_t, 20); |
62 cap.set(v4_t, 4); |
55 length.set(v4_t, 4); |
63 */ |
56 */ |
64 |
57 |
65 |
58 |
66 //Ahuja könyv példája |
59 //Ahuja könyv példája |
67 |
60 |
68 NodeIt s=flowG.addNode(); |
61 Node s=graph.addNode(); |
69 NodeIt v2=flowG.addNode(); |
62 Node v2=graph.addNode(); |
70 NodeIt v3=flowG.addNode(); |
63 Node v3=graph.addNode(); |
71 NodeIt v4=flowG.addNode(); |
64 Node v4=graph.addNode(); |
72 NodeIt v5=flowG.addNode(); |
65 Node v5=graph.addNode(); |
73 NodeIt t=flowG.addNode(); |
66 Node t=graph.addNode(); |
74 |
67 |
75 EdgeIt s_v2=flowG.addEdge(s, v2); |
68 Edge s_v2=graph.addEdge(s, v2); |
76 EdgeIt s_v3=flowG.addEdge(s, v3); |
69 Edge s_v3=graph.addEdge(s, v3); |
77 EdgeIt v2_v4=flowG.addEdge(v2, v4); |
70 Edge v2_v4=graph.addEdge(v2, v4); |
78 EdgeIt v2_v5=flowG.addEdge(v2, v5); |
71 Edge v2_v5=graph.addEdge(v2, v5); |
79 EdgeIt v3_v5=flowG.addEdge(v3, v5); |
72 Edge v3_v5=graph.addEdge(v3, v5); |
80 EdgeIt v4_t=flowG.addEdge(v4, t); |
73 Edge v4_t=graph.addEdge(v4, t); |
81 EdgeIt v5_t=flowG.addEdge(v5, t); |
74 Edge v5_t=graph.addEdge(v5, t); |
82 |
75 |
83 //Kis modositas |
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); |
81 length.set(s_v2, 10); |
89 cap.set(s_v3, 10); |
82 length.set(s_v3, 10); |
90 cap.set(v2_v4, 5); |
83 length.set(v2_v4, 5); |
91 cap.set(v2_v5, 8); |
84 length.set(v2_v5, 8); |
92 cap.set(v3_v5, 5); |
85 length.set(v3_v5, 5); |
93 cap.set(v4_t, 8); |
86 length.set(v4_t, 8); |
94 cap.set(v5_t, 8); |
87 length.set(v5_t, 8); |
95 |
88 |
96 //Kis modositas |
89 //Kis modositas |
97 //cap.put(v2_s, 100); |
90 //length.put(v2_s, 100); |
98 |
|
99 |
91 |
100 |
92 |
101 |
93 |
102 /*Egyszerű példa |
|
103 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 std::cout << "preflow-push algorithm test..." << std::endl; |
94 std::cout << "preflow-push 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) { |
97 preflow_push<ListGraph, int> preflow_push_test(graph, s, t, length); |
143 // std::cout << i << " "; |
|
144 //} |
|
145 |
|
146 preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap); |
|
147 cout << preflow_push_test.run()<<endl; |
98 cout << preflow_push_test.run()<<endl; |
148 |
99 |
149 //cap.put(v5_t, 9); |
100 //cap.put(v5_t, 9); |
150 //cout << preflow_push_test.run()<<endl; |
101 //cout << preflow_push_test.run()<<endl; |
151 |
102 |
152 return 0; |
103 return 0; |
153 } |
104 } |
154 |
|
155 |
|
156 |
|
157 |
|
158 |
|
159 |
|
160 |
|
161 |
|
162 |
|