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