|
1 #include <lemon/smart_graph.h> |
|
2 #include <lemon/kruskal.h> |
|
3 #include <lemon/graph_reader.h> |
|
4 #include <lemon/time_measure.h> |
|
5 #include <lemon/graph_to_eps.h> |
|
6 |
|
7 #include <lemon/steiner.h> |
|
8 |
|
9 #include <cstdlib> |
|
10 #include <cmath> |
|
11 |
|
12 using namespace lemon; |
|
13 using namespace lemon::dim2; |
|
14 |
|
15 using namespace std; |
|
16 |
|
17 int main(int argc, const char *argv[]) { |
|
18 std::string lgf = argc > 1 ? argv[1] : "steiner.lgf"; |
|
19 std::string eps = argc > 2 ? argv[2] : "steiner.eps"; |
|
20 |
|
21 SmartUGraph graph; |
|
22 SmartUGraph::NodeMap<bool> terminal(graph); |
|
23 SmartUGraph::NodeMap<int> label(graph); |
|
24 SmartUGraph::NodeMap<Point<double> > coord(graph); |
|
25 |
|
26 UGraphReader<SmartUGraph>(lgf, graph). |
|
27 readNodeMap("coordinates_x", xMap(coord)). |
|
28 readNodeMap("coordinates_y", yMap(coord)). |
|
29 readNodeMap("terminal", terminal).run(); |
|
30 |
|
31 SmartUGraph::UEdgeMap<double> cost(graph); |
|
32 for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) { |
|
33 cost[it] = sqrt((coord[graph.target(it)] - |
|
34 coord[graph.source(it)]).normSquare()); |
|
35 } |
|
36 |
|
37 SteinerTree<SmartUGraph> steiner(graph, cost); |
|
38 steiner.init(); |
|
39 |
|
40 for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) { |
|
41 if (terminal[it]) { |
|
42 steiner.addTerminal(it); |
|
43 } |
|
44 } |
|
45 steiner.start(); |
|
46 |
|
47 |
|
48 Palette nodepalette(0); |
|
49 nodepalette.add(Color(1.0, 1.0, 1.0)); |
|
50 nodepalette.add(Color(0.0, 1.0, 0.0)); |
|
51 nodepalette.add(Color(0.5, 0.5, 0.5)); |
|
52 SmartUGraph::NodeMap<int> nodecolor(graph); |
|
53 for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) { |
|
54 if (steiner.terminal(it)) { |
|
55 nodecolor[it] = 1; |
|
56 } else if (steiner.steiner(it)) { |
|
57 nodecolor[it] = 2; |
|
58 } else { |
|
59 nodecolor[it] = 0; |
|
60 } |
|
61 } |
|
62 |
|
63 |
|
64 Palette edgepalette(0); |
|
65 edgepalette.add(Color(0.0, 0.0, 0.0)); |
|
66 edgepalette.add(Color(1.0, 0.0, 0.0)); |
|
67 SmartUGraph::UEdgeMap<int> edgecolor(graph); |
|
68 for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) { |
|
69 edgecolor[it] = steiner.tree(it) ? 1 : 0; |
|
70 } |
|
71 |
|
72 |
|
73 graphToEps(graph, eps). |
|
74 coords(coord).undirected(). |
|
75 nodeScale(1.0).scaleToA4(). |
|
76 nodeColors(composeMap(nodepalette, nodecolor)). |
|
77 edgeColors(composeMap(edgepalette, edgecolor)). |
|
78 nodeTexts(label).nodeTextSize(8).run(); |
|
79 |
|
80 std::cout << "The tree constructed: " << eps << std::endl; |
|
81 std::cout << "The cost of the tree: " << steiner.treeValue() << std::endl; |
|
82 |
|
83 return 0; |
|
84 } |