DirPath fejlodes.
Kiserleti struktura a forditasi idoben kapcsolhato konzisztencia es range
ellenorzesekre.
5 #include <list_graph.h>
6 #include <bfs_iterator.h>
7 #include <edmonds_karp.h>
11 int main (int, char*[])
13 typedef ListGraph::Node Node;
14 typedef ListGraph::Edge Edge;
15 typedef ListGraph::NodeIt NodeIt;
16 typedef ListGraph::EdgeIt EdgeIt;
17 typedef ListGraph::OutEdgeIt OutEdgeIt;
18 typedef ListGraph::InEdgeIt InEdgeIt;
19 typedef ListGraph::SymEdgeIt SymEdgeIt;
21 std::vector<Node> vector_of_Nodes;
22 for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode());
23 for(int i=0; i!=8; ++i)
24 for(int j=0; j!=8; ++j)
25 if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]);
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;
28 std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl;
30 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
31 std::cout << "node " << G.id(i) << std::endl;
32 std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " ";
33 for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {
34 std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
36 std::cout << std::endl;
39 for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {
40 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
43 std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
44 for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {
45 std::cout << j << " "; }
46 std::cout << std::endl;
49 for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {
50 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
53 std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
54 for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {
55 std::cout << j << " "; }
59 for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {
60 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
64 std::cout << "all edges: ";
65 for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
66 std::cout << i << " ";
68 std::cout << std::endl;
70 std::cout << "node property array test" << std::endl;
71 ListGraph::NodeMap<int> my_property_vector(G);
74 my_property_vector.set(v, 42);
75 my_property_vector.set(G.next(G.first<NodeIt>()), 314);
76 my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956);
77 my_property_vector.set(vector_of_Nodes[3], 1989);
78 my_property_vector.set(vector_of_Nodes[4], 2003);
79 my_property_vector.set(vector_of_Nodes[7], 1978);
80 std::cout << "some node property values..." << std::endl;
81 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
82 std::cout << my_property_vector.get(i) << std::endl;
86 ListGraph::EdgeMap<int> my_edge_property(G);
87 for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
88 my_edge_property.set(i, _i);
92 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
93 for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) {
94 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
96 std::cout << std::endl;
98 std::cout << "bfs from the first node" << std::endl;
99 bfs<ListGraph> bfs_test(G, G.first<NodeIt>());
101 std::cout << "reached: ";
102 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
103 std::cout << bfs_test.reached.get(i) << " ";
105 std::cout<<std::endl;
106 std::cout << "dist: ";
107 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
108 std::cout << bfs_test.dist.get(i) << " ";
110 std::cout<<std::endl;
113 std::cout << "augmenting path flow algorithm test..." << std::endl;
116 Node s=flowG.addNode();
117 Node v1=flowG.addNode();
118 Node v2=flowG.addNode();
119 Node v3=flowG.addNode();
120 Node v4=flowG.addNode();
121 Node t=flowG.addNode();
123 ListGraph::NodeMap<std::string> node_name(flowG);
124 node_name.set(s, "s");
125 node_name.set(v1, "v1");
126 node_name.set(v2, "v2");
127 node_name.set(v3, "v3");
128 node_name.set(v4, "v4");
129 node_name.set(t, "t");
131 Edge s_v1=flowG.addEdge(s, v1);
132 Edge s_v2=flowG.addEdge(s, v2);
133 Edge v1_v2=flowG.addEdge(v1, v2);
134 Edge v2_v1=flowG.addEdge(v2, v1);
135 Edge v1_v3=flowG.addEdge(v1, v3);
136 Edge v3_v2=flowG.addEdge(v3, v2);
137 Edge v2_v4=flowG.addEdge(v2, v4);
138 Edge v4_v3=flowG.addEdge(v4, v3);
139 Edge v3_t=flowG.addEdge(v3, t);
140 Edge v4_t=flowG.addEdge(v4, t);
142 ListGraph::EdgeMap<int> cap(flowG);
155 std::cout << "on directed graph graph" << std::endl; //<< flowG;
156 std::cout << "names and capacity values" << std::endl;
157 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
158 std::cout << node_name.get(i) << ": ";
159 std::cout << "out edges: ";
160 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
161 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
162 std::cout << "in edges: ";
163 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
164 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
165 std::cout << std::endl;
168 //flowG.deleteEdge(s_v1);
169 //flowG.deleteEdge(s_v2);
170 //flowG.deleteEdge(v1_v2);
171 //flowG.deleteEdge(v1_v3);
174 //flowG.setTail(v3_t, v2);
175 //flowG.setHead(v3_t, s);
177 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
178 std::cout << node_name.get(i) << ": ";
179 std::cout << "out edges: ";
180 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
181 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
182 std::cout << "in edges: ";
183 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
184 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
185 std::cout << std::endl;
188 for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
189 std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
193 while (flowG.valid(flowG.first<EdgeIt>())) {
194 flowG.deleteEdge(flowG.first<EdgeIt>());
195 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
196 std::cout << node_name.get(i) << ": ";
197 std::cout << "out edges: ";
198 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
199 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
200 std::cout << "in edges: ";
201 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
202 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
203 std::cout << std::endl;
207 while (flowG.valid(flowG.first<NodeIt>())) {
208 flowG.deleteNode(flowG.first<NodeIt>());
209 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
210 std::cout << node_name.get(i) << ": ";
211 std::cout << "out edges: ";
212 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
213 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
214 std::cout << "in edges: ";
215 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
216 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
217 std::cout << std::endl;
222 //std::cout << std::endl;
226 ListGraph::EdgeMap<int> flow(flowG, 0);
227 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
229 max_flow_test.augmentOnBlockingFlow<ListGraph>();
230 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
231 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
233 std::cout<<std::endl;
234 max_flow_test.augmentOnBlockingFlow<ListGraph>();
235 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
236 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
238 std::cout<<std::endl;*/
239 //max_flow_test.run();
241 //std::cout << "maximum flow: "<< std::endl;
242 while (max_flow_test.augmentOnShortestPath()) {
243 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
244 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
246 std::cout<<std::endl;
248 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
253 S.push_back(s); S.push_back(v3);
257 ListGraph::EdgeMap<int> flow(flowG, 0);
258 MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap);
261 std::cout << "maximum flow: "<< std::endl;
262 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
263 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
265 std::cout<<std::endl;
266 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;