Bug fix in heap_test.cc.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 ///\brief Calculating an approximate Steiner-tree.
23 /// Calculating an approximate Steiner-tree.
25 /// \include steiner_demo.cc
27 #include <lemon/smart_graph.h>
28 #include <lemon/kruskal.h>
29 #include <lemon/graph_reader.h>
30 #include <lemon/time_measure.h>
31 #include <lemon/graph_to_eps.h>
33 #include <lemon/steiner.h>
38 using namespace lemon;
39 using namespace lemon::dim2;
43 int main(int argc, const char *argv[]) {
44 std::string lgf = argc > 1 ? argv[1] : "steiner.lgf";
45 std::string eps = argc > 2 ? argv[2] : "steiner.eps";
48 SmartUGraph::NodeMap<bool> terminal(graph);
49 SmartUGraph::NodeMap<int> label(graph);
50 SmartUGraph::NodeMap<Point<double> > coord(graph);
52 UGraphReader<SmartUGraph>(lgf, graph).
53 readNodeMap("coordinates_x", xMap(coord)).
54 readNodeMap("coordinates_y", yMap(coord)).
55 readNodeMap("terminal", terminal).run();
57 SmartUGraph::UEdgeMap<double> cost(graph);
58 for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) {
59 cost[it] = sqrt((coord[graph.target(it)] -
60 coord[graph.source(it)]).normSquare());
63 SteinerTree<SmartUGraph> steiner(graph, cost);
66 for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) {
68 steiner.addTerminal(it);
74 Palette nodepalette(0);
75 nodepalette.add(Color(1.0, 1.0, 1.0));
76 nodepalette.add(Color(0.0, 1.0, 0.0));
77 nodepalette.add(Color(0.5, 0.5, 0.5));
78 SmartUGraph::NodeMap<int> nodecolor(graph);
79 for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) {
80 if (steiner.terminal(it)) {
82 } else if (steiner.steiner(it)) {
90 Palette edgepalette(0);
91 edgepalette.add(Color(0.0, 0.0, 0.0));
92 edgepalette.add(Color(1.0, 0.0, 0.0));
93 SmartUGraph::UEdgeMap<int> edgecolor(graph);
94 for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) {
95 edgecolor[it] = steiner.tree(it) ? 1 : 0;
99 graphToEps(graph, eps).
100 coords(coord).undirected().
101 nodeScale(1.0).scaleToA4().
102 nodeColors(composeMap(nodepalette, nodecolor)).
103 edgeColors(composeMap(edgepalette, edgecolor)).
104 nodeTexts(label).nodeTextSize(8).run();
106 std::cout << "The tree constructed: " << eps << std::endl;
107 std::cout << "The cost of the tree: " << steiner.treeValue() << std::endl;