marci@9
|
1 |
#include <iostream>
|
marci@9
|
2 |
#include <vector>
|
marci@9
|
3 |
#include <string>
|
marci@9
|
4 |
|
marci@49
|
5 |
#include <list_graph.hh>
|
marci@49
|
6 |
#include <bfs_iterator.hh>
|
marci@49
|
7 |
#include <edmonds_karp.hh>
|
marci@9
|
8 |
|
marci@9
|
9 |
using namespace marci;
|
marci@9
|
10 |
|
marci@9
|
11 |
int main (int, char*[])
|
marci@9
|
12 |
{
|
marci@49
|
13 |
typedef ListGraph::NodeIt NodeIt;
|
marci@49
|
14 |
typedef ListGraph::EdgeIt EdgeIt;
|
marci@49
|
15 |
typedef ListGraph::EachNodeIt EachNodeIt;
|
marci@49
|
16 |
typedef ListGraph::EachEdgeIt EachEdgeIt;
|
marci@49
|
17 |
typedef ListGraph::OutEdgeIt OutEdgeIt;
|
marci@49
|
18 |
typedef ListGraph::InEdgeIt InEdgeIt;
|
marci@49
|
19 |
typedef ListGraph::SymEdgeIt SymEdgeIt;
|
marci@49
|
20 |
ListGraph G;
|
marci@49
|
21 |
std::vector<NodeIt> vector_of_NodeIts;
|
marci@49
|
22 |
for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode());
|
marci@9
|
23 |
for(int i=0; i!=8; ++i)
|
marci@49
|
24 |
for(int j=0; j!=8; ++j)
|
marci@49
|
25 |
if ((i<j)&&(i+j)%3) G.addEdge(vector_of_NodeIts[i], vector_of_NodeIts[j]);
|
marci@9
|
26 |
|
marci@9
|
27 |
std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl;
|
marci@49
|
28 |
std::cout << "number of nodes: " << count(G.first<EachNodeIt>()) << std::endl;
|
marci@9
|
29 |
|
marci@49
|
30 |
for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
|
marci@9
|
31 |
std::cout << "node " << G.id(i) << std::endl;
|
marci@49
|
32 |
std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " ";
|
marci@49
|
33 |
for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
|
marci@9
|
34 |
std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
|
marci@9
|
35 |
}
|
marci@9
|
36 |
std::cout << std::endl;
|
marci@12
|
37 |
|
marci@12
|
38 |
std::cout<< " ";
|
marci@49
|
39 |
for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
|
marci@49
|
40 |
std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
|
marci@12
|
41 |
std::cout<<std::endl;
|
marci@12
|
42 |
|
marci@49
|
43 |
std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
|
marci@49
|
44 |
for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
|
marci@9
|
45 |
std::cout << j << " "; }
|
marci@9
|
46 |
std::cout << std::endl;
|
marci@12
|
47 |
|
marci@12
|
48 |
std::cout<< " ";
|
marci@49
|
49 |
for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
|
marci@49
|
50 |
std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
|
marci@12
|
51 |
std::cout<<std::endl;
|
marci@12
|
52 |
|
marci@49
|
53 |
std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
|
marci@49
|
54 |
for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
|
marci@9
|
55 |
std::cout << j << " "; }
|
marci@9
|
56 |
std::cout<<std::endl;
|
marci@12
|
57 |
|
marci@12
|
58 |
std::cout<< " ";
|
marci@49
|
59 |
for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
|
marci@49
|
60 |
std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
|
marci@12
|
61 |
std::cout<<std::endl;
|
marci@9
|
62 |
}
|
marci@9
|
63 |
|
marci@9
|
64 |
std::cout << "all edges: ";
|
marci@49
|
65 |
for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
|
marci@9
|
66 |
std::cout << i << " ";
|
marci@9
|
67 |
}
|
marci@9
|
68 |
std::cout << std::endl;
|
marci@9
|
69 |
|
marci@9
|
70 |
std::cout << "node property array test" << std::endl;
|
marci@49
|
71 |
ListGraph::NodeMap<int> my_property_vector(G);
|
marci@49
|
72 |
EachNodeIt v;
|
marci@49
|
73 |
G.getFirst(v);
|
marci@49
|
74 |
my_property_vector.set(v, 42);
|
marci@49
|
75 |
my_property_vector.set(++G.first<EachNodeIt>(), 314);
|
marci@49
|
76 |
my_property_vector.set(++++G.first<EachNodeIt>(), 1956);
|
marci@49
|
77 |
my_property_vector.set(vector_of_NodeIts[3], 1989);
|
marci@49
|
78 |
my_property_vector.set(vector_of_NodeIts[4], 2003);
|
marci@49
|
79 |
my_property_vector.set(vector_of_NodeIts[7], 1978);
|
marci@9
|
80 |
std::cout << "some node property values..." << std::endl;
|
marci@49
|
81 |
for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
|
marci@9
|
82 |
std::cout << my_property_vector.get(i) << std::endl;
|
marci@9
|
83 |
}
|
marci@9
|
84 |
int _i=1;
|
marci@9
|
85 |
int _ii=1;
|
marci@49
|
86 |
ListGraph::EdgeMap<int> my_edge_property(G);
|
marci@49
|
87 |
for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
|
marci@49
|
88 |
my_edge_property.set(i, _i);
|
marci@9
|
89 |
_i*=_ii; ++_ii;
|
marci@9
|
90 |
}
|
marci@9
|
91 |
|
marci@9
|
92 |
std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
|
marci@49
|
93 |
for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) {
|
marci@9
|
94 |
std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
|
marci@9
|
95 |
}
|
marci@9
|
96 |
std::cout << std::endl;
|
marci@9
|
97 |
|
marci@9
|
98 |
std::cout << "bfs from the first node" << std::endl;
|
marci@49
|
99 |
bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
|
marci@9
|
100 |
bfs_test.run();
|
marci@9
|
101 |
std::cout << "reached: ";
|
marci@49
|
102 |
for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
|
marci@9
|
103 |
std::cout << bfs_test.reached.get(i) << " ";
|
marci@9
|
104 |
}
|
marci@9
|
105 |
std::cout<<std::endl;
|
marci@9
|
106 |
std::cout << "dist: ";
|
marci@49
|
107 |
for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
|
marci@9
|
108 |
std::cout << bfs_test.dist.get(i) << " ";
|
marci@9
|
109 |
}
|
marci@9
|
110 |
std::cout<<std::endl;
|
marci@9
|
111 |
|
marci@9
|
112 |
|
marci@9
|
113 |
std::cout << "augmenting path flow algorithm test..." << std::endl;
|
marci@49
|
114 |
ListGraph flowG;
|
marci@9
|
115 |
|
marci@49
|
116 |
NodeIt s=flowG.addNode();
|
marci@49
|
117 |
NodeIt v1=flowG.addNode();
|
marci@49
|
118 |
NodeIt v2=flowG.addNode();
|
marci@49
|
119 |
NodeIt v3=flowG.addNode();
|
marci@49
|
120 |
NodeIt v4=flowG.addNode();
|
marci@49
|
121 |
NodeIt t=flowG.addNode();
|
marci@9
|
122 |
|
marci@49
|
123 |
ListGraph::NodeMap<std::string> node_name(flowG);
|
marci@49
|
124 |
node_name.set(s, "s");
|
marci@49
|
125 |
node_name.set(v1, "v1");
|
marci@49
|
126 |
node_name.set(v2, "v2");
|
marci@49
|
127 |
node_name.set(v3, "v3");
|
marci@49
|
128 |
node_name.set(v4, "v4");
|
marci@49
|
129 |
node_name.set(t, "t");
|
marci@9
|
130 |
|
marci@49
|
131 |
EdgeIt s_v1=flowG.addEdge(s, v1);
|
marci@49
|
132 |
EdgeIt s_v2=flowG.addEdge(s, v2);
|
marci@49
|
133 |
EdgeIt v1_v2=flowG.addEdge(v1, v2);
|
marci@49
|
134 |
EdgeIt v2_v1=flowG.addEdge(v2, v1);
|
marci@49
|
135 |
EdgeIt v1_v3=flowG.addEdge(v1, v3);
|
marci@49
|
136 |
EdgeIt v3_v2=flowG.addEdge(v3, v2);
|
marci@49
|
137 |
EdgeIt v2_v4=flowG.addEdge(v2, v4);
|
marci@49
|
138 |
EdgeIt v4_v3=flowG.addEdge(v4, v3);
|
marci@49
|
139 |
EdgeIt v3_t=flowG.addEdge(v3, t);
|
marci@49
|
140 |
EdgeIt v4_t=flowG.addEdge(v4, t);
|
marci@9
|
141 |
|
marci@49
|
142 |
ListGraph::EdgeMap<int> cap(flowG);
|
marci@9
|
143 |
|
marci@49
|
144 |
cap.set(s_v1, 16);
|
marci@49
|
145 |
cap.set(s_v2, 13);
|
marci@49
|
146 |
cap.set(v1_v2, 10);
|
marci@49
|
147 |
cap.set(v2_v1, 4);
|
marci@49
|
148 |
cap.set(v1_v3, 12);
|
marci@49
|
149 |
cap.set(v3_v2, 9);
|
marci@49
|
150 |
cap.set(v2_v4, 14);
|
marci@49
|
151 |
cap.set(v4_v3, 7);
|
marci@49
|
152 |
cap.set(v3_t, 20);
|
marci@49
|
153 |
cap.set(v4_t, 4);
|
marci@9
|
154 |
|
marci@49
|
155 |
std::cout << "on directed graph graph" << std::endl; //<< flowG;
|
marci@9
|
156 |
std::cout << "names and capacity values" << std::endl;
|
marci@49
|
157 |
for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
|
marci@9
|
158 |
std::cout << node_name.get(i) << ": ";
|
marci@9
|
159 |
std::cout << "out edges: ";
|
marci@49
|
160 |
for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
|
marci@49
|
161 |
std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
|
marci@9
|
162 |
std::cout << "in edges: ";
|
marci@49
|
163 |
for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
|
marci@49
|
164 |
std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
|
marci@9
|
165 |
std::cout << std::endl;
|
marci@9
|
166 |
}
|
marci@9
|
167 |
|
marci@49
|
168 |
//flowG.setTail(v3_t, v2);
|
marci@49
|
169 |
//flowG.setHead(v3_t, s);
|
marci@49
|
170 |
|
marci@49
|
171 |
for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
|
marci@49
|
172 |
std::cout << node_name.get(i) << ": ";
|
marci@49
|
173 |
std::cout << "out edges: ";
|
marci@49
|
174 |
for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
|
marci@49
|
175 |
std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
|
marci@49
|
176 |
std::cout << "in edges: ";
|
marci@49
|
177 |
for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
|
marci@49
|
178 |
std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
|
marci@49
|
179 |
std::cout << std::endl;
|
marci@49
|
180 |
}
|
marci@9
|
181 |
|
marci@49
|
182 |
|
marci@49
|
183 |
/*
|
marci@49
|
184 |
while (flowG.first<EachEdgeIt>().valid()) {
|
marci@49
|
185 |
flowG.deleteEdge(flowG.first<EachEdgeIt>());
|
marci@49
|
186 |
for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
|
marci@49
|
187 |
std::cout << node_name.get(i) << ": ";
|
marci@49
|
188 |
std::cout << "out edges: ";
|
marci@49
|
189 |
for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
|
marci@49
|
190 |
std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
|
marci@49
|
191 |
std::cout << "in edges: ";
|
marci@49
|
192 |
for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
|
marci@49
|
193 |
std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
|
marci@49
|
194 |
std::cout << std::endl;
|
marci@49
|
195 |
}
|
marci@49
|
196 |
}
|
marci@9
|
197 |
|
marci@49
|
198 |
while (flowG.first<EachNodeIt>().valid()) {
|
marci@49
|
199 |
flowG.deleteNode(flowG.first<EachNodeIt>());
|
marci@49
|
200 |
for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
|
marci@49
|
201 |
std::cout << node_name.get(i) << ": ";
|
marci@49
|
202 |
std::cout << "out edges: ";
|
marci@49
|
203 |
for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
|
marci@49
|
204 |
std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
|
marci@49
|
205 |
std::cout << "in edges: ";
|
marci@49
|
206 |
for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
|
marci@49
|
207 |
std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
|
marci@49
|
208 |
std::cout << std::endl;
|
marci@49
|
209 |
}
|
marci@49
|
210 |
}
|
marci@49
|
211 |
*/
|
marci@49
|
212 |
|
marci@49
|
213 |
//ListGraph::EdgeMap<int> flow(flowG, 0);
|
marci@49
|
214 |
//ResGraph<ListGraph, int> res_graph(flowG, cap, flow);
|
marci@49
|
215 |
max_flow_type<ListGraph, int> max_flow_test(flowG, s, t, cap);
|
marci@9
|
216 |
max_flow_test.run();
|
marci@9
|
217 |
|
marci@9
|
218 |
return 0;
|
marci@9
|
219 |
}
|