Storage of a graph

Details Storage of a graph Storage of a graph

1996-12-17

1999-03-02

Black, Thomas G.

Data processing: database and file management or data structures

Database design

Data structure types

345333, G06F 1730

Patent

active

058784071

DESCRIPTION:

BRIEF SUMMARY
The invention relates to a method for storing a graph in a computer memory, a method of graphical representation of a graph, and a computer system for storing a graph.
Graphs show relationships between objects. They are often used to model or represent a real process, sequence or structure. Graphs are used in particular to represent networks, such as transport or communications networks.
The state of the art not only includes the use of graphs for the representation and modelling of a real system comprising various objects which are separated from each other, at least logically; it also includes the use of graphs for analytical purposes. Fundamental examples of this are to be found in "Foundations of Computer Science, Computer Science Press, Alfred V. Aho, Jeffrey D. Ullman" and in "Introduction to Algorithms, The MIT Press, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest".
The practical application of graphs is, however, problematic, because the state of the art contains no practicable method of mapping a graph in such a way that the topography of the graph can be automatically processed by a computer. Likewise, the problem of clearly defined representation--especially of a complex, three-dimensional graph--on the limited flat area of a computer screen also remains unsolved.
The object of the invention is therefore to create a method of mapping a graph into a computer memory, as well as a computer system to execute the said method.
The objects are achieved with the characteristics of claims 1 or 9 and 11 respectively.
The method in accordance with the invention permits a graph to be represented by means of an array of indices. These indices can be stored in the computer memory so that the graph can be analysed by the computer. For example, the question as to whether there is a relationship between a first node--in the remaining vertex--and a second vertex can be answered by a simple comparison of the indices in the memory. Likewise, the vertices lying on a path from a first vertex to a second vertex in the graph can be determined by such comparisons. The question of a shortest path between two vertices, too, can be answered by comparison in this way. The method in accordance with the invention has the further advantage that the number of operations to be performed to determine the arrays describing the graph to be stored in the memory only increases linearly with the number of vertices and the edges of the graph.
In addition to the areas cited at the beginning, fields of application of the invention include control flow analysis, data flow analysis, modelling of business processes and of hardware and software configurations, and network modelling.
The invention offers particular advantages for computer graphics. If the arrays located by application of the method are interpreted as coordinates of the vertices in a coordinates system, they produce an ordered representation of the graph in several layered planar sub-graphs.
An embodiment of the invention is shown in the drawing, and is described in more detail in the following.
FIG. 1 shows a graph G;
FIG. 2A-O show the determining of a first map of the graph G;
FIG. 3A-B show the determining of a second map of the graph G;
FIG. 4A-B show the determining of a third map of the graph G;
FIG. 5 shows the located arrays of the map of graph G;
FIG. 6A-B show another graph G' and the associated arrays of indices;
FIG. 7A-B show another graph G" and the associated arrays of indices.
For depth-first searching in the graph G, the following algorithm is to be applied in this embodiment of the invention:
Initially the global variables of the algorithm are defined: G, if the depth-first search occurs in forward direction; otherwise the initial value is equal to 0. the stack are all vertices on which the depth-first search can be started, the so-called sources of graph G, if the depth-first search occurs in forward direction; otherwise the initial contents are the so-called sinks of graph G. called the current vertex.
For each vertex the following local variable

REFERENCES:
patent: 5163016 (1992-11-01), Har'El et al.
patent: 5257363 (1993-10-01), Shapiro et al.
patent: 5553206 (1996-09-01), Meshkat
patent: 5555270 (1996-09-01), Sun et al.
patent: 5630051 (1997-05-01), Sun et al.
patent: 5649165 (1997-07-01), Jain et al.

Affiliated with

Also associated with

Rating

Storage of a graph does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Storage of a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Storage of a graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-433414