descriptor_map_demo.cc File Reference

---

Detailed Description

This demo shows how can be used the DescriptorMap class which helps to use unique label for each node or edge. And it gives an example how easy is creating own map types.

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */


#include <lemon/list_graph.h>
#include <lemon/graph_utils.h>
#include <lemon/graph_writer.h>
#include <lemon/dim2.h>
#include <lemon/graph_to_eps.h>

#include <lemon/random.h>

#include <iostream>

#include <lemon/math.h>


using namespace lemon;

// Special dim2::Point<double> map type 
//
// It gives back a position for each node. The position of the nodes
// are on the circle with the given center and radius.
//
// Because we use the descriptor map it will hold the proprty
// described above even if a node added or deleted.
template <typename Graph>
class CircleMap {
public:

  typedef dim2::Point<double> Value;
  typedef typename Graph::Node Key;

  CircleMap(const Graph& _graph, 
            const Value& _center = Value(0.0, 0.0), 
            double _radius = 1.0) 
    : descriptor(_graph), center(_center), radius(_radius) {}

  Value operator[](const Key& key) const {
    double angle = descriptor[key] * 2 * PI 
      / double(descriptor.inverse().size());
    double x = std::cos(angle) * radius + center.x;
    double y = std::sin(angle) * radius + center.y;
    return Value(x, y);
  }

private:
  
  DescriptorMap<Graph, typename Graph::Node> descriptor;
  Value center;
  double radius;
};

int main() {
  typedef ListGraph Graph;
  typedef Graph::Node Node;
  typedef Graph::Edge Edge;
  
  // Generating a graph

  std::cout << "Generating graph: " << std::endl;

  Graph graph;
  
  const int NODE = 16;
  for (int i = 0; i < NODE; ++i) {
    graph.addNode();
  } 

  // Creating descriptor map and inverse
  DescriptorMap<Graph, Node> nodeDesc(graph);
  DescriptorMap<Graph, Node>::InverseMap nodeInv(nodeDesc);

  // Adding edges
  // The descriptor map always maps an integer value for each node.
  // The range of the values is always [0..n - 1] where n is the
  // number of the nodes of the graph. The inverse map gives back the
  // the node by its descriptor value. 
  //
  // The inversemap cannot works without its DescriptorMap because
  // it holds reference to it. 
  const int EDGE = int(NODE * std::log(double(NODE)));
  for (int i = 0; i < EDGE; ++i) {
    int si = rnd[NODE];
    int ti = rnd[NODE];
      
    graph.addEdge(nodeInv[si], nodeInv[ti]);
  }

  GraphWriter<Graph>(std::cout, graph).run();

  std::cout << std::endl;
  std::cout << "Postscript file: descriptor_map_demo.eps" << std::endl;

  // Make postscript from the graph.
    
  CircleMap<Graph> coords(graph, dim2::Point<double>(0.0, 0.0), 10.0);
    
  graphToEps(graph,"descriptor_map_demo.eps").scaleToA4().
    title("Generated graph").
    copyright("(C) 2003-2007 LEMON Project").
    coords(coords).
    nodeScale(1.0).
    enableParallel().parEdgeDist(1).
    drawArrows().arrowWidth(1).arrowLength(1).
    run();
 
  return 0;
}

#include <lemon/list_graph.h>
#include <lemon/graph_utils.h>
#include <lemon/graph_writer.h>
#include <lemon/dim2.h>
#include <lemon/graph_to_eps.h>
#include <lemon/random.h>
#include <iostream>
#include <lemon/math.h>