Browse Prior Art Database

PRUNING DIRECTED GRAPHS

IP.com Disclosure Number: IPCOM000006437D
Original Publication Date: 1992-May-01
Included in the Prior Art Database: 2002-Jan-03
Document File: 3 page(s) / 145K

Publishing Venue

Motorola

Related People

Yves Mathys: AUTHOR

Abstract

The large size of modem designs results in increased complexity of hierarchical design data. Since the design data is strongly coupled designers should be able to tra- verse data relations for querying information about objects or configuration of objects.

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

Page 1 of 3

MOTOROLA INC. Technical Developments Volume 15 May 1992

0 M

PRUNING DIRECTED GRAPHS

by Yves Mathys

INTRODUCTION

  The large size of modem designs results in increased complexity of hierarchical design data. Since the design data is strongly coupled designers should be able to tra- verse data relations for querying information about objects or configuration of objects.

  A graphical browser supports the designer by giv- ing him a visual representation of the data dependencies and by facilitating navigation in the design database. Pro- viding a better access control of design data and an under- standing of the da& dependencies strongly reduce design cycle time by avoiding error prone modifications and unnecessary data generation.

  The large size of the databases makes the task of graphically representing the data diicult. The graph is rapidly overcrowded and thus unreadable. Techniques should be developed to reduce the graph complexity.

  The existing browsers" have not been designed to address large collections of data, made of multiple thou- sand objects. These tools give little assistance to the designer for exploring large design databases.

We present a technique to prune the complexity of a directed graph by isolating commonly used nodes into a dedicated table. We have developed a display algorithm to optimize nodes visibility.

DESCRIPTION

We simplitied the directed graph by placing the nodes for utilities, such as design library elements, into a dedi-

cated column, located to the side of the main graphic window, that we call library table (see Figure 1).

  Usually the visible slots in the library table are outnumbered by the large population of commonly used libraries. The library table can be vertically scrolled independently of the main window. The library elements do not have descendants s&e they represent the lowest level of the data hierarchy. !'We have developed a draw- ing algorithm to optimize the display of the library ele- ments. The display algorithm is composed oftwo modes; scrolling mode and active mode.

  The tirst mode permits to search for a speci& node's name for which the user wants to display its ancestors- answering the question who is wing fhis library element.7 The second mode is enabled when a node in the graph window requests the display of its descendants, includ- ing library elements. Some library elements receive a request to become visible. Since the library table has only a limited number of visible slots-which depend on the size of the entire window-we use a least used strat- egy to assign elements to Gisible slots. A time stamp is associated with an element/slot pair (in a similar fashion than...