#include <lemon/list_graph.h>

#include <lemon/graph_utils.h>

#include <lemon/xy.h>

#include <lemon/graph_to_eps.h>

#include <cstdlib>

#include <cmath>

#include <ctime>

using namespace lemon;

// Special 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 xy<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 * M_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() {

  std::srand(std::time(0));

  typedef ListGraph Graph;

  typedef Graph::Node Node;

  typedef Graph::Edge Edge;

  // Generating a graph

  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(NODE));

  for (int i = 0; i < EDGE; ++i) {

    int si = (int)(std::rand() / (RAND_MAX + 1.0) * NODE);

    int ti = (int)(std::rand() / (RAND_MAX + 1.0) * NODE);

    graph.addEdge(nodeInv[si], nodeInv[ti]);

  }

  // Make postscript from the graph.

  CircleMap<Graph> coords(graph, xy<double>(0.0, 0.0), 10.0);

  graphToEps(graph,"descriptor_map_demo.eps").scaleToA4().

    title("Generated graph").

    copyright("(C) 2005 LEMON Project").

    coords(coords).

    nodeScale(1.0).

    enableParallel().parEdgeDist(1).

    drawArrows().arrowWidth(1).arrowLength(1).

    run();

  return 0;

}