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 <lemon/smart_graph.h>
deba@2400: #include <lemon/kruskal.h>
deba@2400: #include <lemon/graph_reader.h>
deba@2400: #include <lemon/time_measure.h>
deba@2400: #include <lemon/graph_to_eps.h>
deba@2400: 
deba@2400: #include <lemon/steiner.h>
deba@2400: 
deba@2400: #include <cstdlib>
deba@2400: #include <cmath>
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<bool> terminal(graph);
deba@2400:   SmartUGraph::NodeMap<int> label(graph);
deba@2400:   SmartUGraph::NodeMap<Point<double> > coord(graph);
deba@2400:   
deba@2400:   UGraphReader<SmartUGraph>(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<double> 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<SmartUGraph> 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<int> 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<int> 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: }