System for arranging a plurality of relational nodes into graphical layout form

Abstract

A system for arranging a plurality of nodes into graphical layout form partitions the nodes into a set of clusters from which a cluster graph is created. The cluster partitioning is based on the inter-nodal relationships, and cluster size depends on the number of nodes associated with each cluster. The clusters are laid out to avoid overlap, and cluster boundaries, within which nodes in a cluster are constrained, are generated. Nodes of each cluster as classified as either internal or boundary nodes, with boundary nodes being projected outward towards the boundary of the cluster. As an optional step, connection edges between nodes are routed to avoid overlap.

1 . A method for generating a graphical layout for a plurality of nodes based on the presence of predetermined inter-nodal relationships between the nodes, the method comprising: 
 grouping nodes into one or more clusters, each containing one or more nodes, based on the inter-nodal relationships;    determining inter-cluster relationships from the inter-nodal relationships;    determining a spatial layout of the clusters; and    for each cluster containing multiple nodes, 
 determining a boundary for the cluster;  
 classifying the nodes in the cluster as either internal or boundary nodes;  
 projecting the boundary nodes to the boundary of the cluster; and  
 determining a spatial layout of the internal nodes.  
   
   
   
       2 . The method of  claim 1 , wherein said grouping comprises: 
 balancing a cluster size parity optimization operation with a cluster connectivity minimization operation,    wherein said cluster size parity optimization operation comprises attempting to achieve clusters whose sizes are as close to one another as possible, and wherein said connectivity minimization operation comprises attempting to minimize the number of connections between clusters, each connection representing an inter-nodal relationship    
   
   
       3 . The method of  claim 1 , wherein determining a spatial layout of the clusters comprises using a spring-directed algorithm.  
   
   
       4 . The method of  claim 1 , wherein determining a spatial layout of the clusters comprises using a force-directed algorithm.  
   
   
       5 . The method of  claim 1 , wherein determining a spatial layout of the internal nodes comprises using a spring-directed algorithm.  
   
   
       6 . The method of  claim 1 , wherein determining a spatial layout of the internal nodes comprises using a force-directed algorithm.  
   
   
       7 . The method of  claim 1 , wherein the boundary is circular.  
   
   
       8 . The method of  claim 1 , further comprising providing non-overlapping connection edges between nodes.  
   
   
       9 . The method of  claim 1 , wherein determining a spatial layout of the clusters, classifying the nodes in the cluster as either internal or boundary nodes, and determining a spatial layout of the internal nodes are performed using existing node positions.  
   
   
       10 . The method of  claim 9 , wherein a calculation of previously existing groups is performed using a proximity graph.