Browse Prior Art Database

New approach to Dependency Sorting Disclosure Number: IPCOM000129035D
Original Publication Date: 2005-Sep-27
Included in the Prior Art Database: 2005-Sep-27
Document File: 4 page(s) / 112K

Publishing Venue



The present publication relates to a modelling tools software. In a business process, activities having inter-dependencies must be executed based on their dependency level. For instance if activity A depends on activity B, then activity B must be executed before A. The object of the present publication is to reorder an input tree of inter-dependent activities to a tree having activities sorted according to their relative dependencies.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 4

New approach to Dependency Sorting


A tree is a construct of nodes in a multi-layer hierarchy. Normally all nodes contain the same type and structure of data. The following figure shows an example of a simple tree.


1 2 3

4 5

The tree consists of 6 nodes, each node comprising data. The upper node is a special node called "Root". The Root is at the origin of the tree. The lower nodes are called "leaf" (nodes 4 and 5). Leaves have no child nodes. Also nodes which have children are called "parent". For instance, node 1 is parent of both nodes 4 and 5. All nodes are parent except leaves which have no children. The maximum number of children that any parent can have in a tree is called the "order" of the tree. For instance a tree of order 3 means that every parent node can have a maximum of 3 child nodes.

In a tree, nodes are organized in layers also known as "levels". For instance, the tree shown in the figure here above comprises 3 layers.

It is possible to define tree with specific constrains related to the order, the number of layers (maximum or minimum number of layers), the number of nodes (maximum number of nodes), the content and connectivity of the nodes, ....

Input Tree

The following tree shows the inter-dependencies between nodes :


[This page contains 1 picture or other non-text object]

Page 2 of 4

In this example, the tree comprises a Root and 3 levels of nodes. This tree has the following properties:
1. The tree order is unlimited ("Each node can have an unlimited number of children"), however "each node has only one parent".
2. There is no special constraint on the tree.
3. The parent-child relation is represented for each node in the figure by a level (For example, nodes from 1 to 6 are in level 1, nodes from 7 to 11 are in level 2 and so on).
4. Arrows in the figure represent dependencies between nodes (and not the parent-child relation).
5. The arrow represents a dependency direction. For example, the arrow from node 13 to node 5 means that node 5 depends on node 13. Hence node 13 must appear in the output tree at a level higher than node 5. This means that the activity represented by node 13 must be executed before the activity represented by node 5 .
6. The parent-child link is not shown in the graph for simplicity reasons and also because the parent-child link is not important for the algorithm. The parent-child link is not important because in the algorithm the parent-child link will be broken into another parent-child relation. Thus it does not matter to know which node is parent and which node is child.
8. The root is a virtual dummy node and must appear first in the input and output trees.