Abstract Data Types - Page 2
       by kirupa  |  4 January 2006

In the previous page, I explained what ADT's are provided some guidelines on creating your own. In this and the next few pages, I will explain how I created my Graph ADT.

Graph Representation
Our Graph is composed of Nodes with connected Edges. In my representation, an edge exists only if it is connecting two nodes. A pair of nodes may have multiple, different edges between them.

For consistency purposes, the node from which the edge originates from will be called the source node. The node that receives the edge will be called the target node.

Graph Examples
The following series of images provide valid representations of our Graph:

[ just one node ]

[ two nodes connected by one edge]

[ two nodes connected by two edges ]

[ a complicated example containing many nodes and edges ]

Another minor detail is how neighbors are defined. A neighbor is a node that can be reached in one step by traveling an edge. In the second example containing one edge and two nodes, Node 1's neighbor would be the Node 2. Node 2 does not have any neighbors because Node 1 cannot be reached using Edge 1.

Now that we have an idea of how our Graph will behave, let me run through some of the basic requirements of the ADT:

  • I should be able to add Nodes by simply specifying a Node's name and it's X and Y position.

  • I should be able to add an edge by calling a source node's add method that would take in the name of the target node.

  • Everything else - such as specifying the neighbors and displaying the data should be done automatically.

In the next page, I will provide a brief overview of all public methods in both the Node and Edge classes.

Onwards to the next page!

1 | 2 | 3 | 4 | 5


kirupa.com's fast and reliable hosting provided by Media Temple.