US 5,878,407 AGrant
Storage of a Graph
Issue Date:1999-03-02
•14 Claims
•22 Drawing Sheets
Abstract
The invention relates to a method to store a graph G in a memory of a computer system by a number of depth-first and breadth-first searches in different directions. The entire topological information contained in the graph is mapped into the memory. At the same time redundant information is eliminated.
Metadata
Assignee
- International Business Machines Corporation
Inventor
- Enis Olgac
Application Information
Application Number:US 7508875
Filing Date:1996-12-17
Priority Date:1995-04-18
Art Unit:271
Classifications
IPC:
G06F 1730
Field of Search:
7073953643713451;2;3;4;5;6;7;8;9;10;100;200500;183.0857827.1;67.1326;333
Patent Drawings (22 sheets)
Description
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:
Pre-clock; the pre-clock initial value is equal to 0.
Post-clock; the post-clock initial value is the number of vertices of graph G, if the depth-first search occurs in forward direction; otherwise the initial value is equal to 0.
A stack of the vertices currently being processed; the initial contents of 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.
A data field for storing a vertex currently being processed, hereafter called the current vertex.
For each vertex the following local variables are defined:
A list of the successors of the vertex in question, with successors being designated as all those vertices directly related to the vertex in question. In the list of successors there is a pointer. Prior to execution of the depth-first search the pointer is located before the first element in the successor list.
A data field for storing the variable "pre-order"; the pre-order value is initially equal to 0.
A field for storing "post-order"; the post-order value is initially equal to 0.
The depth-first search algorithm involves the following steps:
1. If the stack is empty:
a) Go to step 8
2. If the stack is not empty:
a) Select vertex (u) at start of stack as current vertex
b) Go to step 3
3. If the data field of the pre-order number of the current vertex (u) is not equal to 0:
a) Go to step 5
4. If the data field of the pre-order number of the current vertex (u) is equal to 0:
a) Increment pre-clock by 1
b) Copy content of pre-clock into data field of pre-order number of current vertex (u)
c) Go to step 5
5. If the pointer in the successor list of the current vertex (u) is at the end of the successor list:
a) Copy content of post-clock into data field of post-order number of vertex (u)
b) Decrement post-clock by 1
c) Remove vertex (u) from stack
d) Go to step 1
6. If there is a vertex (v) to the right of the pointer in the successor list of the current vertex (u) and the pre-order number of the vertex (v) is equal to 0:
a) Add vertex (v) to start of stack
b) Move pointer one position to right
c) Go to step 1
7. If there is a vertex (v) to the right of the pointer in the successor list of the current vertex (u) and the pre-order number of the vertex (v) is not equal to 0:
a) Move pointer one position to right
b) Go to step 5
8. End depth-first search.
On termination of the depth-first search the data structures defined at the beginning contain the following results:
The global variables:
The pre-clock contains the number of vertices in the graph G.
The post-clock is equal to 0, if the depth-first search occurs in forward direction; otherwise equal to the number of vertices "n" of graph G.
The stack is empty.
The local variables in each vertex:
The pointer in the successor list is at the end of the list.
The pre-order number includes the pre-clock value at the point in time when the vertex in question was discovered.
The post-order number includes the post-clock value at the point in time when the vertex in question was removed from the stack or, in other words, at the point in time when processing of the vertex in question was completed.
For breadth-first searching, the following algorithm is applied in this example:
Definition of data structures used:
Global variable:
Proc-clock; the proc-clock value is initially equal to 0.
A queue of the vertices currently being processed; "queue" initially contains all vertices on which the breadth-first search can be started. These are the sinks of graph G; if the breadth-first search occurs in forward direction these are the sources of graph G.
A data field for storing the vertex currently being processed; that is, the current vertex.
Local variable for each vertex:
A successor list with a pointer, which is initially positioned to the left of the first vertex in the successor list.
A data field for storing the processing order; the processing order value is initially equal to 0.
A data field for storing the processing state; the processing state value initially has a first logical value --hereafter called "white".
The breadth-first search involves the following steps:
1. Change the processing state of all vertices in the queue to a second logical value--hereafter called "black".
2. If the queue is empty:
a) Go to step 7
3. If the queue is not empty:
a) Select vertex (u) at start of queue as current vertex
b) Increment proc-clock by 1
b) Copy content of proc-clock into data field of processing order variable of current vertex (u)
c) Go to step 4
4. If the pointer in the successor list of the current vertex (u) is at the end of the successor list:
a) Remove vertex (u) from queue
b) Go to step 2
5. If there is a vertex (v) to the right of the pointer in the successor list of the current vertex (u) and the processing state of the vertex (v) is white:
a) Add vertex (v) to end of queue
b) Change processing state of vertex (v) to black
c) Move pointer one position to right
d) Go to step 4
6. If there is a vertex (v) to the right of the pointer in the successor list of the current vertex (u) and the processing state of the vertex (v) is black:
a) Move pointer one position to right
b) Go to step 4
7. End breadth-first search.
On termination of the breadth-first search the data structures defined at the beginning contain the following results:
The global variables:
The proc-clock contains the number of vertices in the graph G.
The queue is empty.
The local variable in each vertex:
The pointer in the successor list is at the end of the list.
The processing order includes the proc-clock value at the point in time when the vertex to which the processing order belongs was selected for processing.
The logical processing state is black.
Apart from the algorithms for depth-first and breadth-first searching described above, the state of the art also reveals a multiplicity of equivalent algorithms, which are likewise suitable for use in a method in accordance with the invention.
FIG. 1 shows a graph G, to which an embodiment of the method in accordance with the invention is to be applied. Graph G consists of vertices A, B, C, D, E, F, G, K, L, M, N, P, R, S and the associated edges, as shown in FIG. 1 at the top.
Graph G in FIG. 1 is to be represented by indices stored in a memory, e.g. of a computer, by means of the method in accordance with the invention. To this end, the graph G is subjected to a first mapping, on the basis of a total of five depth-first searches and one breadth-first search:
Depth-first search number 1: Graph G is subjected to a depth-first search in forward direction, wherein the successors of the vertices can be arranged consecutively, in any order; in the example, in alphabetical order. The result of the first depth-first search is a topological ordering of graph G.
FIG. 2a shows the initial values of the data structures used. The pre-clock initial value is equal to 0; the post-clock initial value is equal to 15. There is initially no current vertex. The stack contains only source A of graph G. The first column in FIG. 2a shows the vertices of graph G; the second column the successors belonging to the vertex in question in graph G; the third column the pre-order number of each vertex; and the fourth column the post-order number of each vertex.
FIG. 2b shows the individual steps of the depth-first search algorithm worked through in depth-first search 1. FIG. 2b shows only those steps of the algorithm which are actually performed, and the corresponding data thereby modified. The numbering of the steps in FIG. 2b corresponds to the numbering in the algorithm described above; as indeed a uniform numbering scheme is observed throughout.
FIG. 2c shows the result of depth-first search 1. The pointers in the successor list, as also in FIG. 2a, are symbolised by a "+". The pointers of all vertices are positioned at the extreme right margin of the successor list after completion of depth-first search 1.
FIG. 2d shows the data structures used for the subsequent breadth-first search in graph G in forward direction. The proc-clock is equal to 0; a current vertex is not yet defined, since processing has not yet begun; the queue contains source A of graph G. The first column of FIG. 2d contains the list of vertices; the second column the list of successors of each vertex; the third column the processing order; the fourth column the logical processing state "State", which is initially "white".
Execution of the breadth-first search is based on the result of the depth-first search 1, because the successor lists are sorted according to the post-order found in depth-first search 1. This means that the successor list of each vertex is sorted according to the post-order found in depth-first search 1, in descending order. The vertex in a successor list which has the highest post-order number on completion of the first depth-first search is placed accordingly at the start of the successor list. FIG. 2e shows the execution of the breadth-first search based on the algorithm described above, wherein once again the numbering of the individual steps in FIG. 2e corresponds to the steps in the breadth-first search algorithm described.
FIG. 2f shows the data structure of FIG. 2d on completion of the breadth-first search.
Thereafter, based on the result of the breadth-first search, another depth-first search is performed in graph G. Depth-first search 2 is performed in the opposite direction, i.e. in backward direction. In comparison with depth-first search 1, this requires the successor lists to be replaced by corresponding lists of predecessors for each vertex. The second column in FIG. 2g accordingly shows the predecessors of each vertex in graph G. For example, vertex F has predecessors B, G, N, as can also be seen in FIG. 1. The predecessor list in FIG. 2g is sorted on the basis of the result of the breadth-first search. Each predecessor list is sorted according to the ascending processing order in FIG. 2f, i.e. the vertex in a predecessor list with the lowest processing order is positioned at the start of the predecessor list, followed by the remaining vertices of the list, in ascending order.
FIG. 2h shows the execution of the depth-first search in backward direction in graph G, wherein once again the numbering of the steps in FIG. 2h corresponds to the steps of the depth-first search algorithm previously described. The difference between this and the depth-first search algorithm previously described is only that--in accordance with the change of direction in the second depth-first search--the successors have been replaced by the predecessors of a vertex.
FIG. 2i shows the data structure of FIG. 2g on completion of the second depth-first search.
Based on the result of the second depth-first search, a third depth-first search is then performed in forward direction, wherein the successors in the successor lists of each vertex are sorted in descending pre-order; the basis is the pre-order found in the second depth-first search (cf. column 3 in FIG. 2i). FIG. 2k shows the data structure of FIG. 2j on completion of the third depth-first search in forward direction. Based on the result of the third depth-first search, a fourth depth-first search is then performed in backward direction, wherein the predecessors of the vertices are sorted in descending post-order prior to execution of the depth-first search (FIG. 2i). Again, the bases for the search are the post-order numbers found in the preceding depth-first search (cf. column 4 in FIG. 2k).The result of the fourth depth-first search is shown in FIG. 2m.
Based on the fourth depth-first search in backward direction, a fifth depth-first search is then performed in forward direction. Again, prior to execution of the fifth search the successor lists of the vertices are sorted in ascending post-order (FIG. 2n); the bases are the post-order numbers found in the fourth depth-first search (cf. column 4 in FIG. 2m). FIG. 2o shows the result of the fifth depth-first search in forward direction. The post-order numbers determined in the fifth depth-first search (cf. column 4 in FIG. 2o) are the map of graph G. This map is designated hereafter as the base index "BsIndex". Vertex A, for example, has been assigned index 1 as a result of the first mapping of graph G; vertex B index 4; vertex C index 2; . . . in accordance with column 4, "BsIndex", in FIG. 2o.
Based on the BsIndex found, two more maps of graph G can be located by means of one further depth-first search for each.
To locate a second map--hereafter designated the forward index "FwdIndex"--the graph G is subjected to a further depth-first search in forward direction. The successors in the successor list of each vertex are sorted according to the BsIndex prior to execution of the sixth depth-first search, in ascending order. The successor in a successor list with the lowest BsIndex is thus positioned at the start of the successor list. This produces the data structure shown in FIG. 3a. Based on this data structure, the sixth depth-first search is performed in forward direction according to the algorithm set out above. The result is the data structure in FIG. 3b. The post-order numbers of the vertices represent the searched-for forward index "FwdIndex". For example, the FwdIndex of vertex A is equal to 1; that of B equal to 9; . . . (in accordance with column 4 in FIG. 3b).
By means of a seventh depth-first search in backward direction a third map of graph G is determined: the so-called backward index "BwdIndex". The predecessors in the predecessor list of each vertex are first sorted in descending order according to their respective base index "BsIndex" (cf. column 4 in FIG. 2o). The vertex in a predecessor list with the highest base index is thus positioned at the start of the list. This sorting of predecessors produces the sort as shown in column 2 of FIG. 4a. The execution of the seventh depth-first search in backward direction based on the algorithm set out above produces the result shown in FIG. 4b. The post-order number of each vertex indicates its backward index "BwdIndex" (cf. column 4 in FIG. 4b).
The results of the above three mapping operations of graph G are assembled in FIG. 5. The first column in FIG. 5 gives the base index "BsIndex"; the third column the forward index "FwdIndex"; and the fourth column the backward index "BwdIndex" of the vertices of the graph G. The vertices of graph G are listed in column 2 of FIG. 5. For each of the listed vertices this results in an index array comprising base index, forward index and backward index. For example, array (1, 1, 1) is allocated to vertex A; array (7, 13, 13) to vertex E.
FIG. 5 shows that, for graph G in FIG. 1, the forward and backward index are equal for each vertex. The unambiguous consequence of this is that graph G is a planar graph. FIG. 6b shows another non-redundant planar graph G'. Graph G' is redundant in that it contains no edges representing "shortcuts". A "shortcut" in this context would be an edge between vertex 11 and vertex 5. An edge of this kind is, however, redundant, because the information that a relationship exists between vertex 11 and vertex 5 is already included in graph G' without that edge. This information is given by the indirect relationship between those vertices by way of vertex 1 in graph G'. If this redundant edge was present in graph G', it would be eliminated by a mapping operation in accordance with the invention.
FIG. 6a shows the results of the mapping operations in accordance with FIG. 5. Since, again, the forward and backward index of graph G' in FIG. 6b are equal, graph G' is consequently also planar.
FIG. 7b shows a graph G"; FIG. 7a the associated result of mapping in accordance with FIG. 5. In this case the forward and backward indices are different. The unambiguous consequence of this is that graph G" in FIG. 7b is a non-planar graph. This means that graph G" cannot be represented in one plane without the intersection of two of its edges.
This method of mapping a graph G into a storage device--in particular a computer system memory--thus merely requires that the vertices, the edges, the sources and the sinks (cf. FIG. 1 at the top) be entered in the computer. The method of mapping graph G is then performed according to the algorithms set out above by means of electronic data processing, resulting in the storing in the computer memory of a number array for each vertex of the graph. The totality of the number arrays located by this means includes the entire topological information which is contained in a graph G. With the aid of the map of a graph G as located, that is to say with the number arrays for each of its vertices, the following questions can, for example, be answered directly:
1. It is a linear graph if BsIndex=FwdIndex=BwdIndex.
2. It is a planar graph if BsIndex is not equal to FwdIndex=BwdIndex.
3. It is a non-planar graph if all three indices are unequal for a vertex of the graph.
4. There is a relationship between any first vertex A and any second vertex B of graph G when
a) BsIndex of vertex A<BsIndex of vertex B
b) FwdIndex of vertex A<FwdIndex of vertex B
c) BwdIndex of vertex A<BwdIndex of vertex B.
If the first depth-first search is performed not in forward direction but in backward direction, the size ratios are reversed accordingly, i.e. "<" becomes ">".
5. In the case of a planar graph, conditions b) and c) are equal; in the case of a linear graph all three conditions are equal, so that it merely remains to check whether the BsIndex of vertex A is lower than the BsIndex of vertex B. The answer to the question of whether a relationship exists between vertex A and vertex B in graph G requires only a low level of computing power of the computer system. To answer the question, the three mapped indices of vertex A and of vertex B must merely be compared with each other. A further advantage of the method in accordance with the invention is that the established result that a relationship exists between vertex A and vertex B is not subject to uncertainty, as would be the case according to the current state of the art.
6. The sequences of relationships, symbolised by edges in graph G, result in so-called paths. Based on the mapping of graph G, all vertices belonging to a path from any vertex A to any vertex B can be determined. For this, all vertices having a relationship both with vertex A and with vertex B must be determined.
7. By means of the method in accordance with the invention, a shortest path Pmin from a vertex A to a vertex B can be located, if conditions 4a-b are applied recursively:
a) For each path P from A to B only those vertices Vi come into question of which the BsIndex is higher than the BsIndex of A but lower than the BsIndex of B.
b) Establish, for each of these vertices Vi in ascending order of base indices, the following:
aa) Is there a relationship between vertex Vi and vertex B? If not, vertex Vi cannot belong to a path from A to B. The next vertex Vi+1 with the next highest BsIndex is then checked.
bb) If condition aa) is met: Is there a relationship between a vertex Vj, which belongs to a path Pj, and the current vertex Vi being checked? As long as no such vertex Vj has yet been found, this is vertex A. If that is the case, the vertex currently being checked Vi likewise belongs to the path Pj. Since vertex Vj is the vertex in path Pj with the highest BsIndex, it is also ensured that the vertex currently being checked Vi immediately follows vertex Vj in path Pj. The vertex currently being checked Vi, which belongs to the path Pj, then in a further recursion becomes vertex Vj in the execution of step b)--in particular bb)--for this vertex.
If there is no relationship between vertex Vj in path Pj and vertex Vi, with Vj and Vi having minimal differences in their BsIndex, a check must be made as to whether there are other paths Pj+1 to which the vertex currently being checked Vi belongs. To do this, a check must be made for the last vertex V found in each of the other paths P, that is to say for the respective vertices V with the highest BsIndex, as to whether there is a relationship between the said vertex V and the vertex currently being checked Vi. If that is the case, vertex Vi consequently immediately follows the last located vertex V in the relevant path P.
c) Determination of the length of all located paths, where appropriate taking account of numeric information relating to the relationships. If graph G represents a computer network, for example, then the numeric information relating to the individual relationship between two vertices can give information on the line length, for example.
d) Determine from the path lengths determined under c) the path of the shortest length Pmin.
The storage in a computer system memory created by the mapping in accordance with the invention can be advantageously used for the graphical representation of graph G, for example on a monitor of the computer system. If the individual arrays of indices are interpreted as coordinates of the vertex in question in a coordinates system, the planar sub-graphs in graph G are represented in one plane. The resulting different planes are interlinked on specific vertices. These vertices can be represented in tubular form, for example.
This ensures a clear, concise and memory-saving form of representation.
The method in accordance with the invention is also not restricted to acyclically directional graphs. It can also be applied to non-directional graphs, if a direction is simulated in a non-directional graph by means which are in themselves already known.
A further advantage of the method in accordance with the invention results from the fact that the located map of graph G has no redundancy whatever in the memory. This can, however, also be seen as disadvantageous--especially in determining a shortest path. If, for example, there were a relationship between vertices A and L in the graph in FIG. 1, that relationship would no longer be expressed in the established arrays of indices. If the information that there is a direct relationship between vertices A and L is of significance, and the information contained in the map indicating that such a relationship exists by way of vertex C is not sufficient, the following remedial action can be taken:
On completion of a first storing of the graph in accordance with the invention, the edges eliminated in the process of mapping are identified. These are the redundant edges. Notional nodes are inserted in the edges eliminated as a result of the mapping. After insertion of the notional nodes into the graph, the method in accordance with the invention is performed for a second time, with the redundant edges being retained.
The method in accordance with the invention can be integrated into an operating system as a library program. When a storage medium, such as a diskette or a CD-ROM, is inserted into the computer system reading device, a computer system is created which is able to execute the method in accordance with the invention.
Claims
I claim:
1. Method for storage of a graph of vertices and associated edges connecting pairs of said vertices in a memory of a computer system as a table of the vertices and a group of indexes ordering the vertices, characterized by the steps of: a) representing the graph as a list of the vertices and a list of successors of each vertex; b) performing a depth first search in graph G in a first direction; c) performing a breadth-first search in graph G in the first direction; and d) performing four further depth-first searches in graph G alternately in a second direction and the first direction to produce a first map (BsIndex), wherein the breadth-first and depth-first searches in steps c) and d) are each based on the result of the preceding search.
2. Method in accordance with claim 1, characterized in that prior to the searches in steps c) and d) the lists of successors of each vertex of graph G are sorted according to the result of the preceding search.
3. Method in accordance with claim 2, characterized in that the graph G contains a shortcut between two of its vertices, and a vertex is introduced into the edge of graph G corresponding to the shortcut.
4. Method in accordance with claim 1, characterized by the following steps: a) performing a depth-first search in the first direction in graph G based on the first map (BsIndex) for creation of a second map (FwdIndex); b) performing a depth-first search in the second direction in graph G based on the first map (BsIndex) for creation of a third map (BwdIndex).
6. Method to ascertain whether in a graph G a relationship exists between a first vertex A and a second vertex B, wherein graph G is stored in a memory by means of a first, second and third mapping in accordance with claim 4, characterized in that the indices X (BsIndex) of the first map, Y (FwdIndex) of the second map, and Z (BwdIndex) of the third map of vertices A and B are each read from the memory, and that a check is made as to whether the indices X, Y, Z of vertices A and B respectively have a pre-determined size ratio to each other.
7. Method to ascertain a shortest path Pmin from a vertex A to a vertex B of a graph G, characterized in that the method in accordance with the invention is applied recursively in accordance with claim 6.
8. Method to ascertain all vertices belonging to a path from a vertex A to a vertex B in graph G, wherein graph G is stored in a memory by means of a first, second and third mapping in accordance with claim 4, characterized in that the indices X (BsIndex) of the first map, Y (FwdIndex) of the second map, and Z (BwdIndex) of the third map of vertices A and B are each read from the memory, and that all vertices of graph G are ascertained of which the indices lie between the indices of vertices A and B.
9. Method for graphically representing a graph G, characterized in that the maps of graph G located by means of a method in accordance with claim 1 serve to determine the coordinates of the vertices of graph G.
10. Computer system with means of executing a method in accordance with claim 1.
12. Method for storing a graph G in a computer memory, characterized in that, for each vertex Vi of graph G, an array of indices is stored in the memory and the array of indices of a vertex Vj stands in a pre-determined ratio to the corresponding array of indices of a vertex Vk when a relationship exists in graph G between vertices Vj and Vk.
13. A method of storing a graph of vertices and associated edges connecting pairs of said vertices in a memory of a computer system, comprising the steps of: representing the graph as a list of the vertices and a group of successor/predecessor lists of the vertices, each successor/predecessor list being associated with one of the vertices and representing the edges of the graph connecting the associated vertex in a first direction to the succeeding/preceding vertices listed in the associated successor/predecessor lists; topologically ordering the vertices by performing a sequence of searches in the graph, each successive search in the graph being performed using an ordering of the vertices in each of the successor/predecessor lists produced in accordance with an ordering of the vertices generated by the next preceding search; forming a first map of the graph containing a base index for each vertex of the graph from the ordering of vertices produced by the sequence of searches; forming a second map of the graph containing a forward index for each vertex of the graph by performing a depth-first search in the graph in forward direction with the successor/predecessor lists of vertices each being sorted in accordance with the base indexes of the vertices in ascending order; forming a third map of the graph containing a backward index for each vertex of the graph by performing a depth-first search in the graph in backward direction with the successor/predecessor lists of vertices each being sorted in accordance with the base indexes of the vertices in descending order; forcing a table of the vertices containing the base index, forward index and backward index for each of the vertices; and storing the formed table as a stored representation of the graph.
14. A method as defined in claim 13 wherein the sequence of successive searches in the topologically ordering step comprises the steps of performing a first depth-first search in the first direction, followed by a breadth-first search in the first direction, followed by a second depth-first search in a second direction, followed by a third depth-first search in the first direction, followed by a fourth depth-first search in the second direction, followed by a fifth depth-first search in the first direction.