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