Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Algorithm to prevent circular dependencies

IP.com Disclosure Number: IPCOM000014154D
Original Publication Date: 2001-Feb-01
Included in the Prior Art Database: 2003-Jun-19
Document File: 5 page(s) / 50K

Publishing Venue

IBM

Abstract

This invention analyzes a heirarchical tree that will be referred to from this point as a "dependency tree" and identifies circular dependencies between nodes. Based on return codes from the algorithm, the calling routine is then able take the appropriate actions to prevent circular dependencies from occuring. So that this algorithm may be more valuable to the reader, the assumptions made for it's originating implementation will be described briefly. This algorithm was implemented with the following assumptions. First, two objects may have a Finish-to-Start relationship. (I.E. Assuming two objects (A, B) have a Finish-to-Start relationship, object A must complete before object B may start.) Next, the relationships between objects are many to many(N:N). Finally, an perhaps obvious, the Finish-to-Start relationship may also be referred to as a successor-to-predecessor relationship. To prevent the problem of circular dependencies, this algorithm, first, constructs a dependency tree. The dependency tree maps all current dependencies between objects. The resulting dependency tree accounts for successor relationships only since it is heirarchical in nature. See the following example: Next, each object is evaluated. Relative to the current object, all other objects are evaluated and sorted into two lists, one for "Available Predecessors" and another for "Available Successors". Those objects that do not qualify for either list are excluded.

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 32% of the total text.

Page 1 of 5

Algorithm to prevent circular dependencies

     This invention analyzes a heirarchical tree that will be referred to from this point as a "dependency tree" and identifies circular dependencies between nodes. Based on return codes from the algorithm, the calling routine is then able take the appropriate actions to prevent circular dependencies from occuring. So that this algorithm may be more valuable to the reader, the assumptions made for it's originating implementation will be described briefly.

     This algorithm was implemented with the following assumptions. First, two objects may have a Finish-to-Start relationship. (I.E. Assuming two objects (A, B) have a Finish-to-Start relationship, object A must complete before object B may start.) Next, the relationships between objects are many to many(N:N). Finally, an perhaps obvious, the Finish-to-Start relationship may also be referred to as a successor-to-predecessor relationship.

     To prevent the problem of circular dependencies, this algorithm, first, constructs a dependency tree. The dependency tree maps all current dependencies between objects. The resulting dependency tree accounts for successor relationships only since it is heirarchical in nature. See the following example:

Next, each object is evaluated. Relative to the current object, all other objects are evaluated and sorted into two lists, one for "Available Predecessors" and another for "Available Successors". Those objects that do not qualify for either list are excluded.

To qualify, the following criteria are used: A valid predecessor object...

(1) May not be an immediate predecessor.
(2) May not include descendents to the leaf nodes. A valid successor object...

(1) May not be an immediate successor.
(2) May not include ancestors to the root node.

     Once all nodes have been sorted into one of these two lists, additional dependencies may be established. After each dependency has been added or removed, the algorithm is re-executed to determine the currently available predecessor and/or successor nodes.

CODE EXCERPTS -

Record Defintion:

R_DEPENDENCY_TREE_REC IS RECORD

sched_id : INTEGER; - - Parent node

1

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

Page 2 of 5

c_node_id : LIST OF INTEGER; - - Child node

END;

Code:

(*==========================================================================

*

* Function Name : R_qualifyAsPredecessor

*

* Syntax : R_qualifyAsPredecessor(VAL id_in_question: INTEGER,

* VAL id_being_edited: INTEGER,

* VAL task_being_edited_status_id: INTEGER,

* VAL this_tree: LIST OF R_DEPENDENCY_TREE_REC): BOOLEAN

*

* Parameters : id_in_question - id of the task object that is a potential predecessor.

* id_being_edited - id of the task object to which the id_in_question is a potential

* predecessor.

* task_being_edited_status_id - status of the task object being edited.

* this_tree - list of dependency trees that contain the dependency

* relationships being evaluated against.

*

* Returns : BOOLEAN

*

* Side Eff...