Algorithm to position a connected, directed and ordered network of entities on a two dimensional canvas respecting the direction and order-properties of connections
Original Publication Date: 2001-Sep-16
Included in the Prior Art Database: 2003-Jun-20
Consider an ordered network of connected 'nodes'. Assume each node has a number of 'output terminals'. A connection from one node to another will join a single output teminal of a node to the unique input terminal of the following node. Assume the network is described in a flat file as an XML representation, for example. The information stored is a list of the nodes and a list of the connections between them specifying the output node and terminal and the input node and terminal of each connection but no information on relative positioning in physical space. The invention represents an algorithm (and implementation) to take a representation of the nodes and the connections between them and position them on a two dimensional canvas such that: a) no two nodes are placed within a given distance of each other b) the flow of connections is always from left to right i.e. there are no outbound connections pointing from right to left. c) gratuitous crossing of connections is avoided and logically-related nodes appear close together on the canvas. What makes the invention novel is that it offers a solution to the problem of drawing a directed network on a canvas where there is an ordered output from each node. A usual solution to this problem is to add extra "virtual" nodes at each stage such that connections from the same terminal are associated with the same virtual node. However, this solution allows the ordering of the output terminals to be respected.