7c2410d66f4dc696214df283124956a4c0f8bea7
[public/netxms.git] / src / libnxmap / rt.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
8 **
9 ** This program is free software; you can redistribute it and/or modify
10 ** it under the terms of the GNU General Public License as published by
11 ** the Free Software Foundation; either version 2 of the License, or
12 ** (at your option) any later version.
13 **
14 ** This program is distributed in the hope that it will be useful,
15 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
16 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 ** GNU General Public License for more details.
18 **
19 ** You should have received a copy of the GNU General Public License
20 ** along with this program; if not, write to the Free Software
21 ** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 **
23 ** File: rt.cpp
24 **
25 **/
26
27 #include "libnxmap.h"
28
29
30 //
31 // Constructor
32 //
33
34 nxleReingoldTilford::nxleReingoldTilford(nxmap_Graph *pGraph)
35 :nxleGeneric(pGraph)
36 {
37 m_xPreliminary = (double *)malloc(pGraph->GetVertexCount() * sizeof(double));
38 m_xModifier = (double *)malloc(pGraph->GetVertexCount() * sizeof(double));
39 m_xParentModifier = (double *)malloc(pGraph->GetVertexCount() * sizeof(double));
40 m_passCount = (int *)malloc(pGraph->GetVertexCount() * sizeof(int));
41 m_leftBrother = (nxmap_Vertex **)malloc(pGraph->GetVertexCount() * sizeof(nxmap_Vertex *));
42 m_layer = (DWORD *)malloc(pGraph->GetVertexCount() * sizeof(DWORD));
43 m_contour = (nxmap_Vertex **)malloc(pGraph->GetVertexCount() * sizeof(nxmap_Vertex *));
44 m_spacing = MAP_OBJECT_SIZE_Y + MAP_TEXT_BOX_HEIGHT + MAP_OBJECT_INTERVAL_Y;
45 }
46
47
48 //
49 // Destructor
50 //
51
52 nxleReingoldTilford::~nxleReingoldTilford()
53 {
54 safe_free(m_xPreliminary);
55 safe_free(m_xModifier);
56 safe_free(m_xParentModifier);
57 safe_free(m_passCount);
58 safe_free(m_leftBrother);
59 safe_free(m_layer);
60 safe_free(m_contour);
61 }
62
63
64 //
65 // Initialise a node for RT-layout. This involves finding,
66 // for each node, the left-hand brother of the node, i.e. the
67 // node at the same depth in the tree that would be to the
68 // immediate left of this node. This is achieved by doing a
69 // traversal of the tree.
70 //
71 // The parameter "layer" represents the nodes at the level
72 // of the tree currently being considered.
73 //
74
75 void nxleReingoldTilford::Initialize(nxmap_Vertex *root, DWORD layer)
76 {
77 DWORD i, index;
78
79 index = m_graph->GetVertexIndex(root);
80
81 if ((m_layer[index] < layer) || (m_layer[index] == 0))
82 {
83 m_leftBrother[index] = m_contour[layer];
84 m_contour[layer] = root;
85 m_layer[index] = layer;
86
87 for(i = 0; i < root->GetNumChilds(); i++)
88 {
89 Initialize(root->GetChild(i), layer + 1);
90 }
91 }
92 }
93
94
95 //
96 // Return actual x coordinate of a node, taking into account
97 // the position modifiers of its ancestors up to the root.
98 //
99
100 double nxleReingoldTilford::TrueX(nxmap_Vertex *root)
101 {
102 double x;
103 DWORD index;
104 nxmap_Vertex *node;
105
106 index = m_graph->GetVertexIndex(root);
107 node = root;
108 x = m_xPreliminary[index];
109
110 while(node->GetNumParents() > 0)
111 {
112 x += m_xModifier[index];
113 node = node->GetParent(node->GetNumParents() / 2);
114 index = m_graph->GetVertexIndex(node);
115 }
116 return x;
117 }
118
119
120 //
121 // First pass
122 //
123
124 void nxleReingoldTilford::FirstPass(nxmap_Vertex *root)
125 {
126 double modifier, xRoot, xBrother;
127 DWORD i, index, leftIndex, rightIndex;
128 nxmap_Vertex *brother;
129
130 index = m_graph->GetVertexIndex(root);
131
132 // Case 1. Node is a leaf
133 if (root->GetNumChilds() == 0)
134 {
135 brother = m_leftBrother[index];
136 if (brother == NULL)
137 {
138 xRoot = 0.0; // no left brother
139 }
140 else
141 {
142 // Find coordinate relative to brother. Include the
143 // size of the node and an internode interval
144 xRoot = TrueX(brother) + MAP_OBJECT_SIZE_X + MAP_OBJECT_INTERVAL_X;
145 }
146 modifier = 0.0;
147 }
148 else
149 {
150 // Apply FirstPass to each child
151 for(i = 0; i < root->GetNumChilds(); i++)
152 {
153 FirstPass(root->GetChild(i));
154 }
155
156 // Position the node.
157 leftIndex = m_graph->GetVertexIndex(root->GetChild(0));
158 rightIndex = m_graph->GetVertexIndex(root->GetChild(root->GetNumChilds() - 1));
159 xRoot = (m_xPreliminary[leftIndex] + m_xModifier[leftIndex] + m_xPreliminary[rightIndex] + m_xModifier[rightIndex]) / 2.0;
160 modifier = 0.0;
161 brother = m_leftBrother[index];
162
163 if (brother != NULL)
164 {
165 xBrother = TrueX(brother);
166 modifier = MAP_OBJECT_SIZE_X + MAP_OBJECT_INTERVAL_X - (xRoot - xBrother);
167 if (modifier < 0)
168 modifier = 0;
169 }
170 }
171
172 m_xPreliminary[index] = xRoot;
173 m_xModifier[index] = modifier;
174 }
175
176
177 //
178 // Second pass
179 //
180
181 void nxleReingoldTilford::SecondPass(nxmap_Vertex *root, double modifier)
182 {
183 double childModif;
184 DWORD i, index;
185
186 index = m_graph->GetVertexIndex(root);
187 m_passCount[index]++;
188 m_xParentModifier[index] += modifier;
189 root->SetPosition((int)(m_xPreliminary[index] + m_xModifier[index] + m_xParentModifier[index] / m_passCount[index]),
190 (int)(m_layer[index] * m_spacing));
191
192 childModif = modifier + m_xModifier[index];
193 for(i = 0; i < root->GetNumChilds(); i++)
194 {
195 SecondPass(root->GetChild(i), childModif);
196 }
197 }
198
199
200 //
201 // Execute
202 //
203
204 void nxleReingoldTilford::Execute(void)
205 {
206 if (m_graph->GetVertexCount() == 0)
207 return;
208
209 memset(m_xPreliminary, 0, sizeof(double) * m_graph->GetVertexCount());
210 memset(m_xModifier, 0, sizeof(double) * m_graph->GetVertexCount());
211 memset(m_xParentModifier, 0, sizeof(double) * m_graph->GetVertexCount());
212 memset(m_passCount, 0, sizeof(int) * m_graph->GetVertexCount());
213 memset(m_contour, 0, sizeof(nxmap_Vertex *) * m_graph->GetVertexCount());
214 memset(m_leftBrother, 0, sizeof(nxmap_Vertex *) * m_graph->GetVertexCount());
215 memset(m_layer, 0, sizeof(DWORD) * m_graph->GetVertexCount());
216
217 Initialize(m_graph->GetRootVertex(), 0);
218 FirstPass(m_graph->GetRootVertex());
219 SecondPass(m_graph->GetRootVertex(), 0);
220 }