license changed to LGPL for libnxcl, libnxsnmp, libnxlp, libnxsl, and libnxmap
[public/netxms.git] / src / libnxmap / graph.cpp
1 /*
2 ** NetXMS - Network Management System
3 ** Network Maps Library
4 ** Copyright (C) 2003-2010 Victor Kirhenshtein
5 **
6 ** This program is free software; you can redistribute it and/or modify
7 ** it under the terms of the GNU Lesser General Public License as published by
8 ** the Free Software Foundation; either version 3 of the License, or
9 ** (at your option) any later version.
10 **
11 ** This program is distributed in the hope that it will be useful,
12 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 ** GNU General Public License for more details.
15 **
16 ** You should have received a copy of the GNU Lesser General Public License
17 ** along with this program; if not, write to the Free Software
18 ** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 **
20 ** File: graph.cpp
21 **
22 **/
23
24 #include "libnxmap.h"
25
26
27 //
28 // Default constructor
29 //
30
31 nxmap_Graph::nxmap_Graph()
32 {
33 m_dwVertexCount = 0;
34 m_ppVertexList = NULL;
35 m_dwVertexCount = 0;
36 m_ppVertexList = NULL;
37 m_pRoot = NULL;
38 }
39
40
41 //
42 // Create graph from list of objects and links
43 //
44
45 nxmap_Graph::nxmap_Graph(DWORD dwNumObjects, DWORD *pdwObjectList,
46 DWORD dwNumLinks, OBJLINK *pLinkList)
47 {
48 DWORD i;
49 nxmap_Vertex *pVtx1, *pVtx2;
50
51 m_dwVertexCount = dwNumObjects;
52 m_ppVertexList = (nxmap_Vertex **)malloc(sizeof(nxmap_Vertex *) * dwNumObjects);
53 for(i = 0; i < dwNumObjects; i++)
54 {
55 m_ppVertexList[i] = new nxmap_Vertex(pdwObjectList[i]);
56 }
57
58 // Create links between vertexes
59 for(i = 0; i < dwNumLinks; i++)
60 {
61 pVtx1 = FindVertex(pLinkList[i].dwId1);
62 pVtx2 = FindVertex(pLinkList[i].dwId2);
63 if ((pVtx1 != NULL) && (pVtx2 != NULL))
64 pVtx1->LinkChild(pVtx2);
65 }
66
67 m_pRoot = NULL; // No selected root by default
68 }
69
70
71 //
72 // Destructor
73 //
74
75 nxmap_Graph::~nxmap_Graph()
76 {
77 DWORD i;
78
79 for(i = 0; i < m_dwVertexCount; i++)
80 delete m_ppVertexList[i];
81 safe_free(m_ppVertexList);
82 }
83
84
85 //
86 // Set all vertexes as unprocessed
87 //
88
89 void nxmap_Graph::SetAsUnprocessed(void)
90 {
91 DWORD i;
92
93 for(i = 0; i < m_dwVertexCount; i++)
94 m_ppVertexList[i]->SetAsUnprocessed();
95 }
96
97
98 //
99 // Find vertex by ID
100 //
101
102 nxmap_Vertex *nxmap_Graph::FindVertex(DWORD dwId)
103 {
104 DWORD i;
105
106 for(i = 0; i < m_dwVertexCount; i++)
107 if (m_ppVertexList[i]->GetId() == dwId)
108 return m_ppVertexList[i];
109 return NULL;
110 }
111
112
113 //
114 // Get internal index of given vertex
115 //
116
117 DWORD nxmap_Graph::GetVertexIndex(nxmap_Vertex *pVertex)
118 {
119 DWORD i;
120
121 for(i = 0; i < m_dwVertexCount; i++)
122 if (m_ppVertexList[i]->GetId() == pVertex->GetId())
123 return i;
124 return INVALID_INDEX;
125 }
126
127
128 //
129 // Normalize vertex positions
130 //
131
132 void nxmap_Graph::NormalizeVertexPositions(void)
133 {
134 DWORD i;
135 int x, y, dx, dy;
136
137 // Calculate required offset
138 for(i = 0, dx = 0, dy = 0; i < m_dwVertexCount; i++)
139 {
140 x = m_ppVertexList[i]->GetPosX();
141 if (x < MAP_LEFT_MARGIN)
142 if (dx < MAP_LEFT_MARGIN - x)
143 dx = MAP_LEFT_MARGIN - x;
144 y = m_ppVertexList[i]->GetPosY();
145 if (y < MAP_TOP_MARGIN)
146 if (dy < MAP_TOP_MARGIN - y)
147 dy = MAP_TOP_MARGIN - y;
148 }
149
150 // Change coordinates
151 if ((dx != 0) || (dy != 0))
152 {
153 for(i = 0; i < m_dwVertexCount; i++)
154 m_ppVertexList[i]->SetPosition(m_ppVertexList[i]->GetPosX() + dx,
155 m_ppVertexList[i]->GetPosY() + dy);
156 }
157 }
158
159
160 //
161 // Set root vertex
162 //
163
164 void nxmap_Graph::SetRootVertex(DWORD dwId)
165 {
166 DWORD i;
167
168 for(i = 0; i < m_dwVertexCount; i++)
169 if (m_ppVertexList[i]->GetId() == dwId)
170 {
171 m_pRoot = m_ppVertexList[i];
172 return;
173 }
174 m_pRoot = NULL;
175 }
176
177
178 //
179 // Normalize links for given vertex
180 //
181
182 void nxmap_Graph::NormalizeVertexLinks(nxmap_Vertex *pRoot)
183 {
184 DWORD i;
185
186 for(i = 0; i < m_dwVertexCount; i++)
187 {
188 if (!m_ppVertexList[i]->IsProcessed() && m_ppVertexList[i]->IsParentOf(pRoot))
189 {
190 m_ppVertexList[i]->UnlinkChild(pRoot);
191 pRoot->LinkChild(m_ppVertexList[i]);
192 }
193 }
194
195 for(i = 0; i < pRoot->GetNumChilds(); i++)
196 {
197 if (!pRoot->GetChild(i)->IsProcessed())
198 {
199 pRoot->GetChild(i)->SetAsProcessed();
200 NormalizeVertexLinks(pRoot->GetChild(i));
201 }
202 }
203 }
204
205
206 //
207 // Normalize links - make all links to go from root when possible
208 //
209
210 void nxmap_Graph::NormalizeLinks(void)
211 {
212 if (m_pRoot != NULL)
213 {
214 SetAsUnprocessed();
215 m_pRoot->SetAsProcessed();
216 NormalizeVertexLinks(m_pRoot);
217 }
218 }