CO205 Coursework: Abstract Data-Type Graph

Towns.PAS

(*
	Graph Route Finder

	CO205 Coursework: GRAPHS
	Eamonn Martin (BSc Computing)
	ID: 96D59682
*)

PROGRAM Towns;

USES
	Strings, ADTStack, ADTGraph;

(* Return string zstr left-justified in a field of width w *)
FUNCTION StrField (zstr: PChar; w: Integer): String;
VAR
	pstr: String;
BEGIN
	pstr := StrPas(zstr);
	WHILE Length(pstr)<w DO pstr := pstr+' ';
	StrField := pstr;
END;

(* Display all towns in graph *)
PROCEDURE ShowTowns (graph: GRAPHPTR);
VAR
	node: NODEPTR;
	n: Integer;
BEGIN
	node := FirstNode(graph);
	WriteLn;
	WriteLn('Enter starting and ending towns from the following list:');
	WriteLn;
	WHILE node<>Nil DO
	BEGIN
		Write(StrField(GetNodeName(node), 20));
		node := GetNextNode(node);
		n := n+1
	END;
	IF (n MOD 4)<>0 THEN WriteLn;
	WriteLn
END;

(* Get the name of a town in the list in graph from the user *)
FUNCTION GetTown (prompt: PChar; graph: GRAPHPTR): Integer;
VAR
	buf: nlab_t;
	t: Integer;
BEGIN
	Write(prompt);				(* Write prompt *)
	ReadLn(buf);				(* Read town name *)
	WHILE StrLen(buf)>0 DO
	BEGIN
		t := NodeIndex(buf, graph);	(* Search in graph *)
		IF t>=0 THEN			(* Node was located *)
		BEGIN
			GetTown := t;		(* Return node index *)
			Exit
		END;
		WriteLn('Town is not listed!');	(* Node not located *)
		Write(prompt);			(* Repeat prompt *)
		ReadLn(buf)			(* Re-read town name *)
	END;
	GetTown := -1				(* Input was aborted *)
END;

(* Display the route through graph currently stored in stack *)
PROCEDURE ShowRoute (stack: STACKPTR; graph: GRAPHPTR);
VAR
	total, d: lval_t;
	t1, t2: Integer;
BEGIN
	total := 0;
	t1 := PopStack(stack);
	WriteLn('':10, '':15, 'Distance':10, 'Total':10);
	WriteLn('Start at:':10, GetNodeName(NodeNumber(t1, graph)):15, 0:10, 0:10);
	WHILE StackSize(stack)>0 DO
	BEGIN
		t2 := PopStack(stack);
		d := GetLinkValue(NodeLink(t1, t2, graph));
		total := total+d;
		WriteLn('Then to:':10, GetNodeName(NodeNumber(t2, graph)):15, d:10, total:10);
		t1 := t2
	END;
	WriteLn;
END;

(* Output shortest path between two entered names through graph in fname *)
PROCEDURE GraphFile (fname: PChar);
VAR
	graph	: GRAPH_T;
	stack	: STACK_T;
	t1, t2	: Integer;
BEGIN
	InitGraphADT(@graph);
	InitStackADT(@stack);
	IF NOT LoadLinkFile(fname, @graph) THEN		(* Read data file *)
	BEGIN
		WriteLn('Cannot open file: ', fname);
		Exit
	END;
	ShowTowns(@graph);				(* Display list *)
	REPEAT
		t1 := GetTown('Start at.: ', @graph);	(* Get town 1 *)
		IF t1<0 THEN Break;
		t2 := GetTown('End at...: ', @graph)	(* Get town 2 *)
	UNTIL t2>=0;
	IF t1>=0 THEN
	BEGIN
		GraphPath(t1, t2, @stack, @graph);	(* Search graph *)
		IF NOT (StackSize(@stack)>0) THEN WriteLn('No link found!')
		ELSE ShowRoute(@stack, @graph)		(* Show path *)
	END;
	FreeGraphADT(@graph)				(* Destroy graph *)
END;

PROCEDURE Main;
CONST	DATAFILE = 'TOWNS.DAT';
VAR	fname	: Array[0..80] Of Char;
BEGIN
	IF ParamCount=0 THEN StrCopy(fname, DATAFILE)	(* Default filename *)
	ELSE StrPCopy(fname, ParamStr(1));		(* Given filename *)
	GraphFile(fname)				(* Process file *)
END;

BEGIN
	Main;
END.