/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2008

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 ///\ingroup demos

 ///\file

 ///\brief Calculating an approximate Steiner-tree.

 ///

 /// Calculating an approximate Steiner-tree.

 ///

 /// \include steiner_demo.cc

 #include <lemon/smart_graph.h>

 #include <lemon/kruskal.h>

 #include <lemon/graph_reader.h>

 #include <lemon/time_measure.h>

 #include <lemon/graph_to_eps.h>

 #include <lemon/steiner.h>

 #include <cstdlib>

 #include <cmath>

 using namespace lemon;

 using namespace lemon::dim2;

 using namespace std;

 int main(int argc, const char *argv[]) {

   std::string lgf = argc > 1 ? argv[1] : "steiner.lgf";

   std::string eps = argc > 2 ? argv[2] : "steiner.eps";

   SmartUGraph graph;

   SmartUGraph::NodeMap<bool> terminal(graph);

   SmartUGraph::NodeMap<int> label(graph);

   SmartUGraph::NodeMap<Point<double> > coord(graph);

   UGraphReader<SmartUGraph>(lgf, graph).

     readNodeMap("coordinates_x", xMap(coord)).

     readNodeMap("coordinates_y", yMap(coord)).

     readNodeMap("terminal", terminal).run();

   SmartUGraph::UEdgeMap<double> cost(graph);

   for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) {

     cost[it] = sqrt((coord[graph.target(it)] - 

                      coord[graph.source(it)]).normSquare());

   }

   SteinerTree<SmartUGraph> steiner(graph, cost);

   steiner.init();

   for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) {

     if (terminal[it]) {

       steiner.addTerminal(it);

     }

   }

   steiner.start();

   Palette nodepalette(0);

   nodepalette.add(Color(1.0, 1.0, 1.0));

   nodepalette.add(Color(0.0, 1.0, 0.0));

   nodepalette.add(Color(0.5, 0.5, 0.5));

   SmartUGraph::NodeMap<int> nodecolor(graph);

   for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) {

     if (steiner.terminal(it)) {

       nodecolor[it] = 1;

     } else if (steiner.steiner(it)) {

       nodecolor[it] = 2;

     } else {

       nodecolor[it] = 0;

     }

   }

   Palette edgepalette(0);

   edgepalette.add(Color(0.0, 0.0, 0.0));

   edgepalette.add(Color(1.0, 0.0, 0.0));

   SmartUGraph::UEdgeMap<int> edgecolor(graph);

   for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) {

     edgecolor[it] = steiner.tree(it) ? 1 : 0;

   }

   graphToEps(graph, eps).

     coords(coord).undirected().

     nodeScale(1.0).scaleToA4().

     nodeColors(composeMap(nodepalette, nodecolor)).

     edgeColors(composeMap(edgepalette, edgecolor)).

     nodeTexts(label).nodeTextSize(8).run();

   std::cout << "The tree constructed: " << eps << std::endl;

   std::cout << "The cost of the tree: " << steiner.treeValue() << std::endl;

   return 0;

 }