next up previous
Next: Group based fields Up: Related Work Previous: Data Structures

Graph Types

The Graph Types approach [12], retains a tree based backbone structure, but augments it with a set of routing directions that can point to a particular node, relative to it. Thus a simple linked list can be converted into a cyclic doubly-linked list. These additional pointers are defined using a routing expression which describes the route taken to reach the destination node. It has the disadvantage that the structure must have a tree backbone, and it allows structures where the routing directions depend on the run-time instance of the structure. This makes static analysis more difficult as knowledge not available at compile time would be required to fully analyse such structures.



Timothy Lewis
11/12/1997