[2400] | 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 | } |
---|