CO205 Coursework: Abstract Data-Type Graph

AdtGraph.PAS

(*
	Graph ADT Module

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

UNIT ADTGraph;

INTERFACE

USES
	ADTStack;
CONST
	MAXNODENAME = 20;		(* Maximum length of a node label *)
	MAXLINKNAME = 20;		(* Maximum length of a link label *)
	NUMLINKNODE = 2;		(* Number of nodes in a link *)
TYPE
	nlab_t = Array[0..MAXNODENAME-1] Of Char; (* Node label type *)
	llab_t = Array[0..MAXLINKNAME-1] Of Char; (* Link label type *)

	nval_t = Integer;		(* Node value type (integer/real) *)
	lval_t = Integer;		(* Link value type (integer/real) *)

	NODEPTR = ^NODE_T;		(* Pointer to a node type *)
	LINKPTR = ^LINK_T;		(* Pointer to a link type *)
	GRAPHPTR = ^GRAPH_T;		(* Pointer to a graph type *)

	NODE_T = Record			(* Node data structure *)
	  next:  NODEPTR;		(* Next node *)
	  name:	 nlab_t;		(* Node label *)
	  value: nval_t			(* Node value *)
	End;

	LINK_T = Record			(* Link data structure *)
	  next:  LINKPTR;		(* Next link *)
	  name:  llab_t;		(* Link label *)
	  value: lval_t;		(* Link value *)
	  node:  Array[1..NUMLINKNODE] Of Integer (* Linked nodes *)
	End;

	GRAPH_T = Record		(* Graph ADT data type *)
	  node: NODE_T;			(* Root of node list *)
	  link: LINK_T			(* Root of link list *)
	End;


(* Set the name of node to name *)
PROCEDURE SetNodeName (node: NODEPTR; name: PChar);

(* Set the value of node to value *)
PROCEDURE SetNodeValue (node: NODEPTR; value: nval_t);

(* Set the next-node pointer in node to next *)
PROCEDURE SetNextNode (node, next: NODEPTR);

(* Get the name of node *)
FUNCTION GetNodeName (node: NODEPTR): PChar;

(* Get the value of node *)
FUNCTION GetNodeValue (node: NODEPTR): nval_t;

(* Return the next-node pointer in node *)
FUNCTION GetNextNode (node: NODEPTR): NODEPTR;

(* Set the name of link to name *)
PROCEDURE SetLinkName (link: LINKPTR; name: PChar);

(* Set the value of link to value *)
PROCEDURE SetLinkValue (link: LINKPTR; value: lval_t);

(* Set the value of node n in link to value *)
PROCEDURE SetLinkNode (link: LINKPTR; n, value: Integer);

(* Set the next-link pointer in link to next *)
PROCEDURE SetNextLink (link, next: LINKPTR);

(* Get the name of link *)
FUNCTION GetLinkName (link: LINKPTR): PChar;

(* Get the value of link *)
FUNCTION GetLinkValue (link: LINKPTR): lval_t;

(* Get the value of node n in link *)
FUNCTION GetLinkNode (link: LINKPTR; n: Integer): Integer;

(* Return the next-link pointer in link *)
FUNCTION GetNextLink (link: LINKPTR): LINKPTR;

(* Return the root of the node list in graph *)
FUNCTION RootNode (graph: GRAPHPTR): NODEPTR;

(* Return the root of the link list in graph *)
FUNCTION RootLink (graph: GRAPHPTR): LINKPTR;

(* Return the first node listed in graph *)
FUNCTION FirstNode (graph: GRAPHPTR): NODEPTR;

(* Return the last node in the list in graph *)
FUNCTION LastNode (graph: GRAPHPTR): NODEPTR;

(* Return the index of node name in graph (or -1 if not found) *)
FUNCTION NodeIndex (name: PChar; graph: GRAPHPTR): Integer;

(* Return a pointer to node number index in graph *)
FUNCTION NodeNumber (index: Integer; graph: GRAPHPTR): NODEPTR;

(* Return the first link listed in graph *)
FUNCTION FirstLink (graph: GRAPHPTR): LINKPTR;

(* Return the last link in the list in graph *)
FUNCTION LastLink (graph: GRAPHPTR): LINKPTR;

(* Return the index of link name in graph (or -1 if not found) *)
FUNCTION LinkIndex (name: PChar; graph: GRAPHPTR): Integer;

(* Return a pointer to link number index in graph *)
FUNCTION LinkNumber (index: Integer; graph: GRAPHPTR): LINKPTR;

(* Create a new node with name and value *)
FUNCTION MakeNode (name: PChar; value: nval_t): NODEPTR;

(* Append node to the node list in graph *)
PROCEDURE AddNode (node: NODEPTR; graph: GRAPHPTR);

(* Create a new link between node n1 and node n2 with name and value *)
FUNCTION MakeLink (name: PChar; value: lval_t; n1, n2: Integer): LINKPTR;

(* Append link to the link list in graph *)
PROCEDURE AddLink (link: LINKPTR; graph: GRAPHPTR);

(* Initialize graph ADT data structure *)
PROCEDURE InitGraphADT (graph: GRAPHPTR);

(* Free all nodes and links in graph *)
PROCEDURE FreeGraphADT (graph: GRAPHPTR);

(* If node n is in link then return the linked node, otherwise -1 *)
FUNCTION LinkedNode (n: Integer; link: LINKPTR): Integer;

(* Return the link between nodes n1 and n2 in graph (or Nil if not found) *)
FUNCTION NodeLink (n1, n2: Integer; graph: GRAPHPTR): LINKPTR;

(* Find the shortest path (by link values) between nodes n1 and n2 *)
(* The path is stored in stack and the path length (or -1) is returned *)
(* If stack is Nil the path is discarded and only the length is returned *)
FUNCTION GraphPath (n1, n2: Integer; stack: STACKPTR; graph: GRAPHPTR): lval_t;

(* Load next link from file f and add it to graph *)
FUNCTION LoadLink (graph: GRAPHPTR; VAR f: Text): Boolean;

(* Load and add all links in file fname to graph *)
FUNCTION LoadLinkFile (fname: PChar; graph: GRAPHPTR): Boolean;


IMPLEMENTATION

USES
	Strings;

(*** Graph ADT Basic Primitives: NODES ***)

(* Set the name of node to name *)
PROCEDURE SetNodeName (node: NODEPTR; name: PChar);
BEGIN
	StrCopy(node^.name, name)
END;

(* Set the value of node to value *)
PROCEDURE SetNodeValue (node: NODEPTR; value: nval_t);
BEGIN
	node^.value := value
END;

(* Set the next-node pointer in node to next *)
PROCEDURE SetNextNode (node, next: NODEPTR);
BEGIN
	node^.next := next
END;

(* Get the name of node *)
FUNCTION GetNodeName (node: NODEPTR): PChar;
BEGIN
	GetNodeName := node^.name
END;

(* Get the value of node *)
FUNCTION GetNodeValue (node: NODEPTR): nval_t;
BEGIN
	GetNodeValue := node^.value
END;

(* Return the next-node pointer in node *)
FUNCTION GetNextNode (node: NODEPTR): NODEPTR;
BEGIN
	GetNextNode := node^.next
END;


(*** Graph ADT Basic Primitives: LINKS ***)

(* Set the name of link to name *)
PROCEDURE SetLinkName (link: LINKPTR; name: PChar);
BEGIN
	StrCopy(link^.name, name)
END;

(* Set the value of link to value *)
PROCEDURE SetLinkValue (link: LINKPTR; value: lval_t);
BEGIN
	link^.value := value
END;

(* Set the value of node n in link to value *)
PROCEDURE SetLinkNode (link: LINKPTR; n, value: Integer);
BEGIN
	link^.node[n] := value
END;

(* Set the next-link pointer in link to next *)
PROCEDURE SetNextLink (link, next: LINKPTR);
BEGIN
	link^.next := next
END;

(* Get the name of link *)
FUNCTION GetLinkName (link: LINKPTR): PChar;
BEGIN
	GetLinkName := link^.name
END;

(* Get the value of link *)
FUNCTION GetLinkValue (link: LINKPTR): lval_t;
BEGIN
	GetLinkValue := link^.value
END;

(* Get the value of node n in link *)
FUNCTION GetLinkNode (link: LINKPTR; n: Integer): Integer;
BEGIN
	GetLinkNode := link^.node[n]
END;

(* Return the next-link pointer in link *)
FUNCTION GetNextLink (link: LINKPTR): LINKPTR;
BEGIN
	GetNextLink := link^.next
END;


(*** Graph ADT Basic Primitives: GRAPHS ***)

(* Return the root of the node list in graph *)
FUNCTION RootNode (graph: GRAPHPTR): NODEPTR;
BEGIN
	RootNode := @graph^.node
END;

(* Return the root of the link list in graph *)
FUNCTION RootLink (graph: GRAPHPTR): LINKPTR;
BEGIN
	RootLink := @graph^.link
END;


(*** Graph ADT Locator Functions: NODES ***)

(* Return the first node listed in graph *)
FUNCTION FirstNode (graph: GRAPHPTR): NODEPTR;
BEGIN
	FirstNode := GetNextNode(RootNode(graph))
END;

(* Return the last node in the list in graph *)
FUNCTION LastNode (graph: GRAPHPTR): NODEPTR;
 FUNCTION _LastNode (node: NODEPTR): NODEPTR;
 BEGIN
	IF GetNextNode(node)=Nil THEN _LastNode := node
	ELSE _LastNode := _LastNode(GetNextNode(node))
 END;
BEGIN
	LastNode := _LastNode(RootNode(graph))
END;

(* Return the index of node name in graph (or -1 if not found) *)
FUNCTION NodeIndex (name: PChar; graph: GRAPHPTR): Integer;
 FUNCTION _NodeIndex (node: NODEPTR; name: PChar; n: Integer): Integer;
 BEGIN
	IF node=Nil THEN _NodeIndex := -1
	ELSE IF StrIComp(name, GetNodeName(node))=0 THEN _NodeIndex := n
	ELSE _NodeIndex := _NodeIndex(GetNextNode(node), name, n+1)
 END;
BEGIN
	NodeIndex := _NodeIndex(FirstNode(graph), name, 0)
END;

(* Return a pointer to node number index in graph *)
FUNCTION NodeNumber (index: Integer; graph: GRAPHPTR): NODEPTR;
 FUNCTION _NodeNumber (index: Integer; node: NODEPTR): NODEPTR;
 BEGIN
	IF index=0 THEN _NodeNumber := node
	ELSE _NodeNumber := _NodeNumber(index-1, GetNextNode(node))
 END;
BEGIN
	NodeNumber := _NodeNumber(index, FirstNode(graph))
END;


(*** Graph ADT Locator Functions: LINKS ***)

(* Return the first link listed in graph *)
FUNCTION FirstLink (graph: GRAPHPTR): LINKPTR;
BEGIN
	FirstLink := GetNextLink(RootLink(graph))
END;

(* Return the last link in the list in graph *)
FUNCTION LastLink (graph: GRAPHPTR): LINKPTR;
 FUNCTION _LastLink (link: LINKPTR): LINKPTR;
 BEGIN
	IF GetNextLink(link)=Nil THEN _LastLink := link
	ELSE _LastLink := _LastLink(GetNextLink(link))
 END;
BEGIN
	LastLink := _LastLink(RootLink(graph))
END;

(* Return the index of link name in graph (or -1 if not found) *)
FUNCTION LinkIndex (name: PChar; graph: GRAPHPTR): Integer;
 FUNCTION _LinkIndex (link: LINKPTR; name: PChar; n: Integer): Integer;
 BEGIN
	IF link=Nil THEN _LinkIndex := -1
	ELSE IF StrIComp(name, GetLinkName(link))=0 THEN _LinkIndex := n
	ELSE _LinkIndex := _LinkIndex(GetNextLink(link), name, n+1)
 END;
BEGIN
	LinkIndex := _LinkIndex(FirstLink(graph), name, 0)
END;

(* Return a pointer to link number index in graph *)
FUNCTION LinkNumber (index: Integer; graph: GRAPHPTR): LINKPTR;
 FUNCTION _LinkNumber (index: Integer; link: LINKPTR): LINKPTR;
 BEGIN
	IF index=0 THEN _LinkNumber := link
	ELSE _LinkNumber := _LinkNumber(index-1, GetNextLink(link))
 END;
BEGIN
	LinkNumber := _LinkNumber(index, FirstLink(graph))
END;


(*** Graph ADT Constructor Functions ***)

(* Create a new node with name and value *)
FUNCTION MakeNode (name: PChar; value: nval_t): NODEPTR;
VAR
	node: NODEPTR;
BEGIN
	New(node);			(* Create a new node *)
	SetNextNode(node, Nil);		(* Initialize next-node pointer *)
	SetNodeName(node, name);	(* Set node name *)
	SetNodeValue(node, value);	(* Set node value *)
	MakeNode := node		(* Return node pointer *)
END;

(* Append node to the node list in graph *)
PROCEDURE AddNode (node: NODEPTR; graph: GRAPHPTR);
BEGIN
	SetNextNode(LastNode(graph), node)
END;

(* Create a new link between node n1 and node n2 with name and value *)
FUNCTION MakeLink (name: PChar; value: lval_t; n1, n2: Integer): LINKPTR;
VAR
	link: LINKPTR;
BEGIN
	New(link);			(* Create a new link *)
	SetNextLink(link, Nil);		(* Initialize next-link pointer *)
	SetLinkName(link, name);	(* Set link name *)
	SetLinkValue(link, value);	(* Set link value *)
	SetLinkNode(link, 1, n1);	(* Set first linked node *)
	SetLinkNode(link, 2, n2);	(* Set second linked node *)
	MakeLink := link		(* Return link pointer *)
END;

(* Append link to the link list in graph *)
PROCEDURE AddLink (link: LINKPTR; graph: GRAPHPTR);
BEGIN
	SetNextLink(LastLink(graph), link)
END;


(*** Graph ADT Initialize/Shutdown ***)

(* Initialize graph ADT data structure *)
PROCEDURE InitGraphADT (graph: GRAPHPTR);
BEGIN
	SetNextNode(RootNode(graph), Nil);	(* Initialize node list *)
	SetNextLink(RootLink(graph), Nil);	(* Initialize link list *)
END;

(* Free all nodes and links in graph *)
PROCEDURE FreeGraphADT (graph: GRAPHPTR);
 PROCEDURE FreeNodes (node: NODEPTR);	(* Free node and its successors *)
 BEGIN
	IF GetNextNode(node)<>Nil THEN FreeNodes(GetNextNode(node));
	Dispose(node)
 END;
 PROCEDURE FreeLinks (link: LINKPTR);	(* Free link and its successors *)
 BEGIN
	IF GetNextLink(link)=Nil THEN FreeLinks(GetNextLink(link));
	Dispose(link)
 END;
BEGIN
	IF FirstNode(graph)<>Nil THEN FreeNodes(FirstNode(graph));
	IF FirstLink(graph)<>Nil THEN FreeLinks(FirstLink(graph));
END;


(*** Graph ADT High Level Functions ***)

(* If node n is in link then return the linked node, otherwise -1 *)
FUNCTION LinkedNode (n: Integer; link: LINKPTR): Integer;
VAR
	n1, n2: Integer;
BEGIN
	n1 := GetLinkNode(link, 1);		(* Get first linked node *)
	n2 := GetLinkNode(link, 2);		(* Get second linked node *)
	IF n=n1 THEN LinkedNode := n2		(* Return second if first *)
	ELSE IF n=n2 THEN LinkedNode := n1	(* Return first if second *)
	ELSE LinkedNode := -1			(* Return -1 if neither *)
END;

(* Return the link between nodes n1 and n2 in graph (or Nil if not found) *)
FUNCTION NodeLink (n1, n2: Integer; graph: GRAPHPTR): LINKPTR;
 FUNCTION _NodeLink (n1, n2: Integer; link: LINKPTR): LINKPTR;
 BEGIN
	IF link=Nil THEN _NodeLink := Nil
	ELSE BEGIN
		IF (LinkedNode(n1, link)<0) OR (LinkedNode(n2, link)<0)
		THEN _NodeLink := _NodeLink(n1, n2, GetNextLink(link))
		ELSE _NodeLink := link
	END
 END;
BEGIN
	NodeLink := _NodeLink(n1, n2, FirstLink(graph))
END;

(* Find the shortest path (by link values) between nodes n1 and n2 *)
(* The path is stored in stack and the path length (or -1) is returned *)
(* If stack is Nil the path is discarded and only the length is returned *)
FUNCTION GraphPath (n1, n2: Integer; stack: STACKPTR; graph: GRAPHPTR): lval_t;
 FUNCTION _GraphPath (n1, n2: Integer; dist, max: lval_t; stack: STACKPTR; graph: GRAPHPTR): lval_t;
  (* Block or unblock the use of node in a path (using node value) *)
  PROCEDURE NodeBlock (state: Boolean; node: Integer; graph: GRAPHPTR);
  VAR
	v: Integer;
  BEGIN
	IF state THEN v := 1 ELSE v := 0;
	SetNodeValue(NodeNumber(node, graph), v)
  END;
  (* Return true if node has been used in a path (is blocked) *)
  FUNCTION IsBlocked(node: Integer; graph: GRAPHPTR): Boolean;
  BEGIN
	IF GetNodeValue(NodeNumber(node, graph))=0
	THEN IsBlocked := False
	ELSE IsBlocked := True
  END;
 VAR
	link: LINKPTR;
	used: Boolean;
	n: Integer;
	v: lval_t;
 BEGIN
	used := False;			(* This node has not yet been used *)
	NodeBlock(True, n1, graph);	(* Prevent reuse of this node *)
	IF n1=n2 THEN			(* Is n1 the target node? *)
	BEGIN
		IF stack<>Nil THEN	(* Discard current path (if any) *)
		    WHILE StackSize(stack)>0 DO PopStack(stack);
		max := dist;		(* Set new maximum path length *)
		used := True		(* This node has been used *)
	END
	ELSE BEGIN			(* Check all links to node n1 *)
		link := FirstLink(graph);
		WHILE link<>Nil DO
		BEGIN			(* Look for node n1 in link *)
		    n := LinkedNode(n1, link);	(* Check for blocked node *)
		    IF (n>=0) AND NOT IsBlocked(n, graph) THEN
		    BEGIN		(* Check link to n is within range *)
			v := GetLinkValue(link);(* Check for blocked link *)
			IF (v>=0) AND ((max=0) OR (dist+v<max)) THEN
			BEGIN		(* Search all links from node n *)
			    v := _GraphPath(n, n2, dist+v, max, stack, graph);
			    IF v>=0 THEN	(* A path to n2 was found *)
			    BEGIN
				max := v;	(* Update maximum length *)
				used := True	(* This node has been used *)
			    END
			END
		    END;
		    link := GetNextLink(link)
		END
	END;
	NodeBlock(False, n1, graph);	(* Allow reuse of this node *)
	IF used THEN			(* A path to n2 was found *)
	BEGIN				(* Store node n1 on the stack *)
		IF stack<>Nil THEN PushStack(n1, stack);
		_GraphPath := max	(* Return path length *)
	END
	ELSE _GraphPath := -1		(* No path to n2 was found *)
 END;
BEGIN
	GraphPath := _GraphPath(n1, n2, 0, 0, stack, graph);
END;

(* Load next link from file f and add it to graph *)
FUNCTION LoadLink (graph: GRAPHPTR; VAR f: Text): Boolean;
CONST	MAXLINEBUF = 128;		(* Maximum length of a file line *)
 (* Get a non-empty line from file f (returns an empty line if EOF) *)
 FUNCTION GetLine (VAR f: Text): String;
 VAR
	s: String[MAXLINEBUF];
 BEGIN
	GetLine := '';			(* No line has been read *)
	REPEAT
		IF Eof(f) THEN Exit;	(* Terminate if end of file *)
		ReadLn(f, s);		(* Read next line *)
	UNTIL Length(s)>0;		(* Skip empty lines *)
	GetLine := s;			(* A line has been read *)
 END;
 (* Return index of an existing node with name or a node created with name *)
 FUNCTION GetNode (name: PChar; graph: GRAPHPTR): Integer;
 BEGIN
	IF NodeIndex(name, graph)<0		(* Find existing node *)
	THEN AddNode(MakeNode(name, 0), graph);	(* Add a new node *)
	GetNode := NodeIndex(name, graph)	(* Get node index *)
 END;
VAR
	buf: Array[0..MAXLINEBUF] Of Char;
	n1, n2, err: Integer;
	value: lval_t;
BEGIN
	LoadLink := False;			(* No link has been loaded *)
	IF Strlen(StrPCopy(buf, GetLine(f)))=0 THEN Exit; (* Get next line *)
	n1 := GetNode(buf, graph);		(* Get first node index *)
	IF Strlen(StrPCopy(buf, GetLine(f)))=0 THEN Exit; (* Get next line *)
	n2 := GetNode(buf, graph);		(* Get second node index *)
	IF Strlen(StrPCopy(buf, GetLine(f)))=0 THEN Exit; (* Get next line *)
	Val(buf, value, err);			(* Get link value *)
	AddLink(MakeLink('', value, n1, n2), graph);	(* Add a new link *)
	LoadLink := True			(* A link has been loaded *)
END;

(* Load and add all links in file fname to graph *)
FUNCTION LoadLinkFile (fname: PChar; graph: GRAPHPTR): Boolean;
VAR
	f: Text;
BEGIN
	{$I-}
	Assign(f, fname);
	Reset(f);
	IF IOResult<>0 THEN LoadLinkFile := False
	ELSE BEGIN
		WHILE LoadLink(graph, f) DO;
		Close(f);
		LoadLinkFile := True
	END;
	{$I+}
END;

BEGIN
END.