CO205 Coursework: Abstract Data-Type Graph

Documentation

Contents

  1. Task Evaluation

  2. Design Notes

  3. Graph ADT Definition

  4. Graph ADT Module

  5. Stack ADT Module

  6. Graph ADT High Level Functions

  7. User Instructions

Task Evaluation

The primary task of this program is to create and search a graph ADT structure. My first step in creating this program was to design a simple prototype implementing the create and search functions. This was done to isolate the basic features that the graph ADT would need in order to complete the task.

The next step was to refine the specialized graph ADT functions and data types in the prototype to produce a generalized implementation. The graph ADT definitions were expanded to include features which are relevant to the graph ADT but are not actually used by this program (such as link names). The stack ADT module was created to provide a convenient way to store pathways through the graph and this too was developed into a general-purpose implementation.

The various graph ADT operations were isolated and each placed into a separate function or procedure. Related functions were organized into groups. These groups and their contents are listed below.

Design Notes

The MakeLink function and the high level functions assume that each link joins exactly two nodes. This adequately satisfies the requirements of the program, though it would be feasible to generalize their implementation to allow any number of nodes. The basic primitives, the locator functions and the graph ADT definition itself do allow for any number of linked nodes.

The graph-searching function (GraphPath) assumes that links can be traversed in any direction (ie. they are 'edges'). This satisfies the requirements of the program since the distance between two towns is assumed to be the same in either direction. Nodes are also assumed to be implicitly linked to themselves (ie. they are 'looped').

For a full search, the GraphPath function assumes that all node values have been set to zero, as is done by the LoadLink function. This is because GraphPath uses the node values as flags to indicate whether or not each node has been used in a path. If any nodes are set to non-zero values prior to a search, those nodes will be ignored during the search.

GraphPath also assumes that negative link values indicate inactive links. Any links set to negative values prior to a search will not be used during the search.

The LoadLink function assumes that the data file contains a series of newline-separated link records, each consisting of three newline-separated fields. Empty lines in the file are ignored. The three fields expected are two node labels and a link value. For each record the function creates the two nodes and adds them to the graph node list (if not already listed). It then creates a link between the two nodes using the loaded link value. The values of nodes are set to zero and the names of links are set to empty strings.

Graph ADT Definition

Graph ADT Module

This provides general-purpose functions for creating and updating graphs.

Basic Primitives
Provide an implementation-independant interface to the graph data types.

	Nodes:	SetNodeName		GetNodeName
		SetNodeValue		GetNodeValue
		SetNextNode		GetNextNode

	Links:	SetLinkName		GetLinkName
		SetLinkValue		GetLinkValue
		SetLinkNode		GetLinkNode
		SetNextLink		GetNextLink

	Graphs:	RootNode		RootLink
Locator Functions
These allow graph elements to be located and examined.

	Nodes:	FirstNode		LastNode
		NodeIndex		NodeNumber

	Links:	FirstLink		LastLink
		LinkIndex		LinkNumber
Constructor Functions
These provide a mechanism for contructing graphs.

	Nodes:	MakeNode		AddNode

	Links:	MakeLink		AddLink
Initialize/Shutdown
These handle the initialization and destruction of a graph ADT.

	Graphs:	InitGraphADT		FreeGraphADT

Stack ADT Module

This provides general-purpose functions for creating and updating stacks. The GraphPath search routine requires a stack ADT in which it stores the path it has located. The following lists the contents of the stack module.

Basic Primitives
Provide an implementation-independant interface to the stack data type.

		SetStackValue		GetStackValue
		SetNextStack		GetNextStack
Locator
This allows the number of elements in a stack ADT to be determined.

		StackSize
Constructor/Destructor
These add values to and remove values from a stack ADT.

		PushStack		PopStack
Initialization
This handles the initialization of a stack ADT.

		InitStackADT

Graph ADT High Level Functions

These functions make use of the Graph ADT Module and the Stack ADT module.

		LinkedNode
		NodeLink
		GraphPath
		LoadLink
		LoadLinkFile

User Instructions

TOWNS [filename]
The filename is the name of a link-data file to read from. If no filename is given, the default TOWNS.DAT is used.

This program reads a list of towns and the distances between them from a file and uses them to create a graph ADT structure. It then presents the list of towns in the graph and prompts for the names of two towns to find a path between. If a name is entered that is not found in the list, a message is printed and the prompt is repeated. If an empty line is entered at the prompt for the first town, the program terminates. If an empty line is entered for the second town, the prompt for the first town is repeated. If two listed town names are entered, the program searches the graph and reports the shortest path between them (if any).

Go To: CO205 Coursework