COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/pf_demo.cc @ 251:f123e5116bc1

Last change on this file since 251:f123e5116bc1 was 201:b9158a014fe8, checked in by athos, 21 years ago

Alpár javaslatára készítettem egy struktúrát 2 dimenziós vektorok (síkvektorok) tárolására. Olyasmiket tud, amiket síkvektoroktól szeretnénk. A neve: xy, a hasonló nevu .h file-ban található.

File size: 3.8 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  ListGraph flowG;
27
28  /*
29  //Marci példája
30
31
32  NodeIt s=flowG.addNode();
33  NodeIt v1=flowG.addNode();
34  NodeIt v2=flowG.addNode();
35  NodeIt v3=flowG.addNode();
36  NodeIt v4=flowG.addNode();
37  NodeIt t=flowG.addNode();
38 
39
40  EdgeIt s_v1=flowG.addEdge(s, v1);
41  EdgeIt s_v2=flowG.addEdge(s, v2);
42  EdgeIt v1_v2=flowG.addEdge(v1, v2);
43  EdgeIt v2_v1=flowG.addEdge(v2, v1);
44  EdgeIt v1_v3=flowG.addEdge(v1, v3);
45  EdgeIt v3_v2=flowG.addEdge(v3, v2);
46  EdgeIt v2_v4=flowG.addEdge(v2, v4);
47  EdgeIt v4_v3=flowG.addEdge(v4, v3);
48  EdgeIt v3_t=flowG.addEdge(v3, t);
49  EdgeIt v4_t=flowG.addEdge(v4, t);
50
51  ListGraph::EdgeMap<int> cap(flowG);
52
53  cap.set(s_v1, 16);
54  cap.set(s_v2, 13);
55  cap.set(v1_v2, 10);
56  cap.set(v2_v1, 4);
57  cap.set(v1_v3, 12);
58  cap.set(v3_v2, 9);
59  cap.set(v2_v4, 14);
60  cap.set(v4_v3, 7);
61  cap.set(v3_t, 20);
62  cap.set(v4_t, 4);
63  */
64
65
66  //Ahuja könyv példája
67
68  NodeIt s=flowG.addNode();
69  NodeIt v2=flowG.addNode();
70  NodeIt v3=flowG.addNode();
71  NodeIt v4=flowG.addNode();
72  NodeIt v5=flowG.addNode();
73  NodeIt t=flowG.addNode();
74
75  EdgeIt s_v2=flowG.addEdge(s, v2);
76  EdgeIt s_v3=flowG.addEdge(s, v3);
77  EdgeIt v2_v4=flowG.addEdge(v2, v4);
78  EdgeIt v2_v5=flowG.addEdge(v2, v5);
79  EdgeIt v3_v5=flowG.addEdge(v3, v5);
80  EdgeIt v4_t=flowG.addEdge(v4, t);
81  EdgeIt v5_t=flowG.addEdge(v5, t);
82 
83  //Kis modositas
84  //edge_iterator v2_s=flowG.add_edge(v2, s);
85
86  ListGraph::EdgeMap<int> cap(flowG);
87
88  cap.set(s_v2, 10);
89  cap.set(s_v3, 10);
90  cap.set(v2_v4, 5);
91  cap.set(v2_v5, 8);
92  cap.set(v3_v5, 5);
93  cap.set(v4_t, 8);
94  cap.set(v5_t, 8);
95
96  //Kis modositas
97  //cap.put(v2_s, 100);
98 
99
100
101
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;
126
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 
142  //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) {
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;
148
149  //cap.put(v5_t, 9);
150  //cout << preflow_push_test.run()<<endl;
151
152  return 0;
153}
154
155
156
157
158
159
160
161
162
Note: See TracBrowser for help on using the repository browser.