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

# Method to Traverse and Display a Rooted Directed Acyclic Graph using Preferred Parentage

IP.com Disclosure Number: IPCOM000014943D
Original Publication Date: 2001-Aug-01
Included in the Prior Art Database: 2003-Jun-20
Document File: 3 page(s) / 63K

IBM

## Abstract

Method to Traverse and Display a Rooted Directed Acyclic Graph using Preferred Parentage Disclosed is a method to search and display a rooted Directed Acyclic Graph (DAG). It is achieved by superimposing a tree over the DAG. That is, each node specifies a preferred parent. This provides single path from an individual node to the root node. A DAG is defined as having:

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

Page 1 of 3

Method to Traverse and Display a Rooted Directed Acyclic Graph using Preferred

Parentage

Disclosed is a method to search and display a rooted Directed Acyclic Graph (DAG). It is achieved by superimposing a tree over the DAG. That is, each node specifies a preferred parent. This provides single path from an individual node to the root node.

A DAG is defined as having:

An arbitrary number of nodes. An arbitrary number of children stemming from a given node. An arbitrary number of parents leading to a given node. An arbitrary number of roots (nodes with no parents). Nodes or connected groups of nodes need not be connected. For example: P1--->P2, P3--->P4, P3--->P5 is a valid DAG, even though P1 and P3 are in no way connected. There can be at most one arc between two given nodes. The DAG must be acyclic, that is, there cannot be a closed circle of A--->B--->C---> ... --->A.

A rooted DAG is a DAG where all nodes are reachable from a root element.

Therefore with the "preferred parent" superimposed over a rooted DAG, it is possible to:
· Navigate down the DAG from the root by successively opening parent nodes and selecting a child to be the next parent.

· Navigate up the tree from any node to the root by following the preferred parent.

Here is an example rooted DAG showing categories. The thick solid lines show the preferred parentage. The one dashed line shows non-preferred parentage (between JDBC and RDBMS).

1

Page 2 of 3

ROOT

Database

Java RDBMS

OODBMS

EJB RMI JDBC SQL

Below is the preferred UML class model to describe this category hierarchy with preferred parentage. Of course additional attributes can be added to the classes Category and CategoryList for the required applic...