# HG changeset patch # User deba # Date 1173268859 0 # Node ID b199ded24c19f20ecd66a670e005b8d502d9b13f # Parent ccf2a1fa1821ecf77a500e9d75cf589789ca12f9 Steiner 2-approximation demo diff -r ccf2a1fa1821 -r b199ded24c19 demo/Makefile.am --- a/demo/Makefile.am Wed Mar 07 11:57:51 2007 +0000 +++ b/demo/Makefile.am Wed Mar 07 12:00:59 2007 +0000 @@ -12,8 +12,9 @@ demo/simann_maxcut_demo.lgf \ demo/strongly_connected_orientation.lgf \ demo/sub_gad_input.lgf \ - demo/u_components.lgf - + demo/u_components.lgf \ + demo/steiner.lgf + if WANT_DEMO noinst_PROGRAMS += \ @@ -39,7 +40,8 @@ demo/topological_ordering \ demo/simann_maxcut_demo \ demo/disjoint_paths_demo \ - demo/strongly_connected_orientation + demo/strongly_connected_orientation \ + demo/steiner_demo if HAVE_GLPK noinst_PROGRAMS += demo/lp_demo demo/lp_maxflow_demo demo/mip_demo @@ -107,3 +109,5 @@ demo_disjoint_paths_demo_SOURCES = demo/disjoint_paths_demo.cc demo_strongly_connected_orientation_SOURCES = demo/strongly_connected_orientation.cc + +demo_steiner_demo_SOURCES=demo/steiner_demo.cc \ No newline at end of file diff -r ccf2a1fa1821 -r b199ded24c19 demo/steiner.lgf --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/demo/steiner.lgf Wed Mar 07 12:00:59 2007 +0000 @@ -0,0 +1,303 @@ +@nodeset +coordinates_x coordinates_y label terminal +-251.856 -202.321 0 1 +-331.765 100.719 1 0 +-273.677 -294.883 2 0 +-377.147 -85.369 3 0 +169.068 132.547 4 0 +453.494 43.7303 5 0 +350.694 -81.2848 6 0 +-295.393 211.455 7 0 +-231.281 -62.2543 8 0 +275.941 118.221 9 0 +311.816 220.248 10 0 +234.152 -433.718 11 0 +146.458 422.137 12 0 +105.796 -281.078 13 0 +-284.598 -120.027 14 0 +321.329 295.308 15 0 +47.3951 306.406 16 0 +-189.908 -188.032 17 0 +-15.3932 -179.904 18 0 +-178.559 80.3029 19 0 +231.219 332.276 20 0 +314.277 -37.9572 21 0 +412.918 91.483 22 1 +-288.281 10.409 23 0 +-265.853 -415.164 24 1 +357.609 -190.755 25 0 +170.989 275.074 26 1 +-454.346 132.702 27 1 +37.385 -21.8462 28 0 +157.624 325.213 29 0 +349.774 22.435 30 0 +-53.4642 -78.4002 31 0 +-209.404 -275.264 32 0 +226.943 93.2239 33 0 +-415.266 -226.887 34 0 +-268.299 152.735 35 0 +80.0752 337.882 36 0 +-107.322 -328.854 37 0 +118.71 -56.0308 38 1 +257.804 417.75 39 0 +-5.41726 302.825 40 0 +-319.74 -186.925 41 0 +275.381 277.069 42 0 +-273.248 319.744 43 0 +-43.6017 -208.328 44 0 +166.639 -134.903 45 0 +-54.1813 323.637 46 0 +286.634 57.5531 47 0 +426.828 245.989 48 0 +-357.602 220.391 49 0 +135.626 372.331 50 0 +-21.8318 430.892 51 0 +-406.689 46.2421 52 0 +-246.874 262.591 53 0 +-370.766 -20.5267 54 0 +-14.7567 -328.157 55 0 +387.598 40.9046 56 0 +-279.35 -247.789 57 1 +116.726 284.452 58 0 +440.353 141.885 59 0 +-171.65 355.372 60 1 +-207.145 -368.556 61 0 +-369.168 178.735 62 1 +-45.5162 85.4527 63 0 +135.203 71.4192 64 0 +-351.597 -250.799 65 0 +-453.398 -15.6638 66 0 +234.039 -359.178 67 0 +-346.344 349.928 68 0 +4.38307 40.7204 69 0 +224.516 249.259 70 0 +-105.49 22.5721 71 1 +147.119 -215.924 72 0 +-408.527 96.861 73 0 +-99.522 268.879 74 0 +-1.57169 363.155 75 0 +347.538 92.4063 76 0 +353.409 183.093 77 0 +416.442 -69.8499 78 0 +-58.1027 -422.666 79 0 +227.968 -76.286 80 0 +-323.979 42.9237 81 0 +84.2308 -199.473 82 0 +56.538 -83.469 83 0 +244.34 -234.403 84 0 +-361.409 -146.916 85 0 +395.636 189.561 86 0 +-89.832 464.4 87 0 +230.042 199.124 88 0 +-93.6872 145.66 89 1 +-202.746 -118.087 90 0 +-57.6298 207.792 91 0 +377.074 298.05 92 0 +-111.722 83.101 93 0 +279.51 -133.648 94 0 +66.5975 494.601 95 1 +105.518 204.789 96 0 +-324.108 -84.4418 97 1 +-183.456 440.555 98 0 +177.565 215.632 99 0 +@uedgeset + label +38 28 0 +56 5 2 +75 16 3 +40 16 4 +92 48 5 +74 53 8 +88 70 9 +68 43 10 +58 26 11 +69 31 12 +14 0 13 +61 37 14 +73 27 16 +59 5 17 +17 0 18 +29 26 19 +56 22 21 +21 6 22 +55 37 24 +61 32 26 +57 0 27 +93 89 28 +82 45 29 +94 80 30 +38 31 31 +91 89 32 +37 32 33 +66 52 34 +59 22 35 +65 41 36 +99 58 37 +44 18 38 +62 49 40 +83 45 41 +33 4 42 +93 63 43 +50 29 44 +85 3 45 +98 87 46 +81 23 47 +9 4 48 +86 48 49 +69 28 50 +81 54 51 +46 40 52 +84 67 53 +75 36 56 +47 33 58 +77 10 59 +90 14 60 +75 46 62 +81 1 63 +26 20 64 +70 4 65 +97 3 66 +88 10 67 +58 50 68 +92 86 70 +47 9 71 +90 8 75 +49 7 76 +54 23 77 +91 35 79 +42 10 80 +65 34 81 +51 50 82 +86 77 83 +76 30 84 +99 20 86 +42 15 87 +42 20 88 +64 38 89 +78 6 90 +47 30 91 +67 11 93 +78 30 94 +64 28 95 +82 72 96 +76 9 97 +72 13 98 +86 59 100 +69 63 102 +91 74 103 +62 7 105 +44 37 106 +51 12 107 +76 56 108 +50 12 109 +95 51 110 +35 19 111 +30 21 112 +88 9 113 +98 60 114 +73 62 115 +70 42 117 +71 63 118 +85 34 121 +97 54 122 +20 15 123 +39 20 124 +65 2 125 +76 59 126 +90 17 127 +77 76 129 +57 41 130 +23 8 131 +71 19 132 +78 56 133 +91 53 134 +53 46 135 +80 21 137 +72 45 138 +97 8 139 +94 25 141 +62 27 142 +58 36 144 +93 71 145 +57 2 146 +92 10 147 +88 77 148 +91 63 149 +17 2 152 +73 1 153 +55 18 155 +50 20 157 +66 54 158 +51 36 159 +78 5 160 +99 70 161 +87 60 162 +60 53 163 +97 85 164 +97 14 166 +89 19 167 +82 18 169 +85 41 170 +99 96 171 +73 52 172 +92 15 173 +81 52 174 +83 18 176 +41 14 178 +32 17 179 +96 36 180 +74 40 182 +7 1 183 +39 12 185 +94 6 187 +83 38 188 +24 2 189 +32 18 190 +66 3 192 +71 31 194 +68 49 203 +23 19 204 +43 7 208 +96 16 209 +61 2 210 +96 4 211 +64 45 212 +91 16 213 +84 72 214 +66 27 215 +67 13 216 +71 8 217 +19 1 218 +87 46 219 +94 72 220 +84 25 221 +60 43 222 +18 13 225 +35 7 226 +51 46 227 +80 47 229 +80 45 230 +79 55 231 +90 71 232 +64 47 233 +64 4 234 +53 7 236 +64 63 237 +98 68 238 +79 61 239 +96 63 242 +78 25 243 +31 18 244 +90 18 245 +13 11 246 +95 39 247 +95 87 250 +79 24 251 +66 34 252 +92 39 253 +79 13 254 +34 24 255 +68 27 256 +25 11 257 +24 11 259 +@end diff -r ccf2a1fa1821 -r b199ded24c19 demo/steiner_demo.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/demo/steiner_demo.cc Wed Mar 07 12:00:59 2007 +0000 @@ -0,0 +1,84 @@ +#include +#include +#include +#include +#include + +#include + +#include +#include + +using namespace lemon; +using namespace lemon::dim2; + +using namespace std; + +int main(int argc, const char *argv[]) { + std::string lgf = argc > 1 ? argv[1] : "steiner.lgf"; + std::string eps = argc > 2 ? argv[2] : "steiner.eps"; + + SmartUGraph graph; + SmartUGraph::NodeMap terminal(graph); + SmartUGraph::NodeMap label(graph); + SmartUGraph::NodeMap > coord(graph); + + UGraphReader(lgf, graph). + readNodeMap("coordinates_x", xMap(coord)). + readNodeMap("coordinates_y", yMap(coord)). + readNodeMap("terminal", terminal).run(); + + SmartUGraph::UEdgeMap cost(graph); + for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) { + cost[it] = sqrt((coord[graph.target(it)] - + coord[graph.source(it)]).normSquare()); + } + + SteinerTree steiner(graph, cost); + steiner.init(); + + for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) { + if (terminal[it]) { + steiner.addTerminal(it); + } + } + steiner.start(); + + + Palette nodepalette(0); + nodepalette.add(Color(1.0, 1.0, 1.0)); + nodepalette.add(Color(0.0, 1.0, 0.0)); + nodepalette.add(Color(0.5, 0.5, 0.5)); + SmartUGraph::NodeMap nodecolor(graph); + for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) { + if (steiner.terminal(it)) { + nodecolor[it] = 1; + } else if (steiner.steiner(it)) { + nodecolor[it] = 2; + } else { + nodecolor[it] = 0; + } + } + + + Palette edgepalette(0); + edgepalette.add(Color(0.0, 0.0, 0.0)); + edgepalette.add(Color(1.0, 0.0, 0.0)); + SmartUGraph::UEdgeMap edgecolor(graph); + for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) { + edgecolor[it] = steiner.tree(it) ? 1 : 0; + } + + + graphToEps(graph, eps). + coords(coord).undirected(). + nodeScale(1.0).scaleToA4(). + nodeColors(composeMap(nodepalette, nodecolor)). + edgeColors(composeMap(edgepalette, edgecolor)). + nodeTexts(label).nodeTextSize(8).run(); + + std::cout << "The tree constructed: " << eps << std::endl; + std::cout << "The cost of the tree: " << steiner.treeValue() << std::endl; + + return 0; +}