deba@1554: /* -*- C++ -*- ladanyi@1636: * demo/descriptor_map_demo.cc - Part of LEMON, a generic C++ optimization ladanyi@1636: * library deba@1554: * deba@1554: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1554: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1554: * deba@1554: * Permission to use, modify and distribute this software is granted deba@1554: * provided that this copyright notice appears in all copies. For deba@1554: * precise terms see the accompanying LICENSE file. deba@1554: * deba@1554: * This software is provided "AS IS" with no warranty of any kind, deba@1554: * express or implied, and with no claim as to its suitability for any deba@1554: * purpose. deba@1554: * deba@1554: */ deba@1554: deba@1553: #include deba@1553: #include deba@1554: #include deba@1553: #include deba@1554: #include deba@1553: deba@1554: #include deba@1553: deba@1553: #include deba@1553: #include deba@1553: #include deba@1553: deba@1553: using namespace lemon; deba@1553: deba@1553: // Special map type deba@1553: // It gives back a position for each node. The position of the nodes deba@1553: // are on the circle with the given center and radius. deba@1553: // deba@1553: // Because we use the descriptor map it will hold the proprty described above deba@1553: // even if a node added or deleted. deba@1553: template deba@1553: class CircleMap { deba@1553: public: deba@1553: deba@1553: typedef xy Value; deba@1553: typedef typename Graph::Node Key; deba@1553: deba@1553: CircleMap(const Graph& _graph, deba@1553: const Value& _center = Value(0.0, 0.0), deba@1553: double _radius = 1.0) deba@1553: : descriptor(_graph), center(_center), radius(_radius) {} deba@1553: deba@1553: Value operator[](const Key& key) const { deba@1553: double angle = descriptor[key] * 2 * M_PI deba@1553: / (double)descriptor.inverse().size(); deba@1553: double x = std::cos(angle) * radius + center.x; deba@1553: double y = std::sin(angle) * radius + center.y; deba@1553: return Value(x, y); deba@1553: } deba@1553: deba@1553: private: deba@1553: deba@1553: DescriptorMap descriptor; deba@1553: Value center; deba@1553: double radius; deba@1553: }; deba@1553: deba@1553: int main() { deba@1553: std::srand(std::time(0)); deba@1553: typedef ListGraph Graph; deba@1553: typedef Graph::Node Node; deba@1553: typedef Graph::Edge Edge; deba@1553: deba@1553: // Generating a graph deba@1554: deba@1554: std::cout << "Generating graph: " << std::endl; deba@1554: deba@1553: Graph graph; deba@1553: deba@1553: const int NODE = 16; deba@1553: for (int i = 0; i < NODE; ++i) { deba@1553: graph.addNode(); deba@1553: } deba@1553: deba@1553: // Creating descriptor map and inverse deba@1553: DescriptorMap nodeDesc(graph); deba@1553: DescriptorMap::InverseMap nodeInv(nodeDesc); deba@1553: deba@1553: // Adding edges deba@1553: // The descriptor map always maps an integer value for each node. deba@1553: // The range of the values is always [0..n - 1] where n is the deba@1553: // number of the nodes of the graph. The inverse map gives back the deba@1553: // the node by its descriptor value. deba@1553: // deba@1553: // The inversemap cannot works without its DescriptorMap because deba@1553: // it holds reference to it. alpar@1556: const int EDGE = (int)(NODE * std::log(double(NODE))); deba@1553: for (int i = 0; i < EDGE; ++i) { deba@1553: int si = (int)(std::rand() / (RAND_MAX + 1.0) * NODE); deba@1553: int ti = (int)(std::rand() / (RAND_MAX + 1.0) * NODE); deba@1553: deba@1553: graph.addEdge(nodeInv[si], nodeInv[ti]); deba@1553: } deba@1553: deba@1554: GraphWriter(std::cout, graph).run(); deba@1554: deba@1554: std::cout << std::endl; deba@1554: std::cout << "Postscript file: descriptor_map_demo.eps" << std::endl; deba@1554: deba@1553: // Make postscript from the graph. deba@1553: deba@1553: CircleMap coords(graph, xy(0.0, 0.0), 10.0); deba@1553: deba@1553: graphToEps(graph,"descriptor_map_demo.eps").scaleToA4(). deba@1553: title("Generated graph"). deba@1553: copyright("(C) 2005 LEMON Project"). deba@1553: coords(coords). deba@1553: nodeScale(1.0). deba@1553: enableParallel().parEdgeDist(1). deba@1553: drawArrows().arrowWidth(1).arrowLength(1). deba@1553: run(); deba@1553: deba@1553: return 0; deba@1553: }