Method for Interactive Progressive Layout of Graph with Fixed Directional Anchor Points (18-Jan-2010)

Method for Interactive Progressive Layout of Graph with Fixed Directional Anchor Points

Disclosed is a process including a progressive layout algorithm that supports randomness in a graph and provides a layout capability for new nodes enabling a user to see all of the new nodes, while at the same time minimally disturbing the existing relative node positions. A typical graph, with nodes and edges, is illustrated in Figure 1. The left edges of the nodes act as the target of edges. The bottom edges of nodes may also serve as the target of edges. Likewise, the right or top edges of nodes act as the source of edges. Each of these edge anchor locations can be expanded or collapsed to show or hide nodes in the graph, as the user requires.

Figure 1

The example of Figure 1 will be used to illustrate the disclosed process. For example, when the user selects to expand the right side of Node 3, logic of the disclosed process determines the nodes that need to be added to the canvas or presentation space. The nodes are spaced apart with a predetermined padding space and centered to the right of Node 3. Figure 2 illustrates the "target area" for the expanded nodes to reside.

Figure 2

Once the target area is determined for the new nodes, all existing nodes in the graph are checked to determine whether the existing nodes overlap the target area. When a node overlaps, all nodes in the

1

                                                           et area, plus a constant padding value. Figure 3 shows the search region for nodes that need to be moved.

Figure 3

In Figure 3 it is apparent that Node 6 overlaps the search region. Therefore Node 6 is moved to the right by the width of the target area, plus a constant padding amount. The just relocated Node 6 is shown in Figure 4.

Figure 4

While moving Node 6, the relocation process may be animated, to aid the user maintain a mental map of the graph. After Node 6 is moved, new associated nodes are added into the empty space of the target area, as shown in Figure 5.

tar

g

et area and to the ri

g

ht of the tar

g

et area are identified and moved b

y

the width of the tar

g

2

Figure 5

The layout algorithm of the disclosed process attempts to locate existing nodes connected to the node being expanded. For example, when a user expands the right edge of Node 5 that is connected to Node 6 and other nodes that are not currently in the graph. Using the layout algorithm of the disclosed process again with the disclosed feature, the same initial steps occur. The nodes that need to be added are identified and the target area for the identified nodes is calculated. In this case, two new nodes are added because Node 6 is already in the graph. The target area for the two nodes is shown in Figure 6.

Figure 6

The algorithm of...