# Graphs

Many of the programs on the DelphiForFun website use graphs for game play. Examples include Sliding Coins Puzzle, Nim, Gametrees, and Minimax, Knight's Tour, Traffic Jam and Coal to Diamonds Puzzle. We recommend that you do some background reading if necessary, and we provide some guidance and links below. Graphs are often used together with the Minmax algorithm, which is also covered in the suggested reading. The terminology has these synonyms and abbreviations:
• A directed graph is a digraph.
• A vertex is a node.
• An arc is an edge.
• BFS stands for Breadth First Search.
• DFS stands for Depth First Search.
• An heuristic is variously described as an evaluation or rule of thumb.

Several online documents of university Artificial Intelligence course material cover the use of graphs in games. For a thorough explanation of a simple example of the Minimax algorithm see the MIT paper. A useful paper from Iowa covers the terminology and gives clear examples of an adjacency matrix. Trees are special cases of graphs. See this StackOverflow page to help you to decide if a certain graph is a tree. (We have covered binary trees in our tutorial on recursion and referred back to it from our sections on sorting and searching). Two relevant instructive pages on the DelphiForFun website are Graph Searching and Nim, Gametrees, and Minimax.

See our demonstration of breadth first search and depth first search, together with its Smart Pascal code, below.

## Tree Search Demonstration

The demonstration is set up for BFS (breadth first search). Change the selection to DFS for depth first search. Select the node number of the target to see the search results in the memo.

If the program does not work, try another browser such as Chrome. If you see no display at school, the security system might have blocked it. You can try instead this direct link to the program running on its own page.

The nodes are stored in a TObjectList. We use a queue to hold the indices of nodes to be visited in the BFS and a stack to hold them in the DFS. The code of XQueue and XStack was posted recently by Nico Wouterse on the Smart Mobile Studio forum.

## Smart Pascal Code of Form

```unit Form1;

interface

uses
SmartCL.System, SmartCL.Graphics, SmartCL.Components, SmartCL.Forms,
SmartCL.Fonts, SmartCL.Borders, SmartCL.Application, System.Lists,
SmartCL.Controls.PaintBox, SmartCL.Controls.Memo, SmartCL.Controls.Listbox,
SmartCL.Controls.Label, System.Colors, uRendering, uNode, XQueue, XStack;
type
TForm1 = class(TW3Form)
private
{\$I 'Form1:intf'}
protected
NodeIndexQueue: TQueue;
PathStack, NodeIndexStack: TStack;
CurrentIndex: integer;
PathString: string;
procedure InitializeForm; override;
procedure InitializeObject; override;
procedure SetupNodes;
procedure BFS(TargetNode: TNode);
procedure DFS(TargetNode: TNode);
procedure RetrievePath;
end;
var
ListOfNodes: TObjectlist;
A, B, C, D, E, F, G, H, I, J, CurrentNode, TempNode: TNode;

implementation

procedure TForm1.RetrievePath;
begin
PathString := 'Found path: ';
// Follow reverse path via previousNode values and add each node to stack.
PathStack := TStack.Create;
PathStack.Push(CurrentIndex);
repeat
CurrentNode := CurrentNode.PreviousNode;
CurrentIndex := ListOfNodes.IndexOf(CurrentNode);
PathStack.Push(CurrentIndex);
until CurrentIndex = 0;
// Pop the nodes to get the forward path to the target.
for var i := 0 to PathStack.Length - 1 do
begin
CurrentIndex := PathStack.Pop;
PathString += TNode(ListOfNodes[CurrentIndex]).Name + ' ';
end;
W3Memo1.Text := W3Memo1.Text + PathString;
end;

procedure TForm1.BFS(TargetNode: TNode);
begin
repeat
if NodeIndexQueue.Length = 0 then
begin
exit;
end
else
begin
CurrentIndex := NodeIndexQueue.Dequeue;
W3Memo1.Text := W3Memo1.Text + 'Visited ' + inttostr(CurrentIndex) + ' ';
CurrentNode := TNode(ListOfNodes[CurrentIndex]);
if CurrentNode = TargetNode then
begin
RetrievePath;
exit;
end
else
TempNode := CurrentNode;
for var i := 0 to TempNode.AdjacentNodes.Count - 1 do
begin  // Add child nodes to queue
CurrentNode.PreviousNode := TempNode;
CurrentIndex := ListOfNodes.IndexOf(CurrentNode);
NodeIndexQueue.Enqueue(CurrentIndex);
end;
W3Memo1.Text := W3Memo1.Text + 'Queued indices: ' +
NodeIndexQueue.FHandle.join(' ') + #13#10;
end;
end;
until false;
end;

procedure TForm1.DFS(TargetNode: TNode);
begin
repeat
if NodeIndexStack.Length = 0 then
begin
exit;
end
else
begin
CurrentIndex := NodeIndexStack.Pop;
W3Memo1.Text := W3Memo1.Text + 'Visited ' + inttostr(CurrentIndex) + ' ';
CurrentNode := TNode(ListOfNodes[CurrentIndex]);
if CurrentNode = TargetNode then
begin
RetrievePath;
exit;
end
else
TempNode := CurrentNode;
for var i := TempNode.AdjacentNodes.Count - 1 downto 0 do
begin  // Push child nodes to stack in reverse order
CurrentNode.PreviousNode := TempNode;
CurrentIndex := ListOfNodes.IndexOf(CurrentNode);
NodeIndexStack.Push(CurrentIndex);
end;
W3Memo1.Text := W3Memo1.Text + 'Stacked indices: ' +
NodeIndexStack.FHandle.join(' ') +  #13#10;
end;
end;
until false;
end;

procedure TForm1.InitializeForm;
begin
inherited;
SetupNodes;
// Draw tree in paint box
PB.OnPaint := procedure(Sender: TObject; Canvas: TW3Canvas)
begin
RenderScene(PB.Canvas);
PB.Invalidate;
end;
// List box for selecting destination node
lbTarget.ItemHeight := 28;
lbTarget.ItemClass := TW3Label;
for var i := 1 to 9 do
lbTarget.Styles.SelectedColor := clLightBlue;
lbTarget.EnableAnimation := false;
for var i := 0 to 8 do
TW3Label(lbTarget.Items[i]).Caption := inttostr(i + 1);

lbTarget.OnSelected := procedure (sender: TObject; idx: integer)
begin
W3Memo1.Text := '';
CurrentNode := A;
if lbSearchType.SelectedIndex = 0 then  // BFS
begin
NodeIndexQueue := TQueue.Create;
NodeIndexQueue.Enqueue(0);
BFS(TNode(ListOfNodes[idx + 1]));
end
else  // DFS
begin
NodeIndexStack := TStack.Create;
NodeIndexStack.Push(0);
DFS(TNode(listofnodes[idx + 1]));
end;
end;
// List box for selecting BFS or DFS
lbSearchType.ItemHeight := 28;
lbSearchType.ItemClass := TW3Label;
lbSearchType.Styles.SelectedColor := clLightBlue;
lbSearchType.SelectedIndex := 0;
lbSearchType.EnableAnimation := false;
TW3Label(lbSearchType.Items[0]).Caption := 'BFS';
TW3Label(lbSearchType.Items[1]).Caption := 'DFS';
end;

procedure TForm1.InitializeObject;
begin
inherited;
{\$I 'Form1:impl'}
end;

procedure TForm1.SetupNodes;
begin
// Call each node constructor to set X and Y coordinates and name.
A := TNode.Create(150, 20, '0');
B := TNode.Create(100, 80, '1');
C := TNode.Create(200, 80, '2');
D := TNode.Create(30, 140, '3');
E := TNode.Create(100, 140, '4');
F := TNode.Create(140, 140, '5');
G := TNode.Create(190, 140, '6');
H := TNode.Create(230, 140, '7');
I := TNode.Create(60, 200, '8');
J := TNode.Create(130, 200, '9');

ListOfNodes := TObjectList.Create;
// Place the nodes in the ListOfNodes TObjectList.
end;

initialization
Forms.RegisterForm({\$I %FILE%}, TForm1);
end.

```

## Smart Pascal Code of uNode

```unit uNode;

interface

uses
SmartCL.System, System.Lists;

type
double = float;

TNode = class(TObject)
public
X, Y: double;
Name: string;
PreviousNode: TNode;
constructor Create(XX, YY: double; NodeName: string);
end;

implementation

constructor TNode.Create(XX, YY: double; NodeName: string);
begin
X := XX;
Y := YY;
Name := NodeName;
PreviousNode := nil;
end;

begin
end;

end.

```

## Smart Pascal Code of uRendering

```unit uRendering;

{

use this file except in compliance with the License, as described at

Converted to Smart Pascal by PPS (2016)
}

interface

uses
SmartCL.System, SmartCL.Graphics, uNode;

procedure DrawNode(Canvas: TW3Canvas; NodeToDraw: TNode);
procedure RenderScene(Canvas: TW3Canvas);

implementation

uses
Form1;

procedure DrawNode(Canvas: TW3Canvas; NodeToDraw: TNode);
begin
Canvas.FillStyle := 'white';
Canvas.FillRectF(NodeToDraw.X, NodeToDraw.Y, 32, 32);
// Write the node name.
Canvas.FillStyle := 'black';
Canvas.Font := 'bold 12pt arial';
canvas.FillTextF(NodeToDraw.Name, NodeToDraw.X, NodeToDraw.Y, 10000);
end;

procedure RenderScene(canvas: TW3Canvas);
var
Count, InnerCount : integer;
begin
// Draw the  background
Canvas.FillStyle := 'lightgrey';
Canvas.FillRect(0, 0, 304, 232);
// Draw the nodes.
for Count := 0 to ListOfNodes.Count - 1 do
DrawNode(Canvas, TNode(ListOfNodes[Count]));
// Draw the edges
for Count := 0 to ListOfNodes.Count - 2 do
begin
for InnerCount := 0 to (TNode(ListOfNodes[Count]).AdjacentNodes.Count - 1) do
begin
Canvas.FillStyle := 'blue';
Canvas.StrokeStyle := 'blue';
Canvas.BeginPath;
Canvas.LineF(TNode(ListOfNodes[Count]).X + 16,
TNode(listOfNodes[Count]).Y + 16,
TempNode.X + 16, TempNode.Y + 16);
Canvas.ClosePath;
Canvas.Stroke;
end;
end;
end;

end.

```

## Smart Pascal Code of XQueue

We thank Nico Wouterse for sharing his code of XQueue.

```unit XQueue;

interface

uses
SmartCL.System, System.Types;

type
TQueue = class (TObject)
public
Constructor Create; virtual;
Procedure   Enqueue(Item: Variant);
Function    Dequeue: Variant;
Function    Peek: Variant;
Function    Length: Variant;
Procedure   Print;
FHandle :   THandle;
end;

implementation

Constructor TQueue.Create;
begin
inherited Create;
FHandle := TVariant.CreateArray;
end;

Procedure TQueue.Enqueue(Item: Variant);
begin
If Item.IsString then Item := "'" + Item + "'";
FHandle.push(Item);
end;

Function TQueue.Dequeue: Variant;
begin
result := FHandle.shift();
end;

Function TQueue.Peek;
begin
result := FHandle[0];
end;

Function TQueue.Length:Variant;
begin
result := FHandle.length;
end;

Procedure TQueue.Print;
begin
writeln(FHandle.join(' - '));
end;

end.

```

## Smart Pascal Code of XStack

We thank Nico Wouterse for sharing his code of XStack.

```unit XStack;

interface

uses
SmartCL.System, System.Types;

type
TStack = class (TObject)
public
Constructor Create; virtual;
Procedure   Push(Item: Variant);
Function    Pop: Variant;
Function    Peek: Variant;
Function    Length: Variant;
Procedure   Print;
FHandle :   THandle;
end;

implementation

Constructor TStack.Create;
begin
inherited Create;
FHandle := TVariant.CreateArray;
end;

Procedure TStack.Push(Item: Variant);
begin
If Item.IsString then Item := "'" + Item + "'";
FHandle.push(Item);
end;

Function TStack.Peek;
begin
result := FHandle[FHandle.length-1];
end;

Function TStack.Pop: Variant;
begin
result := FHandle.pop();
end;

Function TStack.Length:Variant;
begin
result := FHandle.length;
end;

Procedure TStack.Print;
begin
writeln(FHandle.join(' - '));
end;

end.

```

## XML Code of Form

We use the Android-HoloDark.css theme.

```<SMART>
<Form version="2" subversion="2">
<Created>2016-12-03T14:16:26.359</Created>
<Modified>2016-12-05T12:05:59.562</Modified>
<object type="TW3Form">
<Caption>W3Form</Caption>
<Name>Form1</Name>
<object type="TW3PaintBox">
<Width>304</Width>
<Height>232</Height>
<Name>PB</Name>
</object>
<object type="TW3Memo">
<Width>272</Width>
<Top>240</Top>
<Height>160</Height>
<Name>W3Memo1</Name>
</object>
<object type="TW3ListBox">
<Width>48</Width>
<Top>30</Top>
<Left>320</Left>
<Height>272</Height>
<Name>lbTarget</Name>
</object>
<object type="TW3Label">
<Caption>Select Target</Caption>
<Width>128</Width>
<Left>304</Left>
<Height>24</Height>
<Name>W3Label1</Name>
</object>
<object type="TW3ListBox">
<Width>48</Width>
<Top>328</Top>
<Left>320</Left>
<Height>72</Height>
<Name>lbSearchType</Name>
</object>
<object type="TW3Label">
<Caption>Select Search Type</Caption>
<Width>152</Width>
<Top>304</Top>
<Left>280</Left>
<Height>24</Height>
<Name>W3Label2</Name>
</object>
</object>
</Form>
</SMART>

```
Programming - a skill for life!

Challenges from the DelphiForFun Website