Browse Prior Art Database

Algorithm to position a connected, directed and ordered network of entities on a two dimensional canvas respecting the direction and order-properties of connections

IP.com Disclosure Number: IPCOM000015212D
Original Publication Date: 2001-Sep-16
Included in the Prior Art Database: 2003-Jun-20
Document File: 4 page(s) / 35K

Publishing Venue

IBM

Abstract

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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 39% of the total text.

Page 1 of 4

  Algorithm to position a connected, directed and ordered network of entities on a two dimensional canvas respecting the direction and order-properties of connections

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.

Terminology used:

child: any nodes with a direct connection from a node are
children of that
node
sibling: after the first stage (see below) all nodes allocated
to the same 'level'
are siblings.

         Note that children of a node are not necessarily
siblings.
input node: an input node is one that is required to be in the
left most level.

         This is specified in the definition of the node type.
Note that there can be different "types" of nodes with
differing
numbers of output terminals.

The algorithm consists of four stages:

1

Page 2 of 4

Stage 1) Virtual node

    To provide determinism and to simplify some special cases
later on, we define a virtual first node which we consider all
other nodes to be children of. This allows us to have one 'first'
node rather than the potential multiple nodes when more than one
'input node' is present. (As an optimisation, it is necessary to
only link this virtual node to the designated input nodes). We
assign this virtual first node to level 0.

Stage 2) Horizontal positioning

    This stage assigns the nodes to columns. We satisfy
criterion b) above.

    Each node possesses a 'depth' property that is initially set
to zero. Starting at the virtual first node, we recursively
follow the connections to its children. We maintain a count of
how many connections we followed to reach the node. At each node
reached, if the current depth is greater than its i...