Browse Prior Art Database

Storage Mapping of Directed Graphs

IP.com Disclosure Number: IPCOM000079010D
Original Publication Date: 1973-Apr-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 75K

Publishing Venue

IBM

Related People

Koch, K: AUTHOR

Abstract

A method is described for economically mapping directed graphs as matrices into a computer storage. The proposed matrix is explained by means of a precedence graph, such as the sample graph shown in Fig. 1, defining the processes which can be computed parallelly and those which have to be computed sequentially. In the sample graph the processes are denoted by letters, whereas the directed arcs are marked by arabic numbers.

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

Page 1 of 3

Storage Mapping of Directed Graphs

A method is described for economically mapping directed graphs as matrices into a computer storage. The proposed matrix is explained by means of a precedence graph, such as the sample graph shown in Fig. 1, defining the processes which can be computed parallelly and those which have to be computed sequentially. In the sample graph the processes are denoted by letters, whereas the directed arcs are marked by arabic numbers.

The proposed matrix comprises four colurns and a number of liars, one line describing a directed arc, its predecessor node, its successor node, and the status of its successor node. The entries of the matrix can be positioned at any matrix line. The table below shows the matrix representation of the precedence graph in Fig. 1, with the arc numbers indicating the matrix line in which the directed arcs are described among others.

In any directed graph more than one directed arc may point to a given node (join node). Because in the proposed matrix a given join node is allowed to occur as successor node but once, only one directed arc may point directly to a join node. For the matrix representation of directed graphs, an arbitrary directed arc is chosen which points directly to its successor (join) node. The other directed arcs must point indirectly to that join node.

In the matrix shown in the table,tthe leftmost column contains a line identification number. A Predecessor column includes pointers which refer to the matrix line describing the predecessor node of a given directed arc. The predecessor node of the root of the sample graph is indicated by a null pointer designated as "-". The Direct Indicator column specifies...