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