GraphPack Implementation Design and Details
Introduction
GraphPack contains the data structure for storing a graph of
connected vertices and edges. Vertices are of type Vertex class, and
edges have type Edge class. All the vertices are linked together in a
doubly-linked list, which is held by the Graph class in variable
vlist. Similarly, the edges are chained together and held by variable
elist. There can be at most one edge between any two vertices.
The graph data structure is similar to an adjacency list as
each vertex contains a list of attached edges. However the list of
attached edges doesn't contain the real Edge objects since then there
would be two copies of each Edge, and deleting an edge from the graph
would require an O(number edges) search to find both copies of the
Edge. Instead, we created an EdgeAlias class which points to the real
Edge object. Every vertex has a list of EdgeAliases, each of which
point to the real Edge. The Edge has pointers to both Vertex objects
as well as both EdgeAlias objects, making the deletion of an edge
efficient.
For example, the graph:
has this data structure:
When a user of GraphPack wishes to see a vertex's attached
edges, we pass them the list of EdgeAliases. In order to make the
graph data structure transparent to the user, we created an EdgeList
interface which both EdgeAlias and Edge implement. Thus the user does
not have to know about EdgeAliases in order to use any list of Edges.
If the user needs an operation which is specific to Edge, not
EdgeList, they can call EdgeList.getEdge() which returns a real Edge
object.
Highlighting
For Zarbiff we needed to implement highlighting, ie the
creation of a special subset of vertices and edges within the graph.
We considered two ways of implementing highlighted vertices (same
for edges)
- The graph has two lists: one of highlighted vertices, and one of
plain vertices. However, if we implemented this there would be
no easy way of handing users a complete list of ALL vertices, without
copying and concatenating the lists together.
- Allow each Vertex object to be in two lists at the same time: the
list of all graph vertices, and the list of highlighted vertices.
Similarly for edges.
We implemented (2) and created a Qnode class to implement a
quadrupally-linked object. Vertex, Edge and EdgeAlias all extend
Qnode.
Directed Graphs
DirGraph extends Graph and implements the same GraphDrawingInterface.
DirGraph contains DirVertex and DirEdge, which extend Vertex and
Edge. The data structure is essentially the same as Graph, however
Edge(v1, v2) refers semantically to an edge from v1 to v2, instead of
just an edge between the two vertices. DirVertex contains two lists
of attached edges instead of one: a list of outgoing edges and a list
of incoming edges. The user of GraphPack must know this, and must
explicitly examine both lists in order to get all attached edges. The
edge(v1,v2) will have two edge aliases: one in v1's outgoing edge
list, and one in v2's incoming edge list. A directed graph can have
two edges between a pair of vertices: one edge in each direction.
Drawing graphs
Drawing a directed edge is difficult since if there are two
edges between a pair of vertices then the edge must bow outward.
Since it would be inefficient to recalculate the arc for a bowed out
edge each time the edge is drawn, the information needed to draw the
edge is stored. We wanted to separate the graph data structure from
the details of drawing the graph as much as possible, so all the
classes to draw graphs, vertices, and edges are in GraphDrawingPack.
DirEdge contains a variable of type EdgeDrawingInterface (from
GraphDrawingPack) and currently instatiates it to DirEdgeDrawing.
Whenever one of DirEdge's vertices is moved, or another edge is added
between its two vertices, the information to draw the edge must be
recomputed, thus an update() function is called.
To be consistent, we did the same for vertices. Each vertex
contains a variable of type VertexDrawingInterface, and instantiates
it, currently to VertexDrawing. No information needs to be
updated however, so drawing vertices is easier than edges.
See GraphDrawingPack README for futher details on drawing.
Object Model
Below is the object model for the GraphPack package. Classes are
represented as boxes, circle edges represent "implements", arrow edges
represent "contains" or "has a pointer to", and large triangles
represent "inherits from".
Note: the relation between GraphPack and GraphDrawingPack is not shown
because the model gets too complicated. For further information, see GraphDrawingPack,
UndoPack and Properties
