COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_graph_demo.cc @ 40:ffaa9448964c

Last change on this file since 40:ffaa9448964c was 19:3151a1026db9, checked in by marci, 21 years ago

* empty log message *

File size: 6.8 KB
Line 
1#include <iostream>
2#include <vector>
3#include <string>
4
5#include <marci_list_graph.hh>
6#include <marci_property_vector.hh>
7#include <marci_bfs.hh>
8#include <marci_max_flow.hh>
9
10using namespace marci;
11
12int main (int, char*[])
13{
14  typedef list_graph::node_iterator node_iterator;
15  typedef list_graph::edge_iterator edge_iterator;
16  typedef list_graph::each_node_iterator each_node_iterator;
17  typedef list_graph::each_edge_iterator each_edge_iterator;
18  typedef list_graph::out_edge_iterator out_edge_iterator;
19  typedef list_graph::in_edge_iterator in_edge_iterator;
20  typedef list_graph::sym_edge_iterator sym_edge_iterator;
21  list_graph G;
22  std::vector<node_iterator> vector_of_node_iterators;
23  for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node());
24  for(int i=0; i!=8; ++i)
25    for(int j=0; j!=8; ++j) {
26      if ((i<j)&&(i+j)%3) G.add_edge(vector_of_node_iterators[i], vector_of_node_iterators[j]);
27    } 
28
29  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;
30  std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl;
31
32  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
33    std::cout << "node " << G.id(i) << std::endl;
34    std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " ";
35    for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
36      std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
37    }
38    std::cout << std::endl;
39
40    std::cout<< " ";
41    for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
42      std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
43    std::cout<<std::endl;
44
45    std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " ";
46    for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
47      std::cout << j << " "; }
48    std::cout << std::endl;
49
50    std::cout<< " ";
51    for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
52      std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
53    std::cout<<std::endl;
54
55    std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " ";
56    for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
57      std::cout << j << " "; }
58    std::cout<<std::endl;
59
60    std::cout<< " ";
61    for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
62      std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
63    std::cout<<std::endl;
64  }
65
66  std::cout << "all edges: ";
67  for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
68    std::cout << i << " ";
69  }
70  std::cout << std::endl;
71
72  std::cout << "node property array test" << std::endl;
73  node_property_vector<list_graph, int> my_property_vector(G);
74  each_node_iterator v;
75  G.get_first(v);
76  my_property_vector.put(v, 42);
77  my_property_vector.put(++G.first_node(), 314);
78  my_property_vector.put(++++G.first_node(), 1956);
79  my_property_vector.put(vector_of_node_iterators[3], 1989);
80  my_property_vector.put(vector_of_node_iterators[4], 2003);
81  my_property_vector.put(vector_of_node_iterators[7], 1978);
82  std::cout << "some node property values..." << std::endl;
83  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
84    std::cout << my_property_vector.get(i) << std::endl;
85  }
86  int _i=1;
87  int _ii=1;
88  edge_property_vector<list_graph, int> my_edge_property(G);
89  for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
90    my_edge_property.put(i, _i);
91    _i*=_ii; ++_ii;
92  }
93
94  std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
95  for(each_edge_iterator j=G.first_edge(); j.valid(); ++j) {
96    std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
97  }
98  std::cout << std::endl;
99
100  //std::cout << "the same for inedges of the nodes..." << std::endl;
101  //k=0;
102  //for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
103  //  for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
104  //    std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " ";
105  //  }
106  //  std::cout << std::endl;
107  //}
108
109  std::cout << "bfs from the first node" << std::endl;
110  bfs<list_graph> bfs_test(G, G.first_node());
111  bfs_test.run();
112  std::cout << "reached: ";
113  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
114    std::cout << bfs_test.reached.get(i) << " ";
115  }
116  std::cout<<std::endl;
117  std::cout << "dist: ";
118  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
119    std::cout << bfs_test.dist.get(i) << " ";
120  }
121  std::cout<<std::endl;
122
123
124  std::cout << "augmenting path flow algorithm test..." << std::endl;
125  list_graph flow_test;
126
127  node_iterator s=flow_test.add_node();
128  node_iterator v1=flow_test.add_node();
129  node_iterator v2=flow_test.add_node();
130  node_iterator v3=flow_test.add_node();
131  node_iterator v4=flow_test.add_node();
132  node_iterator t=flow_test.add_node();
133 
134  node_property_vector<list_graph, std::string> node_name(flow_test);
135  node_name.put(s, "s");
136  node_name.put(v1, "v1");
137  node_name.put(v2, "v2");
138  node_name.put(v3, "v3");
139  node_name.put(v4, "v4");
140  node_name.put(t, "t");
141
142  edge_iterator s_v1=flow_test.add_edge(s, v1);
143  edge_iterator s_v2=flow_test.add_edge(s, v2);
144  edge_iterator v1_v2=flow_test.add_edge(v1, v2);
145  edge_iterator v2_v1=flow_test.add_edge(v2, v1);
146  edge_iterator v1_v3=flow_test.add_edge(v1, v3);
147  edge_iterator v3_v2=flow_test.add_edge(v3, v2);
148  edge_iterator v2_v4=flow_test.add_edge(v2, v4);
149  edge_iterator v4_v3=flow_test.add_edge(v4, v3);
150  edge_iterator v3_t=flow_test.add_edge(v3, t);
151  edge_iterator v4_t=flow_test.add_edge(v4, t);
152
153  edge_property_vector<list_graph, int> cap(flow_test);
154
155  cap.put(s_v1, 16);
156  cap.put(s_v2, 13);
157  cap.put(v1_v2, 10);
158  cap.put(v2_v1, 4);
159  cap.put(v1_v3, 12);
160  cap.put(v3_v2, 9);
161  cap.put(v2_v4, 14);
162  cap.put(v4_v3, 7);
163  cap.put(v3_t, 20);
164  cap.put(v4_t, 4);
165
166  std::cout << "on directed graph graph" << std::endl; //<< flow_test;
167  std::cout << "names and capacity values" << std::endl;
168  for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
169    std::cout << node_name.get(i) << ": ";
170    std::cout << "out edges: ";
171    for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
172      std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
173    std::cout << "in edges: ";
174    for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
175      std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
176    std::cout << std::endl;
177  }
178
179 
180  //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
181  //  std::cout << i << " ";
182  //}
183 
184  max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap);
185  max_flow_test.run();
186
187  return 0;
188}
Note: See TracBrowser for help on using the repository browser.