demo/descriptor_map_demo.cc
author hegyi
Wed, 27 Jul 2005 10:47:38 +0000
changeset 1594 0bd9e53c8b28
parent 1554 572bc7d0d3e2
child 1636 260ac104190f
permissions -rw-r--r--
Documentation was added to GUI.
deba@1554
     1
/* -*- C++ -*-
deba@1554
     2
 * demo/descriptor_map_demo.cc - Part of LEMON, a generic C++ optimization library
deba@1554
     3
 *
deba@1554
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1554
     5
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1554
     6
 *
deba@1554
     7
 * Permission to use, modify and distribute this software is granted
deba@1554
     8
 * provided that this copyright notice appears in all copies. For
deba@1554
     9
 * precise terms see the accompanying LICENSE file.
deba@1554
    10
 *
deba@1554
    11
 * This software is provided "AS IS" with no warranty of any kind,
deba@1554
    12
 * express or implied, and with no claim as to its suitability for any
deba@1554
    13
 * purpose.
deba@1554
    14
 *
deba@1554
    15
 */
deba@1554
    16
deba@1553
    17
#include <lemon/list_graph.h>
deba@1553
    18
#include <lemon/graph_utils.h>
deba@1554
    19
#include <lemon/graph_writer.h>
deba@1553
    20
#include <lemon/xy.h>
deba@1554
    21
#include <lemon/graph_to_eps.h>
deba@1553
    22
deba@1554
    23
#include <iostream>
deba@1553
    24
deba@1553
    25
#include <cstdlib>
deba@1553
    26
#include <cmath>
deba@1553
    27
#include <ctime>
deba@1553
    28
deba@1553
    29
using namespace lemon;
deba@1553
    30
deba@1553
    31
// Special map type
deba@1553
    32
// It gives back a position for each node. The position of the nodes 
deba@1553
    33
// are on the circle with the given center and radius.
deba@1553
    34
//
deba@1553
    35
// Because we use the descriptor map it will hold the proprty described above
deba@1553
    36
// even if a node added or deleted. 
deba@1553
    37
template <typename Graph>
deba@1553
    38
class CircleMap {
deba@1553
    39
public:
deba@1553
    40
deba@1553
    41
  typedef xy<double> Value;
deba@1553
    42
  typedef typename Graph::Node Key;
deba@1553
    43
deba@1553
    44
  CircleMap(const Graph& _graph, 
deba@1553
    45
	    const Value& _center = Value(0.0, 0.0), 
deba@1553
    46
	    double _radius = 1.0) 
deba@1553
    47
    : descriptor(_graph), center(_center), radius(_radius) {}
deba@1553
    48
deba@1553
    49
  Value operator[](const Key& key) const {
deba@1553
    50
    double angle = descriptor[key] * 2 * M_PI 
deba@1553
    51
      / (double)descriptor.inverse().size();
deba@1553
    52
    double x = std::cos(angle) * radius + center.x;
deba@1553
    53
    double y = std::sin(angle) * radius + center.y;
deba@1553
    54
    return Value(x, y);
deba@1553
    55
  }
deba@1553
    56
deba@1553
    57
private:
deba@1553
    58
  
deba@1553
    59
  DescriptorMap<Graph, typename Graph::Node> descriptor;
deba@1553
    60
  Value center;
deba@1553
    61
  double radius;
deba@1553
    62
};
deba@1553
    63
deba@1553
    64
int main() {
deba@1553
    65
  std::srand(std::time(0));
deba@1553
    66
  typedef ListGraph Graph;
deba@1553
    67
  typedef Graph::Node Node;
deba@1553
    68
  typedef Graph::Edge Edge;
deba@1553
    69
  
deba@1553
    70
  // Generating a graph
deba@1554
    71
deba@1554
    72
  std::cout << "Generating graph: " << std::endl;
deba@1554
    73
deba@1553
    74
  Graph graph;
deba@1553
    75
  
deba@1553
    76
  const int NODE = 16;
deba@1553
    77
  for (int i = 0; i < NODE; ++i) {
deba@1553
    78
    graph.addNode();
deba@1553
    79
  } 
deba@1553
    80
deba@1553
    81
  // Creating descriptor map and inverse
deba@1553
    82
  DescriptorMap<Graph, Node> nodeDesc(graph);
deba@1553
    83
  DescriptorMap<Graph, Node>::InverseMap nodeInv(nodeDesc);
deba@1553
    84
deba@1553
    85
  // Adding edges
deba@1553
    86
  // The descriptor map always maps an integer value for each node.
deba@1553
    87
  // The range of the values is always [0..n - 1] where n is the
deba@1553
    88
  // number of the nodes of the graph. The inverse map gives back the
deba@1553
    89
  // the node by its descriptor value. 
deba@1553
    90
  //
deba@1553
    91
  // The inversemap cannot works without its DescriptorMap because
deba@1553
    92
  // it holds reference to it. 
alpar@1556
    93
  const int EDGE = (int)(NODE * std::log(double(NODE)));
deba@1553
    94
  for (int i = 0; i < EDGE; ++i) {
deba@1553
    95
    int si = (int)(std::rand() / (RAND_MAX + 1.0) * NODE);
deba@1553
    96
    int ti = (int)(std::rand() / (RAND_MAX + 1.0) * NODE);
deba@1553
    97
      
deba@1553
    98
    graph.addEdge(nodeInv[si], nodeInv[ti]);
deba@1553
    99
  }
deba@1553
   100
deba@1554
   101
  GraphWriter<Graph>(std::cout, graph).run();
deba@1554
   102
deba@1554
   103
  std::cout << std::endl;
deba@1554
   104
  std::cout << "Postscript file: descriptor_map_demo.eps" << std::endl;
deba@1554
   105
deba@1553
   106
  // Make postscript from the graph.
deba@1553
   107
    
deba@1553
   108
  CircleMap<Graph> coords(graph, xy<double>(0.0, 0.0), 10.0);
deba@1553
   109
    
deba@1553
   110
  graphToEps(graph,"descriptor_map_demo.eps").scaleToA4().
deba@1553
   111
    title("Generated graph").
deba@1553
   112
    copyright("(C) 2005 LEMON Project").
deba@1553
   113
    coords(coords).
deba@1553
   114
    nodeScale(1.0).
deba@1553
   115
    enableParallel().parEdgeDist(1).
deba@1553
   116
    drawArrows().arrowWidth(1).arrowLength(1).
deba@1553
   117
    run();
deba@1553
   118
 
deba@1553
   119
  return 0;
deba@1553
   120
}