Browse Prior Art Database

Mapping Directed Graph to a Tree

IP.com Disclosure Number: IPCOM000119069D
Original Publication Date: 1997-Nov-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 2 page(s) / 52K

Publishing Venue

IBM

Related People

Terekhov, A: AUTHOR

Abstract

It is required to provide Graphical User Interface (GUI) to the resource configuration views which are, by their nature, a set of directed graphs. The present approach is based on mapping a directed graph to a hierarchical tree which is a common U1 presentation structure. The problem is that, after the mapping, the tree contains some multiple instances of nodes which represent the same node in a graph. Each instance of such a node in a tree is actually the representation of a link to the corresponding node in a graph. But, a graph is not a static structure - it changes dynamically. Links and nodes could appear and disappear. So, a special identification mechanism for the tree nodes is required, which allows the maintenance of a tree without the need to rebuild it from scratch after each change in the directed graph.

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

Mapping Directed Graph to a Tree

      It is required to provide Graphical User Interface (GUI) to
the resource configuration views which are, by their nature, a set of
directed graphs.  The present approach is based on mapping a directed
graph to a hierarchical tree which is a common U1 presentation
structure.  The problem is that, after the mapping, the tree contains
some multiple instances of nodes which represent the same node in a
graph.  Each instance of such a node in a tree is actually the
representation of a link to the corresponding node in a graph.  But,
a graph is not a static structure - it changes dynamically.  Links
and nodes could appear and disappear.  So, a special identification
mechanism for the tree nodes is required, which allows the
maintenance of a tree without the need to rebuild it from scratch
after each change  in the directed graph.

      The approach is based on a special internal prefix to the
identifier of a tree node.  This prefix represents the information
about the upper path to the node.  The advantage of this approach is
a reduced cost of maintaining the tree.  Therefore, in this
distributed application, it is not necessary to rebuild the tree and
are able to refresh it and show the recent changes in the resource
configuration via a reduced set of requests to the server part of the
application.

Example: Assuming the following directed graph:
  ROOT"
  +--> A"-->--+
  +--> B"-->+
              C"

The pre...