Implemented simple graph layout algorithm - radial layout for connected oriented...
authorVictor Kirhenshtein <victor@netxms.org>
Wed, 6 Dec 2006 16:34:11 +0000 (16:34 +0000)
committerVictor Kirhenshtein <victor@netxms.org>
Wed, 6 Dec 2006 16:34:11 +0000 (16:34 +0000)
.gitattributes
include/netxms_maps.h
src/console/win32/MapView.cpp
src/console/win32/ObjectDepView.cpp
src/libnxmap/Makefile.am
src/libnxmap/graph.cpp [new file with mode: 0644]
src/libnxmap/libnxmap.dsp
src/libnxmap/libnxmap.h
src/libnxmap/radial.cpp [new file with mode: 0644]
src/libnxmap/submap.cpp
src/libnxmap/vertex.cpp [copied from src/libnxmap/libnxmap.h with 54% similarity]

index 94b81b2..1c4612b 100644 (file)
@@ -1031,13 +1031,16 @@ src/libnxcl/snmp.cpp -text
 src/libnxcl/snmptrap.cpp -text
 src/libnxcl/users.cpp -text
 src/libnxmap/Makefile.am -text
+src/libnxmap/graph.cpp -text
 src/libnxmap/libnxmap.dsp -text
 src/libnxmap/libnxmap.dsw -text
 src/libnxmap/libnxmap.h -text
 src/libnxmap/main.cpp -text
 src/libnxmap/map.cpp -text
 src/libnxmap/objlist.cpp -text
+src/libnxmap/radial.cpp -text
 src/libnxmap/submap.cpp -text
+src/libnxmap/vertex.cpp -text
 src/libnxsl/Makefile.am -text
 src/libnxsl/class.cpp -text
 src/libnxsl/compiler.cpp -text
index b8d578d..6ec7f27 100644 (file)
 #define SUBMAP_ATTR_LAYOUT_COMPLETED      0x00010000
 
 
+//
+// Submap layout methods
+//
+
+#define SUBMAP_LAYOUT_DUMB          0
+#define SUBMAP_LAYOUT_RADIAL        1
+
+
 //
 // User access rights
 //
@@ -139,6 +147,59 @@ public:
 };
 
 
+//
+// Graph's vertex
+//
+
+class LIBNXMAP_EXPORTABLE nxVertex
+{
+protected:
+   DWORD m_dwId;
+   DWORD m_dwNumLinks;
+   nxVertex **m_ppLinkList;
+   int m_posX;
+   int m_posY;
+
+public:
+   nxVertex(DWORD dwId);
+   ~nxVertex();
+
+   DWORD GetId(void) { return m_dwId; }
+   int GetPosX(void) { return m_posX; }
+   int GetPosY(void) { return m_posY; }
+   DWORD GetNumLinks(void) { return m_dwNumLinks; }
+   nxVertex *GetLink(DWORD dwIndex) { return (dwIndex < m_dwNumLinks) ? m_ppLinkList[dwIndex] : NULL; }
+
+   void Link(nxVertex *pVtx);
+   void SetPosition(int x, int y) { m_posX = x; m_posY = y; }
+};
+
+
+//
+// Connected graph
+//
+
+class LIBNXMAP_EXPORTABLE nxGraph
+{
+protected:
+   DWORD m_dwVertexCount;
+   nxVertex **m_ppVertexList;
+
+public:
+   nxGraph();
+   nxGraph(DWORD dwNumObjects, DWORD *pdwObjectList, DWORD dwNumLinks, OBJLINK *pLinkList);
+   ~nxGraph();
+
+   DWORD GetVertexCount(void) { return m_dwVertexCount; }
+   nxVertex *FindVertex(DWORD dwId);
+   DWORD GetVertexIndex(nxVertex *pVertex);
+   nxVertex *GetRootVertex(void) { return m_dwVertexCount > 0 ? m_ppVertexList[0] : NULL; }
+   nxVertex *GetVertexByIndex(DWORD dwIndex) { return dwIndex < m_dwVertexCount ? m_ppVertexList[dwIndex] : NULL; }
+
+   void NormalizeVertexPositions(void);
+};
+
+
 //
 // Submap class
 //
@@ -171,7 +232,7 @@ public:
    BOOL IsLayoutCompleted(void) { return (m_dwAttr & SUBMAP_ATTR_LAYOUT_COMPLETED) ? TRUE : FALSE; }
    void DoLayout(DWORD dwNumObjects, DWORD *pdwObjectList,
                  DWORD dwNumLinks, OBJLINK *pLinkList,
-                 int nIdealX, int nIdealY);
+                 int nIdealX, int nIdealY, int nMethod);
    POINT GetObjectPosition(DWORD dwObjectId);
    POINT GetObjectPositionByIndex(DWORD dwIndex);
    void SetObjectPosition(DWORD dwObjectId, int x, int y);
index 93a75c3..30bc632 100644 (file)
@@ -536,14 +536,16 @@ void CMapView::DoSubmapLayout()
             safe_free(pdwSubnetList);
 
             m_pSubmap->DoLayout(dwObjListSize, pdwObjectList,
-                                dwNumLinks, pLinkList, rect.right, rect.bottom);
+                                dwNumLinks, pLinkList, rect.right, rect.bottom,
+                                SUBMAP_LAYOUT_DUMB);
             safe_free(pdwObjectList);
             safe_free(pLinkList);
          }
          else
          {
             m_pSubmap->DoLayout(pObject->dwNumChilds, pObject->pdwChildList,
-                                0, NULL, rect.right, rect.bottom);
+                                0, NULL, rect.right, rect.bottom,
+                                SUBMAP_LAYOUT_DUMB);
          }
          m_bIsModified = TRUE;
       }
index b76f1fe..8790955 100644 (file)
@@ -98,7 +98,8 @@ void CObjectDepView::Refresh()
    
    pSubmap = new nxSubmap((DWORD)0);
    pSubmap->DoLayout(list.GetNumObjects(), list.GetObjects(),
-                     list.GetNumLinks(), list.GetLinks(), rect.right, rect.bottom);
+                     list.GetNumLinks(), list.GetLinks(), rect.right, rect.bottom,
+                     SUBMAP_LAYOUT_RADIAL);
    pMap->AddSubmap(pSubmap);
    m_wndMap.SetMap(pMap);
 }
index e80cdb8..a0bffad 100644 (file)
@@ -1,7 +1,8 @@
 INCLUDES=-I@top_srcdir@/include
 
 lib_LTLIBRARIES = libnxmap.la
-libnxmap_la_SOURCES = main.cpp map.cpp objlist.cpp submap.cpp
+libnxmap_la_SOURCES = graph.cpp main.cpp map.cpp objlist.cpp radial.cpp \
+                     submap.cpp vertex.cpp
 libnxmap_la_LDFLAGS = -version-info $(NETXMS_LIBRARY_VERSION) $(PTHREAD_LIBS)
 libnxmap_la_LIBADD = ../libnetxms/libnetxms.la
 
diff --git a/src/libnxmap/graph.cpp b/src/libnxmap/graph.cpp
new file mode 100644 (file)
index 0000000..eb6024f
--- /dev/null
@@ -0,0 +1,141 @@
+/* 
+** NetXMS - Network Management System
+** Network Maps Library
+** Copyright (C) 2006 Victor Kirhenshtein
+**
+** This program is free software; you can redistribute it and/or modify
+** it under the terms of the GNU General Public License as published by
+** the Free Software Foundation; either version 2 of the License, or
+** (at your option) any later version.
+**
+** This program is distributed in the hope that it will be useful,
+** but WITHOUT ANY WARRANTY; without even the implied warranty of
+** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+** GNU General Public License for more details.
+**
+** You should have received a copy of the GNU General Public License
+** along with this program; if not, write to the Free Software
+** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+**
+** File: graph.cpp
+**
+**/
+
+#include "libnxmap.h"
+
+
+//
+// Default constructor
+//
+
+nxGraph::nxGraph()
+{
+   m_dwVertexCount = 0;
+   m_ppVertexList = NULL;
+   m_dwVertexCount = 0;
+   m_ppVertexList = NULL;
+}
+
+
+//
+// Create graph from list of objects and links
+//
+
+nxGraph::nxGraph(DWORD dwNumObjects, DWORD *pdwObjectList,
+                 DWORD dwNumLinks, OBJLINK *pLinkList)
+{
+   DWORD i;
+   nxVertex *pVtx1, *pVtx2;
+
+   m_dwVertexCount = dwNumObjects;
+   m_ppVertexList = (nxVertex **)malloc(sizeof(nxVertex *) * dwNumObjects);
+   for(i = 0; i < dwNumObjects; i++)
+   {
+      m_ppVertexList[i] = new nxVertex(pdwObjectList[i]);
+   }
+
+   // Create links between vertexes
+   for(i = 0; i < dwNumLinks; i++)
+   {
+      pVtx1 = FindVertex(pLinkList[i].dwId1);
+      pVtx2 = FindVertex(pLinkList[i].dwId2);
+      if ((pVtx1 != NULL) && (pVtx2 != NULL))
+         pVtx1->Link(pVtx2);
+   }
+}
+
+
+//
+// Destructor
+//
+
+nxGraph::~nxGraph()
+{
+   DWORD i;
+
+   for(i = 0; i < m_dwVertexCount; i++)
+      delete m_ppVertexList[i];
+   safe_free(m_ppVertexList);
+}
+
+
+//
+// Find vertex by ID
+//
+
+nxVertex *nxGraph::FindVertex(DWORD dwId)
+{
+   DWORD i;
+
+   for(i = 0; i < m_dwVertexCount; i++)
+      if (m_ppVertexList[i]->GetId() == dwId)
+         return m_ppVertexList[i];
+   return NULL;
+}
+
+
+//
+// Get internal index of given vertex
+//
+
+DWORD nxGraph::GetVertexIndex(nxVertex *pVertex)
+{
+   DWORD i;
+
+   for(i = 0; i < m_dwVertexCount; i++)
+      if (m_ppVertexList[i]->GetId() == pVertex->GetId())
+         return i;
+   return INVALID_INDEX;
+}
+
+
+//
+// Normalize vertex positions
+//
+
+void nxGraph::NormalizeVertexPositions(void)
+{
+   DWORD i;
+   int x, y, dx, dy;
+
+   // Calculate required offset
+   for(i = 0, dx = 0, dy = 0; i < m_dwVertexCount; i++)
+   {
+      x = m_ppVertexList[i]->GetPosX();
+      if (x < MAP_LEFT_MARGIN)
+         if (dx < MAP_LEFT_MARGIN - x)
+            dx = MAP_LEFT_MARGIN - x;
+      y = m_ppVertexList[i]->GetPosY();
+      if (y < MAP_TOP_MARGIN)
+         if (dy < MAP_TOP_MARGIN - y)
+            dy = MAP_TOP_MARGIN - y;
+   }
+
+   // Change coordinates
+   if ((dx != 0) || (dy != 0))
+   {
+      for(i = 0; i < m_dwVertexCount; i++)
+         m_ppVertexList[i]->SetPosition(m_ppVertexList[i]->GetPosX() + dx,
+                                        m_ppVertexList[i]->GetPosY() + dy);
+   }
+}
index 126b58a..890a901 100644 (file)
@@ -168,6 +168,10 @@ PostBuild_Cmds=copy Release_UNICODE\libnxmapw.dll C:\NetXMS\bin
 # PROP Default_Filter "cpp;c;cxx;rc;def;r;odl;idl;hpj;bat"
 # Begin Source File
 
+SOURCE=.\graph.cpp
+# End Source File
+# Begin Source File
+
 SOURCE=.\main.cpp
 # End Source File
 # Begin Source File
@@ -180,8 +184,16 @@ SOURCE=.\objlist.cpp
 # End Source File
 # Begin Source File
 
+SOURCE=.\radial.cpp
+# End Source File
+# Begin Source File
+
 SOURCE=.\submap.cpp
 # End Source File
+# Begin Source File
+
+SOURCE=.\vertex.cpp
+# End Source File
 # End Group
 # Begin Group "Header Files"
 
index ac6d361..bc79d3e 100644 (file)
 #include <nxcpapi.h>
 #include <netxms_maps.h>
 
+
+//
+// Generic layout engine
+//
+
+class nxleGeneric
+{
+protected:
+   nxGraph *m_graph;
+
+public:
+   nxleGeneric(nxGraph *pGraph) { m_graph = pGraph; }
+   virtual ~nxleGeneric() { }
+
+   virtual void Execute(void) { }
+};
+
+
+//
+// Radial layout engine
+//
+
+class nxleRadial : public nxleGeneric
+{
+protected:
+   double *m_width;
+   double *m_fullWidth;
+   double *m_angle;
+   double *m_distance;
+   double m_delta;
+   double m_increase;
+   BOOL m_bConvexity;
+
+   double SetWidth(nxVertex *root);
+   void SetPlacement(nxVertex *root, double ro,
+                     double alpha1, double alpha2,     int layer);
+
+public:
+   nxleRadial(nxGraph *pGraph);
+   virtual ~nxleRadial();
+
+   virtual void Execute(void);
+};
+
 #endif   /* _libnxmap_h_ */
diff --git a/src/libnxmap/radial.cpp b/src/libnxmap/radial.cpp
new file mode 100644 (file)
index 0000000..af965b2
--- /dev/null
@@ -0,0 +1,158 @@
+/* 
+** NetXMS - Network Management System
+** Network Maps Library
+** Copyright (C) 2006 Victor Kirhenshtein
+**
+** This program is free software; you can redistribute it and/or modify
+** it under the terms of the GNU General Public License as published by
+** the Free Software Foundation; either version 2 of the License, or
+** (at your option) any later version.
+**
+** This program is distributed in the hope that it will be useful,
+** but WITHOUT ANY WARRANTY; without even the implied warranty of
+** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+** GNU General Public License for more details.
+**
+** You should have received a copy of the GNU General Public License
+** along with this program; if not, write to the Free Software
+** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+**
+** File: radial.cpp
+**
+**/
+
+#include "libnxmap.h"
+#include <math.h>
+
+#define PI     3.14159
+
+
+//
+// Constructor
+//
+
+nxleRadial::nxleRadial(nxGraph *pGraph)
+           :nxleGeneric(pGraph)
+{
+   m_bConvexity = FALSE;
+   m_delta = MAP_OBJECT_SIZE_X + MAP_OBJECT_INTERVAL_X;
+   m_increase = 50.0 * m_delta / 100.0;
+   m_width = (double *)malloc(pGraph->GetVertexCount() * sizeof(double));
+   m_fullWidth = (double *)malloc(pGraph->GetVertexCount() * sizeof(double));
+   m_angle = (double *)malloc(pGraph->GetVertexCount() * sizeof(double));
+   m_distance = (double *)malloc(pGraph->GetVertexCount() * sizeof(double));
+}
+
+
+//
+// Destructor
+//
+
+nxleRadial::~nxleRadial()
+{
+   safe_free(m_width);
+   safe_free(m_fullWidth);
+   safe_free(m_angle);
+   safe_free(m_distance);
+}
+
+
+//
+// Position the tree rooted at "root".
+// The allocated posiition is not final; each sub-tree is positioned
+// on the assumption that its parent is located at the origin, and all
+// nodes are positioned in the plane z=0.  This will be corrected in a
+// second pass over the tree.
+//
+// The return value is the radius of the circle containing the layout
+// of this (sub)-tree.
+//
+
+double nxleRadial::SetWidth(nxVertex *root)
+{
+       double width;
+   DWORD i;
+
+   if (root->GetNumLinks() == 0)
+   {
+      width = MAP_OBJECT_SIZE_X;
+   }
+   else
+   {
+      width = 0.0;
+      for(i = 0; i < root->GetNumLinks(); i++)
+      {
+         width += SetWidth(root->GetLink(i)) + MAP_OBJECT_INTERVAL_X;
+      }
+   }
+       m_width[m_graph->GetVertexIndex(root)] = width;
+       m_fullWidth[m_graph->GetVertexIndex(root)] = width;
+       return width;
+}
+
+
+//
+// Calculate the final layout for a node, given its level in 
+// the tree, and the (final) position of its parent.
+//
+
+void nxleRadial::SetPlacement(nxVertex *root, double ro,
+                              double alpha1, double alpha2,    int layer)
+{
+   double s, tau, alpha, rootFullWidth, childWidth;
+   double myDelta = m_delta + m_increase;
+   double fi = (alpha1 + alpha2)/2.0;
+   DWORD i, index;
+   nxVertex *child;
+
+       root->SetPosition((int)(ro * sin(fi)), (int)(ro * cos(fi)));
+
+   index = m_graph->GetVertexIndex(root);
+       m_angle[index] = fi;
+       m_distance[index] = ro;
+       
+   if (root->GetNumLinks() > 0)
+   {
+      tau = m_bConvexity ? 2.0 * acos(ro / (ro + myDelta)) : 0.0;
+               rootFullWidth = m_fullWidth[index];
+               if (m_bConvexity && (ro != 0.0) && (tau < (alpha2 - alpha1)))
+      {
+         s = tau / rootFullWidth;
+         alpha = (alpha1 + alpha2 - tau) / 2.0;
+      }
+               else 
+      {
+         s = (alpha2 - alpha1) / rootFullWidth;
+         alpha = alpha1;
+      }
+
+      for(i = 0; i < root->GetNumLinks(); i++)
+      {
+         child = root->GetLink(i);
+                       childWidth = m_width[m_graph->GetVertexIndex(child)];
+                       SetPlacement(child, ro + myDelta, alpha,
+                      alpha + s * childWidth, layer + 1);
+                       alpha += s * childWidth;
+      }
+   }
+}
+
+
+//
+// Execute
+//
+
+void nxleRadial::Execute(void)
+{
+   if (m_graph->GetVertexCount() == 0)
+      return;
+
+   // Layout is performed in two passes.  First, find a provisional location
+   // for each node, via a bottom-up traversal.  Then calculate a final 
+   // position for each node, by performing a top-down traversal, placing
+   // the root at the origin, and then positioning each child using the
+   // provisional location of the child and final location of the parent.
+
+   SetWidth(m_graph->GetRootVertex());
+   SetPlacement(m_graph->GetRootVertex(), 0.0, 0.0, 2.0 * PI, 0);
+}
index 3924dcd..8bc47d7 100644 (file)
@@ -346,7 +346,7 @@ POINT nxSubmap::GetMinSize(void)
 
 void nxSubmap::DoLayout(DWORD dwNumObjects, DWORD *pdwObjectList,
                         DWORD dwNumLinks, OBJLINK *pLinkList,
-                        int nIdealX, int nIdealY)
+                        int nIdealX, int nIdealY, int nMethod)
 {
    DWORD i;
    int x, y;
@@ -358,16 +358,47 @@ void nxSubmap::DoLayout(DWORD dwNumObjects, DWORD *pdwObjectList,
    safe_free_and_null(m_pObjectList);
    m_dwNumObjects = 0;
 
-   for(i = 0, x = MAP_LEFT_MARGIN, y = MAP_TOP_MARGIN; i < dwNumObjects; i++)
+   if (nMethod == SUBMAP_LAYOUT_DUMB)
    {
-      SetObjectPosition(pdwObjectList[i], x, y);
-      x += MAP_OBJECT_SIZE_X + MAP_OBJECT_INTERVAL_X;
-      if (x >= nIdealX - MAP_OBJECT_SIZE_X - MAP_OBJECT_INTERVAL_X / 2)
+      for(i = 0, x = MAP_LEFT_MARGIN, y = MAP_TOP_MARGIN; i < dwNumObjects; i++)
       {
-         x = MAP_LEFT_MARGIN;
-         y += MAP_OBJECT_SIZE_Y + MAP_TEXT_BOX_HEIGHT + MAP_OBJECT_INTERVAL_Y;
+         SetObjectPosition(pdwObjectList[i], x, y);
+         x += MAP_OBJECT_SIZE_X + MAP_OBJECT_INTERVAL_X;
+         if (x >= nIdealX - MAP_OBJECT_SIZE_X - MAP_OBJECT_INTERVAL_X / 2)
+         {
+            x = MAP_LEFT_MARGIN;
+            y += MAP_OBJECT_SIZE_Y + MAP_TEXT_BOX_HEIGHT + MAP_OBJECT_INTERVAL_Y;
+         }
       }
    }
+   else
+   {
+      nxleGeneric *engine;
+      nxGraph *graph;
+      nxVertex *vertex;
+
+      graph = new nxGraph(dwNumObjects, pdwObjectList, dwNumLinks, pLinkList);
+      switch(nMethod)
+      {
+         case SUBMAP_LAYOUT_RADIAL:
+            engine = new nxleRadial(graph);
+            break;
+         default: // Unknown method, do nothing
+            engine = new nxleGeneric(graph);
+            break;
+      }
+
+      engine->Execute();
+      delete engine;
+
+      graph->NormalizeVertexPositions();
+      for(i = 0; i < dwNumObjects; i++)
+      {
+         vertex = graph->GetVertexByIndex(i);
+         SetObjectPosition(vertex->GetId(), vertex->GetPosX(), vertex->GetPosY());
+      }
+      delete graph;
+   }
    
    m_dwAttr |= SUBMAP_ATTR_LAYOUT_COMPLETED;
 }
similarity index 54%
copy from src/libnxmap/libnxmap.h
copy to src/libnxmap/vertex.cpp
index ac6d361..c010794 100644 (file)
@@ -1,6 +1,6 @@
 /* 
 ** NetXMS - Network Management System
-** Network Map Library
+** Network Maps Library
 ** Copyright (C) 2006 Victor Kirhenshtein
 **
 ** This program is free software; you can redistribute it and/or modify
 ** along with this program; if not, write to the Free Software
 ** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 **
-** File: libnxmap.h
+** File: vertex.cpp
 **
 **/
 
-#ifndef _libnxmap_h_
-#define _libnxmap_h_
+#include "libnxmap.h"
 
-#include <nms_common.h>
-#include <nms_util.h>
-#include <nms_threads.h>
-#include <nxcpapi.h>
-#include <netxms_maps.h>
 
-#endif   /* _libnxmap_h_ */
+//
+// Constructor
+//
+
+nxVertex::nxVertex(DWORD dwId)
+{
+   m_dwId = dwId;
+   m_posX = 0;
+   m_posY = 0;
+   m_dwNumLinks = 0;
+   m_ppLinkList = NULL;
+}
+
+
+//
+// Destructor
+//
+
+nxVertex::~nxVertex()
+{
+   safe_free(m_ppLinkList);
+}
+
+
+//
+// Link another vertex
+//
+
+void nxVertex::Link(nxVertex *pVtx)
+{
+   DWORD i;
+
+   for(i = 0; i < m_dwNumLinks; i++)
+      if (m_ppLinkList[i] == pVtx)
+         break;   // Already linked
+   if (i == m_dwNumLinks)
+   {
+      m_dwNumLinks++;
+      m_ppLinkList = (nxVertex **)realloc(m_ppLinkList, sizeof(nxVertex *) * m_dwNumLinks);
+      m_ppLinkList[i] = pVtx;
+   }
+}