COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/steiner_demo.cc @ 2569:12c2c5c4330b

Last change on this file since 2569:12c2c5c4330b was 2569:12c2c5c4330b, checked in by Alpar Juttner, 13 years ago

#include<cmath> -> #include<lemon/math.h>

File size: 3.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19///\ingroup demos
20///\file
21///\brief Calculating an approximate Steiner-tree.
22///
23/// Calculating an approximate Steiner-tree.
24///
25/// \include steiner_demo.cc
26
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>
32#include <lemon/steiner.h>
33#include <lemon/math.h>
34
35#include <cstdlib>
36
37using namespace lemon;
38using namespace lemon::dim2;
39
40using namespace std;
41
42int main(int argc, const char *argv[]) {
43  std::string lgf = argc > 1 ? argv[1] : "steiner.lgf";
44  std::string eps = argc > 2 ? argv[2] : "steiner.eps";
45
46  SmartUGraph graph;
47  SmartUGraph::NodeMap<bool> terminal(graph);
48  SmartUGraph::NodeMap<int> label(graph);
49  SmartUGraph::NodeMap<Point<double> > coord(graph);
50 
51  UGraphReader<SmartUGraph>(lgf, graph).
52    readNodeMap("coordinates_x", xMap(coord)).
53    readNodeMap("coordinates_y", yMap(coord)).
54    readNodeMap("terminal", terminal).run();
55
56  SmartUGraph::UEdgeMap<double> cost(graph);
57  for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) {
58    cost[it] = sqrt((coord[graph.target(it)] -
59                     coord[graph.source(it)]).normSquare());
60  }
61 
62  SteinerTree<SmartUGraph> steiner(graph, cost);
63  steiner.init();
64
65  for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) {
66    if (terminal[it]) {
67      steiner.addTerminal(it);
68    }
69  }
70  steiner.start();
71
72
73  Palette nodepalette(0);
74  nodepalette.add(Color(1.0, 1.0, 1.0));
75  nodepalette.add(Color(0.0, 1.0, 0.0));
76  nodepalette.add(Color(0.5, 0.5, 0.5));
77  SmartUGraph::NodeMap<int> nodecolor(graph);
78  for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) {
79    if (steiner.terminal(it)) {
80      nodecolor[it] = 1;
81    } else if (steiner.steiner(it)) {
82      nodecolor[it] = 2;
83    } else {
84      nodecolor[it] = 0;
85    }
86  }
87
88
89  Palette edgepalette(0);
90  edgepalette.add(Color(0.0, 0.0, 0.0));
91  edgepalette.add(Color(1.0, 0.0, 0.0));
92  SmartUGraph::UEdgeMap<int> edgecolor(graph);
93  for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) {
94    edgecolor[it] = steiner.tree(it) ? 1 : 0;
95  }
96
97
98  graphToEps(graph, eps).
99    coords(coord).undirected().
100    nodeScale(1.0).scaleToA4().
101    nodeColors(composeMap(nodepalette, nodecolor)).
102    edgeColors(composeMap(edgepalette, edgecolor)).
103    nodeTexts(label).nodeTextSize(8).run();
104
105  std::cout << "The tree constructed: " << eps << std::endl;
106  std::cout << "The cost of the tree: " << steiner.treeValue() << std::endl;
107
108  return 0;
109}
Note: See TracBrowser for help on using the repository browser.