Browse Prior Art Database

Three-Dimensional Layout Algorithm for Directed Acylic Graphs

IP.com Disclosure Number: IPCOM000118912D
Original Publication Date: 1997-Sep-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 97K

Publishing Venue

IBM

Related People

Makbily, Y: AUTHOR [+3]

Abstract

Until now, most of the work done on the subject concerns visualization of graphs in 2 Dimensions (2D) and concentrates on small to medium size graphs; the objective of this work is to handle large graphs (hundreds and thousands of nodes). One use of this algorithm is for visualization of Object-Oriented (OO) systems, such as inheritance graphs, which in turn helps in understanding and maintaining the corresponding OO programs. In general, this algorithm can be used to display in a readable form large Directed Acylic Graphs (DAGs).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

Three-Dimensional Layout Algorithm for Directed Acylic Graphs

      Until now, most of the work done on the subject concerns
visualization of graphs in 2 Dimensions (2D) and concentrates on
small to medium size graphs; the objective of this work is to handle
large graphs (hundreds and thousands of nodes).  One use of this
algorithm is for visualization of Object-Oriented (OO) systems, such
as inheritance graphs, which in turn helps in understanding and
maintaining the corresponding OO programs.  In general, this
algorithm can be used  to display in a readable form large Directed
Acylic Graphs (DAGs).

The Algorithm

      Although the algorithm works for any directed acylic graph, OO
design is used as an example here.  It shows a possible use of the
algorithm.  In the sequel, classes are referred to as the nodes of
the graphs and edges as the inheritance relation which induces the
edges of the graph: an edge from node n1 to node n2 indicates that
node n2 inherits from node n1.

An overview of the algorithm is as follows:
  o  Initialization - create a forest that consists of two DAGs:
     1.  DAG1: consists of (an invisible root and) all of the
          "isolated" nodes.  (In an OO example, isolated nodes are
          "base classes" which no other class inherits from.)
     2.  DAG2: consists of (an invisible root and) all of the
          remaining nodes.
  o  Placement:
     1.  Optimize the layout of DAG1 and DAG2 so that siblings are
          assigned to a plane and are located below their parents.
     2.  Shuffle group of sibling nodes, or their parents, so that
          classes that have multiple parents do not form long edges.
     3.  Within each group, move nodes to the side of the
          additional parent(s).

A more detailed description is as follows:
  o  Initialization:
     1.  Create a forest that consists of two DAGs:
         a.  DAG1: consists of an invisible root and all of the
              "isolated" nodes.
         b.  DAG2: consists of an invisible root and all of the
              remaining nodes.
  o  Placement:
     1.  Connect all the isolated nodes to the root of DAG1.
     2.  Assign levels to all graph nodes.  Each level is assigned
          to a 2-D hyperplane in 3-D.  All hyperplanes are parallel
          to each other.
     3.  Add N - 1 virtual nodes, where N is the graph depth, and
          link them the root of DAG2.
         a.  Connect the virtual nodes, as a list, and connect
              only the first node in this list to the root of DAG2.
     4.  Loop over all levels.
         a.  For level i loop over all nodes:
             1) If a node has no ancestors, connect it to the
                 virtual node from level i-1.
     5.  Cal...