kpeter@2472: /* -*- C++ -*- kpeter@2472: * kpeter@2472: * This file is a part of LEMON, a generic C++ optimization library kpeter@2472: * kpeter@2472: * Copyright (C) 2003-2007 kpeter@2472: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport kpeter@2472: * (Egervary Research Group on Combinatorial Optimization, EGRES). kpeter@2472: * kpeter@2472: * Permission to use, modify and distribute this software is granted kpeter@2472: * provided that this copyright notice appears in all copies. For kpeter@2472: * precise terms see the accompanying LICENSE file. kpeter@2472: * kpeter@2472: * This software is provided "AS IS" with no warranty of any kind, kpeter@2472: * express or implied, and with no claim as to its suitability for any kpeter@2472: * purpose. kpeter@2472: * kpeter@2472: */ kpeter@2472: deba@2492: ///\ingroup demos deba@2492: ///\file deba@2492: ///\brief Calculating an approximate Steiner-tree. deba@2492: /// deba@2492: /// Calculating an approximate Steiner-tree. deba@2492: /// deba@2492: /// \include steiner_demo.cc deba@2492: deba@2400: #include deba@2400: #include deba@2400: #include deba@2400: #include deba@2400: #include deba@2400: deba@2400: #include deba@2400: deba@2400: #include deba@2400: #include deba@2400: deba@2400: using namespace lemon; deba@2400: using namespace lemon::dim2; deba@2400: deba@2400: using namespace std; deba@2400: deba@2400: int main(int argc, const char *argv[]) { deba@2400: std::string lgf = argc > 1 ? argv[1] : "steiner.lgf"; deba@2400: std::string eps = argc > 2 ? argv[2] : "steiner.eps"; deba@2400: deba@2400: SmartUGraph graph; deba@2400: SmartUGraph::NodeMap terminal(graph); deba@2400: SmartUGraph::NodeMap label(graph); deba@2400: SmartUGraph::NodeMap > coord(graph); deba@2400: deba@2400: UGraphReader(lgf, graph). deba@2400: readNodeMap("coordinates_x", xMap(coord)). deba@2400: readNodeMap("coordinates_y", yMap(coord)). deba@2400: readNodeMap("terminal", terminal).run(); deba@2400: deba@2400: SmartUGraph::UEdgeMap cost(graph); deba@2400: for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) { deba@2400: cost[it] = sqrt((coord[graph.target(it)] - deba@2400: coord[graph.source(it)]).normSquare()); deba@2400: } deba@2400: deba@2400: SteinerTree steiner(graph, cost); deba@2400: steiner.init(); deba@2400: deba@2400: for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) { deba@2400: if (terminal[it]) { deba@2400: steiner.addTerminal(it); deba@2400: } deba@2400: } deba@2400: steiner.start(); deba@2400: deba@2400: deba@2400: Palette nodepalette(0); deba@2400: nodepalette.add(Color(1.0, 1.0, 1.0)); deba@2400: nodepalette.add(Color(0.0, 1.0, 0.0)); deba@2400: nodepalette.add(Color(0.5, 0.5, 0.5)); deba@2400: SmartUGraph::NodeMap nodecolor(graph); deba@2400: for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) { deba@2400: if (steiner.terminal(it)) { deba@2400: nodecolor[it] = 1; deba@2400: } else if (steiner.steiner(it)) { deba@2400: nodecolor[it] = 2; deba@2400: } else { deba@2400: nodecolor[it] = 0; deba@2400: } deba@2400: } deba@2400: deba@2400: deba@2400: Palette edgepalette(0); deba@2400: edgepalette.add(Color(0.0, 0.0, 0.0)); deba@2400: edgepalette.add(Color(1.0, 0.0, 0.0)); deba@2400: SmartUGraph::UEdgeMap edgecolor(graph); deba@2400: for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) { deba@2400: edgecolor[it] = steiner.tree(it) ? 1 : 0; deba@2400: } deba@2400: deba@2400: deba@2400: graphToEps(graph, eps). deba@2400: coords(coord).undirected(). deba@2400: nodeScale(1.0).scaleToA4(). deba@2400: nodeColors(composeMap(nodepalette, nodecolor)). deba@2400: edgeColors(composeMap(edgepalette, edgecolor)). deba@2400: nodeTexts(label).nodeTextSize(8).run(); deba@2400: deba@2400: std::cout << "The tree constructed: " << eps << std::endl; deba@2400: std::cout << "The cost of the tree: " << steiner.treeValue() << std::endl; deba@2400: deba@2400: return 0; deba@2400: }