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