steiner_demo.cc File Reference

---

Detailed Description

Calculating an approximate Steiner-tree.

/* -*- 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.
 *
 */


#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 <lemon/math.h>

#include <cstdlib>

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;
}

#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 <lemon/math.h>
#include <cstdlib>