license changed to LGPL for libnxcl, libnxsnmp, libnxlp, libnxsl, and libnxmap
[public/netxms.git] / src / libnxmap / radial.cpp
1 /*
2 ** NetXMS - Network Management System
3 ** Network Maps Library
4 ** Copyright (C) 2006 Victor Kirhenshtein
5 **
6 ** This code is derived from Graph visualization library for VTK
7 ** (c) 2003 D.J. Duke. Original license follows.
8 **
9 ** Graph visualization library for VTK
10 ** (c) 2003 D.J. Duke
11 **
12 ** You are warned that this is an alpha release of the library. The
13 ** software has not been extensively tested or used, beyond the
14 ** personal research work of the developer.
15 **
16 ** This copyright notice is based on the copyright distributed with the
17 ** VTK toolkit (see www.vtk.org), which this library extends. The terms
18 ** for using the material in this directory are similar to those of the
19 ** full tool:
20 **
21 ** Redistribution and use in source and binary forms, with or without
22 ** modification, are permitted provided that the following conditions are met:
23 **
24 ** * Redistributions of source code must retain the above copyright notice,
25 ** this list of conditions and the following disclaimer.
26 **
27 ** * Redistributions in binary form must reproduce the above copyright notice,
28 ** this list of conditions and the following disclaimer in the documentation
29 ** and/or other materials provided with the distribution.
30 **
31 ** * With respect to this library, neither the name of the developer
32 ** (David Duke) or the name(s) of any contributor(s) to this library
33 ** may be used to endorse or promote products derived from this
34 ** software without specific prior written permission.
35 **
36 ** * Modified source versions must be plainly marked as such, and must not be
37 ** misrepresented as being the original software.
38 **
39 ** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
40 ** AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41 ** IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
42 ** ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR
43 ** ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
44 ** DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
45 ** SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
46 ** CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
47 ** OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
48 ** OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
49 **
50 ** --- end of original license ---
51 **
52 ** File: radial.cpp
53 **
54 **/
55
56 #include "libnxmap.h"
57 #include <math.h>
58
59 #define PI 3.14159
60
61
62 //
63 // Constructor
64 //
65
66 nxleRadial::nxleRadial(nxmap_Graph *pGraph)
67 :nxleGeneric(pGraph)
68 {
69 m_bConvexity = FALSE;
70 m_delta = MAP_OBJECT_SIZE_X + MAP_OBJECT_INTERVAL_X;
71 m_increase = 50.0 * m_delta / 100.0;
72 m_width = (double *)malloc(pGraph->GetVertexCount() * sizeof(double));
73 m_fullWidth = (double *)malloc(pGraph->GetVertexCount() * sizeof(double));
74 m_angle = (double *)malloc(pGraph->GetVertexCount() * sizeof(double));
75 m_distance = (double *)malloc(pGraph->GetVertexCount() * sizeof(double));
76 }
77
78
79 //
80 // Destructor
81 //
82
83 nxleRadial::~nxleRadial()
84 {
85 safe_free(m_width);
86 safe_free(m_fullWidth);
87 safe_free(m_angle);
88 safe_free(m_distance);
89 }
90
91
92 //
93 // Position the tree rooted at "root".
94 // The allocated posiition is not final; each sub-tree is positioned
95 // on the assumption that its parent is located at the origin, and all
96 // nodes are positioned in the plane z=0. This will be corrected in a
97 // second pass over the tree.
98 //
99 // The return value is the radius of the circle containing the layout
100 // of this (sub)-tree.
101 //
102
103 double nxleRadial::SetWidth(nxmap_Vertex *root)
104 {
105 double width;
106 DWORD i;
107
108 if (root->GetNumChilds() == 0)
109 {
110 width = MAP_OBJECT_SIZE_X;
111 }
112 else
113 {
114 width = 0.0;
115 for(i = 0; i < root->GetNumChilds(); i++)
116 {
117 width += SetWidth(root->GetChild(i)) + MAP_OBJECT_INTERVAL_X;
118 }
119 }
120 m_width[m_graph->GetVertexIndex(root)] = width;
121 m_fullWidth[m_graph->GetVertexIndex(root)] = width;
122 return width;
123 }
124
125
126 //
127 // Calculate the final layout for a node, given its level in
128 // the tree, and the (final) position of its parent.
129 //
130
131 void nxleRadial::SetPlacement(nxmap_Vertex *root, double ro,
132 double alpha1, double alpha2, int layer)
133 {
134 double s, tau, alpha, rootFullWidth, childWidth;
135 double myDelta = m_delta + m_increase;
136 double fi = (alpha1 + alpha2)/2.0;
137 DWORD i, index;
138 nxmap_Vertex *child;
139
140 root->SetPosition((int)(ro * sin(fi)), (int)(ro * cos(fi)));
141
142 index = m_graph->GetVertexIndex(root);
143 m_angle[index] = fi;
144 m_distance[index] = ro;
145
146 if (root->GetNumChilds() > 0)
147 {
148 tau = m_bConvexity ? 2.0 * acos(ro / (ro + myDelta)) : 0.0;
149 rootFullWidth = m_fullWidth[index];
150 if (m_bConvexity && (ro != 0.0) && (tau < (alpha2 - alpha1)))
151 {
152 s = tau / rootFullWidth;
153 alpha = (alpha1 + alpha2 - tau) / 2.0;
154 }
155 else
156 {
157 s = (alpha2 - alpha1) / rootFullWidth;
158 alpha = alpha1;
159 }
160
161 for(i = 0; i < root->GetNumChilds(); i++)
162 {
163 child = root->GetChild(i);
164 childWidth = m_width[m_graph->GetVertexIndex(child)];
165 SetPlacement(child, ro + myDelta, alpha,
166 alpha + s * childWidth, layer + 1);
167 alpha += s * childWidth;
168 }
169 }
170 }
171
172
173 //
174 // Execute
175 //
176
177 void nxleRadial::Execute(void)
178 {
179 if (m_graph->GetVertexCount() == 0)
180 return;
181
182 // Layout is performed in two passes. First, find a provisional location
183 // for each node, via a bottom-up traversal. Then calculate a final
184 // position for each node, by performing a top-down traversal, placing
185 // the root at the origin, and then positioning each child using the
186 // provisional location of the child and final location of the parent.
187
188 SetWidth(m_graph->GetRootVertex());
189 SetPlacement(m_graph->GetRootVertex(), 0.0, 0.0, 2.0 * PI, 0);
190 }