COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/pf_demo.cc @ 105:a3c73e9b9b2e

Last change on this file since 105:a3c73e9b9b2e was 105:a3c73e9b9b2e, checked in by Alpar Juttner, 21 years ago

marci -> hugo replacements
resize -> update replacements

File size: 4.2 KB
Line 
1#include <iostream>
2#include <vector>
3#include <string>
4
5#include "list_graph.hh"
6#include "marci_graph_traits.hh"
7//#include "marci_property_vector.hh"
8#include "preflow_push.hh"
9
10using namespace hugo;
11
12
13int main (int, char*[])
14{
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 
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  /*
69  //Ahuja könyv példája
70  node_iterator s=flow_test.add_node();
71  NodeIt v2=flow_test.add_node();
72  NodeIt v3=flow_test.add_node();
73  NodeIt v4=flow_test.add_node();
74  NodeIt v5=flow_test.add_node();
75  NodeIt t=flow_test.add_node();
76 
77  node_property_vector<list_graph, std::string> node_name(flow_test);
78  node_name.put(s, "s"); 
79  node_name.put(v2, "v2");
80  node_name.put(v3, "v3");
81  node_name.put(v4, "v4");
82  node_name.put(v5, "v5");
83  node_name.put(t, "t");
84
85 
86  edge_iterator s_v2=flow_test.add_edge(s, v2);
87  edge_iterator s_v3=flow_test.add_edge(s, v3);
88 
89  edge_iterator v2_v4=flow_test.add_edge(v2, v4);
90  edge_iterator v2_v5=flow_test.add_edge(v2, v5);
91
92  edge_iterator v3_v5=flow_test.add_edge(v3, v5);
93
94  edge_iterator v4_t=flow_test.add_edge(v4, t);
95  edge_iterator v5_t=flow_test.add_edge(v5, t);
96 
97  //Kis modositas
98  edge_iterator v2_s=flow_test.add_edge(v2, s);
99
100  edge_property_vector<list_graph, int> cap(flow_test); 
101  cap.put(s_v2, 10);
102  cap.put(s_v3, 10);
103  cap.put(v2_v4, 5);
104  cap.put(v2_v5, 8);
105  cap.put(v3_v5, 5);
106  cap.put(v4_t, 8);
107  cap.put(v5_t, 8);
108
109  //Kis modositas
110  cap.put(v2_s, 100);
111
112  //Kis modositas
113  //edge_iterator t_s=flow_test.add_edge(t, s);
114  //cap.put(t_s, 20);
115
116  */
117
118
119
120  /*Egyszerû példa
121  NodeIt s=flow_test.add_node();
122  NodeIt v1=flow_test.add_node();
123  NodeIt v2=flow_test.add_node();
124  NodeIt t=flow_test.add_node();
125 
126  node_property_vector<list_graph, std::string> node_name(flow_test);
127  node_name.put(s, "s");
128  node_name.put(v1, "v1");
129  node_name.put(v2, "v2");
130  node_name.put(t, "t");
131
132  edge_iterator s_v1=flow_test.add_edge(s, v1);
133  edge_iterator v1_v2=flow_test.add_edge(v1, v2);
134  edge_iterator v2_t=flow_test.add_edge(v2, t);
135
136  edge_property_vector<list_graph, int> cap(flow_test);
137   
138  cap.put(s_v1, 16);
139  cap.put(v1_v2, 10);
140  cap.put(v2_t, 4);
141  */
142
143  std::cout << "preflow-push algorithm test..." << std::endl;
144
145  /*
146  std::cout << "on directed graph graph" << std::endl; //<< flow_test;
147  std::cout << "names and capacity values" << std::endl;
148  for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) {
149    std::cout << node_name.get(i) << ": ";
150    std::cout << "out edges: ";
151    for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
152      std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
153    std::cout << "in edges: ";
154    for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
155      std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
156    std::cout << std::endl;
157  }
158  */
159 
160  //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) {
161  //  std::cout << i << " ";
162  //}
163 
164  preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap);
165  cout << preflow_push_test.run()<<endl;
166
167  //cap.put(v5_t, 9);
168  //cout << preflow_push_test.run()<<endl;
169
170  return 0;
171}
172
173
174
175
176
177
178
179
180
Note: See TracBrowser for help on using the repository browser.