demo/steiner_demo.cc
author klao
Tue, 29 Jan 2008 03:39:05 +0000
changeset 2559 75dd6d724f26
parent 2492 387f6ff851ef
child 2569 12c2c5c4330b
permissions -rw-r--r--
grid_ugraph.h: fixed #18 (global functions inlined)
kpeter@2472
     1
/* -*- C++ -*-
kpeter@2472
     2
 *
kpeter@2472
     3
 * This file is a part of LEMON, a generic C++ optimization library
kpeter@2472
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
kpeter@2472
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@2472
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@2472
     8
 *
kpeter@2472
     9
 * Permission to use, modify and distribute this software is granted
kpeter@2472
    10
 * provided that this copyright notice appears in all copies. For
kpeter@2472
    11
 * precise terms see the accompanying LICENSE file.
kpeter@2472
    12
 *
kpeter@2472
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@2472
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@2472
    15
 * purpose.
kpeter@2472
    16
 *
kpeter@2472
    17
 */
kpeter@2472
    18
deba@2492
    19
///\ingroup demos
deba@2492
    20
///\file
deba@2492
    21
///\brief Calculating an approximate Steiner-tree.
deba@2492
    22
///
deba@2492
    23
/// Calculating an approximate Steiner-tree.
deba@2492
    24
///
deba@2492
    25
/// \include steiner_demo.cc
deba@2492
    26
deba@2400
    27
#include <lemon/smart_graph.h>
deba@2400
    28
#include <lemon/kruskal.h>
deba@2400
    29
#include <lemon/graph_reader.h>
deba@2400
    30
#include <lemon/time_measure.h>
deba@2400
    31
#include <lemon/graph_to_eps.h>
deba@2400
    32
deba@2400
    33
#include <lemon/steiner.h>
deba@2400
    34
deba@2400
    35
#include <cstdlib>
deba@2400
    36
#include <cmath>
deba@2400
    37
deba@2400
    38
using namespace lemon;
deba@2400
    39
using namespace lemon::dim2;
deba@2400
    40
deba@2400
    41
using namespace std;
deba@2400
    42
deba@2400
    43
int main(int argc, const char *argv[]) {
deba@2400
    44
  std::string lgf = argc > 1 ? argv[1] : "steiner.lgf";
deba@2400
    45
  std::string eps = argc > 2 ? argv[2] : "steiner.eps";
deba@2400
    46
deba@2400
    47
  SmartUGraph graph;
deba@2400
    48
  SmartUGraph::NodeMap<bool> terminal(graph);
deba@2400
    49
  SmartUGraph::NodeMap<int> label(graph);
deba@2400
    50
  SmartUGraph::NodeMap<Point<double> > coord(graph);
deba@2400
    51
  
deba@2400
    52
  UGraphReader<SmartUGraph>(lgf, graph).
deba@2400
    53
    readNodeMap("coordinates_x", xMap(coord)).
deba@2400
    54
    readNodeMap("coordinates_y", yMap(coord)).
deba@2400
    55
    readNodeMap("terminal", terminal).run();
deba@2400
    56
deba@2400
    57
  SmartUGraph::UEdgeMap<double> cost(graph);
deba@2400
    58
  for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) {
deba@2400
    59
    cost[it] = sqrt((coord[graph.target(it)] - 
deba@2400
    60
                     coord[graph.source(it)]).normSquare());
deba@2400
    61
  }
deba@2400
    62
  
deba@2400
    63
  SteinerTree<SmartUGraph> steiner(graph, cost);
deba@2400
    64
  steiner.init();
deba@2400
    65
deba@2400
    66
  for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) {
deba@2400
    67
    if (terminal[it]) {
deba@2400
    68
      steiner.addTerminal(it);
deba@2400
    69
    }
deba@2400
    70
  }
deba@2400
    71
  steiner.start();
deba@2400
    72
deba@2400
    73
deba@2400
    74
  Palette nodepalette(0);
deba@2400
    75
  nodepalette.add(Color(1.0, 1.0, 1.0));
deba@2400
    76
  nodepalette.add(Color(0.0, 1.0, 0.0));
deba@2400
    77
  nodepalette.add(Color(0.5, 0.5, 0.5));
deba@2400
    78
  SmartUGraph::NodeMap<int> nodecolor(graph);
deba@2400
    79
  for (SmartUGraph::NodeIt it(graph); it != INVALID; ++it) {
deba@2400
    80
    if (steiner.terminal(it)) {
deba@2400
    81
      nodecolor[it] = 1;
deba@2400
    82
    } else if (steiner.steiner(it)) {
deba@2400
    83
      nodecolor[it] = 2;
deba@2400
    84
    } else {
deba@2400
    85
      nodecolor[it] = 0;
deba@2400
    86
    }
deba@2400
    87
  }
deba@2400
    88
deba@2400
    89
deba@2400
    90
  Palette edgepalette(0);
deba@2400
    91
  edgepalette.add(Color(0.0, 0.0, 0.0));
deba@2400
    92
  edgepalette.add(Color(1.0, 0.0, 0.0));
deba@2400
    93
  SmartUGraph::UEdgeMap<int> edgecolor(graph);
deba@2400
    94
  for (SmartUGraph::UEdgeIt it(graph); it != INVALID; ++it) {
deba@2400
    95
    edgecolor[it] = steiner.tree(it) ? 1 : 0;
deba@2400
    96
  }
deba@2400
    97
deba@2400
    98
deba@2400
    99
  graphToEps(graph, eps).
deba@2400
   100
    coords(coord).undirected().
deba@2400
   101
    nodeScale(1.0).scaleToA4().
deba@2400
   102
    nodeColors(composeMap(nodepalette, nodecolor)).
deba@2400
   103
    edgeColors(composeMap(edgepalette, edgecolor)).
deba@2400
   104
    nodeTexts(label).nodeTextSize(8).run();
deba@2400
   105
deba@2400
   106
  std::cout << "The tree constructed: " << eps << std::endl;
deba@2400
   107
  std::cout << "The cost of the tree: " << steiner.treeValue() << std::endl;
deba@2400
   108
deba@2400
   109
  return 0;
deba@2400
   110
}