1.1 --- a/demo/Makefile.am Wed Mar 07 11:57:51 2007 +0000
1.2 +++ b/demo/Makefile.am Wed Mar 07 12:00:59 2007 +0000
1.3 @@ -12,8 +12,9 @@
1.4 demo/simann_maxcut_demo.lgf \
1.5 demo/strongly_connected_orientation.lgf \
1.6 demo/sub_gad_input.lgf \
1.7 - demo/u_components.lgf
1.8 -
1.9 + demo/u_components.lgf \
1.10 + demo/steiner.lgf
1.11 +
1.12 if WANT_DEMO
1.13
1.14 noinst_PROGRAMS += \
1.15 @@ -39,7 +40,8 @@
1.16 demo/topological_ordering \
1.17 demo/simann_maxcut_demo \
1.18 demo/disjoint_paths_demo \
1.19 - demo/strongly_connected_orientation
1.20 + demo/strongly_connected_orientation \
1.21 + demo/steiner_demo
1.22
1.23 if HAVE_GLPK
1.24 noinst_PROGRAMS += demo/lp_demo demo/lp_maxflow_demo demo/mip_demo
1.25 @@ -107,3 +109,5 @@
1.26 demo_disjoint_paths_demo_SOURCES = demo/disjoint_paths_demo.cc
1.27
1.28 demo_strongly_connected_orientation_SOURCES = demo/strongly_connected_orientation.cc
1.29 +
1.30 +demo_steiner_demo_SOURCES=demo/steiner_demo.cc
1.31 \ No newline at end of file
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/demo/steiner.lgf Wed Mar 07 12:00:59 2007 +0000
2.3 @@ -0,0 +1,303 @@
2.4 +@nodeset
2.5 +coordinates_x coordinates_y label terminal
2.6 +-251.856 -202.321 0 1
2.7 +-331.765 100.719 1 0
2.8 +-273.677 -294.883 2 0
2.9 +-377.147 -85.369 3 0
2.10 +169.068 132.547 4 0
2.11 +453.494 43.7303 5 0
2.12 +350.694 -81.2848 6 0
2.13 +-295.393 211.455 7 0
2.14 +-231.281 -62.2543 8 0
2.15 +275.941 118.221 9 0
2.16 +311.816 220.248 10 0
2.17 +234.152 -433.718 11 0
2.18 +146.458 422.137 12 0
2.19 +105.796 -281.078 13 0
2.20 +-284.598 -120.027 14 0
2.21 +321.329 295.308 15 0
2.22 +47.3951 306.406 16 0
2.23 +-189.908 -188.032 17 0
2.24 +-15.3932 -179.904 18 0
2.25 +-178.559 80.3029 19 0
2.26 +231.219 332.276 20 0
2.27 +314.277 -37.9572 21 0
2.28 +412.918 91.483 22 1
2.29 +-288.281 10.409 23 0
2.30 +-265.853 -415.164 24 1
2.31 +357.609 -190.755 25 0
2.32 +170.989 275.074 26 1
2.33 +-454.346 132.702 27 1
2.34 +37.385 -21.8462 28 0
2.35 +157.624 325.213 29 0
2.36 +349.774 22.435 30 0
2.37 +-53.4642 -78.4002 31 0
2.38 +-209.404 -275.264 32 0
2.39 +226.943 93.2239 33 0
2.40 +-415.266 -226.887 34 0
2.41 +-268.299 152.735 35 0
2.42 +80.0752 337.882 36 0
2.43 +-107.322 -328.854 37 0
2.44 +118.71 -56.0308 38 1
2.45 +257.804 417.75 39 0
2.46 +-5.41726 302.825 40 0
2.47 +-319.74 -186.925 41 0
2.48 +275.381 277.069 42 0
2.49 +-273.248 319.744 43 0
2.50 +-43.6017 -208.328 44 0
2.51 +166.639 -134.903 45 0
2.52 +-54.1813 323.637 46 0
2.53 +286.634 57.5531 47 0
2.54 +426.828 245.989 48 0
2.55 +-357.602 220.391 49 0
2.56 +135.626 372.331 50 0
2.57 +-21.8318 430.892 51 0
2.58 +-406.689 46.2421 52 0
2.59 +-246.874 262.591 53 0
2.60 +-370.766 -20.5267 54 0
2.61 +-14.7567 -328.157 55 0
2.62 +387.598 40.9046 56 0
2.63 +-279.35 -247.789 57 1
2.64 +116.726 284.452 58 0
2.65 +440.353 141.885 59 0
2.66 +-171.65 355.372 60 1
2.67 +-207.145 -368.556 61 0
2.68 +-369.168 178.735 62 1
2.69 +-45.5162 85.4527 63 0
2.70 +135.203 71.4192 64 0
2.71 +-351.597 -250.799 65 0
2.72 +-453.398 -15.6638 66 0
2.73 +234.039 -359.178 67 0
2.74 +-346.344 349.928 68 0
2.75 +4.38307 40.7204 69 0
2.76 +224.516 249.259 70 0
2.77 +-105.49 22.5721 71 1
2.78 +147.119 -215.924 72 0
2.79 +-408.527 96.861 73 0
2.80 +-99.522 268.879 74 0
2.81 +-1.57169 363.155 75 0
2.82 +347.538 92.4063 76 0
2.83 +353.409 183.093 77 0
2.84 +416.442 -69.8499 78 0
2.85 +-58.1027 -422.666 79 0
2.86 +227.968 -76.286 80 0
2.87 +-323.979 42.9237 81 0
2.88 +84.2308 -199.473 82 0
2.89 +56.538 -83.469 83 0
2.90 +244.34 -234.403 84 0
2.91 +-361.409 -146.916 85 0
2.92 +395.636 189.561 86 0
2.93 +-89.832 464.4 87 0
2.94 +230.042 199.124 88 0
2.95 +-93.6872 145.66 89 1
2.96 +-202.746 -118.087 90 0
2.97 +-57.6298 207.792 91 0
2.98 +377.074 298.05 92 0
2.99 +-111.722 83.101 93 0
2.100 +279.51 -133.648 94 0
2.101 +66.5975 494.601 95 1
2.102 +105.518 204.789 96 0
2.103 +-324.108 -84.4418 97 1
2.104 +-183.456 440.555 98 0
2.105 +177.565 215.632 99 0
2.106 +@uedgeset
2.107 + label
2.108 +38 28 0
2.109 +56 5 2
2.110 +75 16 3
2.111 +40 16 4
2.112 +92 48 5
2.113 +74 53 8
2.114 +88 70 9
2.115 +68 43 10
2.116 +58 26 11
2.117 +69 31 12
2.118 +14 0 13
2.119 +61 37 14
2.120 +73 27 16
2.121 +59 5 17
2.122 +17 0 18
2.123 +29 26 19
2.124 +56 22 21
2.125 +21 6 22
2.126 +55 37 24
2.127 +61 32 26
2.128 +57 0 27
2.129 +93 89 28
2.130 +82 45 29
2.131 +94 80 30
2.132 +38 31 31
2.133 +91 89 32
2.134 +37 32 33
2.135 +66 52 34
2.136 +59 22 35
2.137 +65 41 36
2.138 +99 58 37
2.139 +44 18 38
2.140 +62 49 40
2.141 +83 45 41
2.142 +33 4 42
2.143 +93 63 43
2.144 +50 29 44
2.145 +85 3 45
2.146 +98 87 46
2.147 +81 23 47
2.148 +9 4 48
2.149 +86 48 49
2.150 +69 28 50
2.151 +81 54 51
2.152 +46 40 52
2.153 +84 67 53
2.154 +75 36 56
2.155 +47 33 58
2.156 +77 10 59
2.157 +90 14 60
2.158 +75 46 62
2.159 +81 1 63
2.160 +26 20 64
2.161 +70 4 65
2.162 +97 3 66
2.163 +88 10 67
2.164 +58 50 68
2.165 +92 86 70
2.166 +47 9 71
2.167 +90 8 75
2.168 +49 7 76
2.169 +54 23 77
2.170 +91 35 79
2.171 +42 10 80
2.172 +65 34 81
2.173 +51 50 82
2.174 +86 77 83
2.175 +76 30 84
2.176 +99 20 86
2.177 +42 15 87
2.178 +42 20 88
2.179 +64 38 89
2.180 +78 6 90
2.181 +47 30 91
2.182 +67 11 93
2.183 +78 30 94
2.184 +64 28 95
2.185 +82 72 96
2.186 +76 9 97
2.187 +72 13 98
2.188 +86 59 100
2.189 +69 63 102
2.190 +91 74 103
2.191 +62 7 105
2.192 +44 37 106
2.193 +51 12 107
2.194 +76 56 108
2.195 +50 12 109
2.196 +95 51 110
2.197 +35 19 111
2.198 +30 21 112
2.199 +88 9 113
2.200 +98 60 114
2.201 +73 62 115
2.202 +70 42 117
2.203 +71 63 118
2.204 +85 34 121
2.205 +97 54 122
2.206 +20 15 123
2.207 +39 20 124
2.208 +65 2 125
2.209 +76 59 126
2.210 +90 17 127
2.211 +77 76 129
2.212 +57 41 130
2.213 +23 8 131
2.214 +71 19 132
2.215 +78 56 133
2.216 +91 53 134
2.217 +53 46 135
2.218 +80 21 137
2.219 +72 45 138
2.220 +97 8 139
2.221 +94 25 141
2.222 +62 27 142
2.223 +58 36 144
2.224 +93 71 145
2.225 +57 2 146
2.226 +92 10 147
2.227 +88 77 148
2.228 +91 63 149
2.229 +17 2 152
2.230 +73 1 153
2.231 +55 18 155
2.232 +50 20 157
2.233 +66 54 158
2.234 +51 36 159
2.235 +78 5 160
2.236 +99 70 161
2.237 +87 60 162
2.238 +60 53 163
2.239 +97 85 164
2.240 +97 14 166
2.241 +89 19 167
2.242 +82 18 169
2.243 +85 41 170
2.244 +99 96 171
2.245 +73 52 172
2.246 +92 15 173
2.247 +81 52 174
2.248 +83 18 176
2.249 +41 14 178
2.250 +32 17 179
2.251 +96 36 180
2.252 +74 40 182
2.253 +7 1 183
2.254 +39 12 185
2.255 +94 6 187
2.256 +83 38 188
2.257 +24 2 189
2.258 +32 18 190
2.259 +66 3 192
2.260 +71 31 194
2.261 +68 49 203
2.262 +23 19 204
2.263 +43 7 208
2.264 +96 16 209
2.265 +61 2 210
2.266 +96 4 211
2.267 +64 45 212
2.268 +91 16 213
2.269 +84 72 214
2.270 +66 27 215
2.271 +67 13 216
2.272 +71 8 217
2.273 +19 1 218
2.274 +87 46 219
2.275 +94 72 220
2.276 +84 25 221
2.277 +60 43 222
2.278 +18 13 225
2.279 +35 7 226
2.280 +51 46 227
2.281 +80 47 229
2.282 +80 45 230
2.283 +79 55 231
2.284 +90 71 232
2.285 +64 47 233
2.286 +64 4 234
2.287 +53 7 236
2.288 +64 63 237
2.289 +98 68 238
2.290 +79 61 239
2.291 +96 63 242
2.292 +78 25 243
2.293 +31 18 244
2.294 +90 18 245
2.295 +13 11 246
2.296 +95 39 247
2.297 +95 87 250
2.298 +79 24 251
2.299 +66 34 252
2.300 +92 39 253
2.301 +79 13 254
2.302 +34 24 255
2.303 +68 27 256
2.304 +25 11 257
2.305 +24 11 259
2.306 +@end
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/demo/steiner_demo.cc Wed Mar 07 12:00:59 2007 +0000
3.3 @@ -0,0 +1,84 @@
3.4 +#include <lemon/smart_graph.h>
3.5 +#include <lemon/kruskal.h>
3.6 +#include <lemon/graph_reader.h>
3.7 +#include <lemon/time_measure.h>
3.8 +#include <lemon/graph_to_eps.h>
3.9 +
3.10 +#include <lemon/steiner.h>
3.11 +
3.12 +#include <cstdlib>
3.13 +#include <cmath>
3.14 +
3.15 +using namespace lemon;
3.16 +using namespace lemon::dim2;
3.17 +
3.18 +using namespace std;
3.19 +
3.20 +int main(int argc, const char *argv[]) {
3.21 + std::string lgf = argc > 1 ? argv[1] : "steiner.lgf";
3.22 + std::string eps = argc > 2 ? argv[2] : "steiner.eps";
3.23 +
3.24 + SmartUGraph graph;
3.25 + SmartUGraph::NodeMap<bool> terminal(graph);
3.26 + SmartUGraph::NodeMap<int> label(graph);
3.27 + SmartUGraph::NodeMap<Point<double> > coord(graph);
3.28 +
3.29 + UGraphReader<SmartUGraph>(lgf, graph).
3.30 + readNodeMap("coordinates_x", xMap(coord)).
3.31 + readNodeMap("coordinates_y", yMap(coord)).
3.32 + readNodeMap("terminal", terminal).run();
3.33 +
3.34 + SmartUGraph::UEdgeMap<double> cost(graph);
3.35 + for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) {
3.36 + cost[it] = sqrt((coord[graph.target(it)] -
3.37 + coord[graph.source(it)]).normSquare());
3.38 + }
3.39 +
3.40 + SteinerTree<SmartUGraph> steiner(graph, cost);
3.41 + steiner.init();
3.42 +
3.43 + for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) {
3.44 + if (terminal[it]) {
3.45 + steiner.addTerminal(it);
3.46 + }
3.47 + }
3.48 + steiner.start();
3.49 +
3.50 +
3.51 + Palette nodepalette(0);
3.52 + nodepalette.add(Color(1.0, 1.0, 1.0));
3.53 + nodepalette.add(Color(0.0, 1.0, 0.0));
3.54 + nodepalette.add(Color(0.5, 0.5, 0.5));
3.55 + SmartUGraph::NodeMap<int> nodecolor(graph);
3.56 + for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) {
3.57 + if (steiner.terminal(it)) {
3.58 + nodecolor[it] = 1;
3.59 + } else if (steiner.steiner(it)) {
3.60 + nodecolor[it] = 2;
3.61 + } else {
3.62 + nodecolor[it] = 0;
3.63 + }
3.64 + }
3.65 +
3.66 +
3.67 + Palette edgepalette(0);
3.68 + edgepalette.add(Color(0.0, 0.0, 0.0));
3.69 + edgepalette.add(Color(1.0, 0.0, 0.0));
3.70 + SmartUGraph::UEdgeMap<int> edgecolor(graph);
3.71 + for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) {
3.72 + edgecolor[it] = steiner.tree(it) ? 1 : 0;
3.73 + }
3.74 +
3.75 +
3.76 + graphToEps(graph, eps).
3.77 + coords(coord).undirected().
3.78 + nodeScale(1.0).scaleToA4().
3.79 + nodeColors(composeMap(nodepalette, nodecolor)).
3.80 + edgeColors(composeMap(edgepalette, edgecolor)).
3.81 + nodeTexts(label).nodeTextSize(8).run();
3.82 +
3.83 + std::cout << "The tree constructed: " << eps << std::endl;
3.84 + std::cout << "The cost of the tree: " << steiner.treeValue() << std::endl;
3.85 +
3.86 + return 0;
3.87 +}