demo/steiner_demo.cc
author convert-repo
Thu, 04 Mar 2010 19:34:55 +0000
changeset 2659 611ced85018b
parent 2553 bfced05fa852
permissions -rw-r--r--
update tags
     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 
    37 using namespace lemon;
    38 using namespace lemon::dim2;
    39 
    40 using namespace std;
    41 
    42 int 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 }