COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/steiner_demo.cc @ 2400:b199ded24c19

Last change on this file since 2400:b199ded24c19 was 2400:b199ded24c19, checked in by Balazs Dezso, 13 years ago

Steiner 2-approximation demo

File size: 2.3 KB
Line 
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
12using namespace lemon;
13using namespace lemon::dim2;
14
15using namespace std;
16
17int 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}
Note: See TracBrowser for help on using the repository browser.