|
1 #include <lemon/list_graph.h> |
|
2 #include <lemon/graph_utils.h> |
|
3 #include <lemon/xy.h> |
|
4 |
|
5 #include <lemon/graph_to_eps.h> |
|
6 |
|
7 #include <cstdlib> |
|
8 #include <cmath> |
|
9 #include <ctime> |
|
10 |
|
11 using namespace lemon; |
|
12 |
|
13 // Special map type |
|
14 // It gives back a position for each node. The position of the nodes |
|
15 // are on the circle with the given center and radius. |
|
16 // |
|
17 // Because we use the descriptor map it will hold the proprty described above |
|
18 // even if a node added or deleted. |
|
19 template <typename Graph> |
|
20 class CircleMap { |
|
21 public: |
|
22 |
|
23 typedef xy<double> Value; |
|
24 typedef typename Graph::Node Key; |
|
25 |
|
26 CircleMap(const Graph& _graph, |
|
27 const Value& _center = Value(0.0, 0.0), |
|
28 double _radius = 1.0) |
|
29 : descriptor(_graph), center(_center), radius(_radius) {} |
|
30 |
|
31 Value operator[](const Key& key) const { |
|
32 double angle = descriptor[key] * 2 * M_PI |
|
33 / (double)descriptor.inverse().size(); |
|
34 double x = std::cos(angle) * radius + center.x; |
|
35 double y = std::sin(angle) * radius + center.y; |
|
36 return Value(x, y); |
|
37 } |
|
38 |
|
39 private: |
|
40 |
|
41 DescriptorMap<Graph, typename Graph::Node> descriptor; |
|
42 Value center; |
|
43 double radius; |
|
44 }; |
|
45 |
|
46 int main() { |
|
47 std::srand(std::time(0)); |
|
48 typedef ListGraph Graph; |
|
49 typedef Graph::Node Node; |
|
50 typedef Graph::Edge Edge; |
|
51 |
|
52 // Generating a graph |
|
53 |
|
54 Graph graph; |
|
55 |
|
56 const int NODE = 16; |
|
57 for (int i = 0; i < NODE; ++i) { |
|
58 graph.addNode(); |
|
59 } |
|
60 |
|
61 // Creating descriptor map and inverse |
|
62 DescriptorMap<Graph, Node> nodeDesc(graph); |
|
63 DescriptorMap<Graph, Node>::InverseMap nodeInv(nodeDesc); |
|
64 |
|
65 // Adding edges |
|
66 // The descriptor map always maps an integer value for each node. |
|
67 // The range of the values is always [0..n - 1] where n is the |
|
68 // number of the nodes of the graph. The inverse map gives back the |
|
69 // the node by its descriptor value. |
|
70 // |
|
71 // The inversemap cannot works without its DescriptorMap because |
|
72 // it holds reference to it. |
|
73 const int EDGE = (int)(NODE * std::log(NODE)); |
|
74 for (int i = 0; i < EDGE; ++i) { |
|
75 int si = (int)(std::rand() / (RAND_MAX + 1.0) * NODE); |
|
76 int ti = (int)(std::rand() / (RAND_MAX + 1.0) * NODE); |
|
77 |
|
78 graph.addEdge(nodeInv[si], nodeInv[ti]); |
|
79 } |
|
80 |
|
81 // Make postscript from the graph. |
|
82 |
|
83 CircleMap<Graph> coords(graph, xy<double>(0.0, 0.0), 10.0); |
|
84 |
|
85 graphToEps(graph,"descriptor_map_demo.eps").scaleToA4(). |
|
86 title("Generated graph"). |
|
87 copyright("(C) 2005 LEMON Project"). |
|
88 coords(coords). |
|
89 nodeScale(1.0). |
|
90 enableParallel().parEdgeDist(1). |
|
91 drawArrows().arrowWidth(1).arrowLength(1). |
|
92 run(); |
|
93 |
|
94 return 0; |
|
95 } |