Dijkstra's algorithm (Inform 7)

From LiteratePrograms

Other implementations: C++ | Inform 7 | Java | Scala

Dijkstra's algorithm is a graph algorithm that simultaneously finds the shortest path from a single vertex in a weighted graph to all other vertices in the graph, called the single-source shortest path problem. It works for directed and undirected graphs, but unlike the Bellman-Ford algorithm, requires nonnegative edge weights.

Contents 1 theory 2 practice 2.1 Dijkstra's algorithm 2.2 definitions 2.3 test data 2.4 interaction 3 wrapping up

theory

We use the relation support in Inform 7 to code a well-known graph algorithm. Inform 7 is somewhat reminiscent of a cross between Prolog, COBOL, and DDL — with the interesting property that phrases such as the nearest examined node contacting the current node may serve both as specification and as executable code.

practice

I got this to work with the current version of Inform 7 by:

• replacing all instances of "total distance" with "total_distance" because otherwise the current version of Inform 7 says "... this seems to be an attempt to total up the column of a table, whereas it's only legal to use 'total' for properties."
• repalcing "decide on the total_distance of n + the distance between m and n." with "let d be the total_distance of n plus the distance between m and n; decide on d." because otherwise the current version of Inform 7 says "you wrote ... the outcome of a phrase to decide a value, but this was the wrong kind of value: an instruction to work something out rather than a number."

Dijkstra's algorithm

Dijkstra's algorithm is a greedy algorithm that divides nodes up into three types:

• nodes for which we have definitely found the shortest path
• nodes which we have examined, which have a shortest path thus far seen
• and, nodes which are yet unreached

We start by examining the source node, by definition at distance 0, with all the rest as yet unreached. Then we repeatedly run examination steps until converging by running out of examined nodes to consider. On each iteration, we greedily convert the nearest examined node to a found node, and then examine all of its neighbors — the nodes contacting n.

<<dijkstra's algorithm>>=
Every turn: run Dijkstra's algorithm.
To run Dijkstra's algorithm:
	initialize Dijkstra's algorithm from the current node;
	while some of the nodes are examined begin;
		continue Dijkstra's algorithm;
	end while.
To initialize Dijkstra's algorithm from (n - a node):
	clear the state;
	now n is examined;
	change the total distance of n to 0.
To continue Dijkstra's algorithm:
	let n be the nearest examined node;
	now n is found;
	repeat with m running through the nodes contacting n begin;
		examine m from n;
	end repeat.

when we examine a path to a node, it may

• already have a confirmed shortest path
• be the first time we have encountered the node
• or, already have a provisional shortest path

in which case, we

• ignore it (perform a NOP to keep Inform happy)
• set its total distance and add it to the examined set along with a back-pointer
• or, do the above only if the new total distance would be shorter than the old.

<<dijkstra's algorithm>>=
To examine (m - a found node) from (n - a node): now m is found.
To examine (m - an unreached node) from (n - a node):
	now m is examined;
	change the total distance of m to the extension of n to m;
	now m follows n.
To examine (m - an examined node) from (n - a node):
	let d be the extension of n to m;
	if the total distance of m > d begin;
		change the total distance of m to d;
		now m follows n;
	end if.

some ancillary details:

<<dijkstra's algorithm>>=
To clear the state:
	repeat with m running through nodes begin;
		now m is unreached;
		now m does not follow anything;
	end repeat;
To decide what number is the extension of (n - a node) to (m - a node):
	decide on the total distance of n + the distance between m and n.

definitions

There are a number of definitions we need to make for the code above to run — both static properties, which are a function of the given graph:

• defining contact allows us to repeat over nodes contacting n.
• as it is constant, we will initialize the contact relation once, when play begins.

<<node properties>>=
A node is a kind of thing.
Contact relates nodes to each other.
The verb to contact (he contacts, they contact, he contacted, it is contacted, he is contacting) implies the contact relation.

and dynamic properties, which will change when we change the source node.

• the total distance holds the the length of the (currently estimated) shortest path from the source node.
• the 10 in the definition of near is arbitrary — we provide this definition only so that we may use the superlative, and ask for the nearest examined node when we continue Dijkstra's algorithm.
• defining the precedent allows us to extract the full path (in reverse order) to any given node from the source node.

<<node properties>>=
The current node is a node that varies.
A node can be found, examined, or unreached.
A node has a number called the total distance.  
Definition: a node is near if its total distance is 10 or less.
Following relates various nodes to one node (called the precedent).
The verb to follow (he follows, they follow, he followed, it is followed, he is following) implies the following relation.

test data

We use the test data from Dijkstra's algorithm (Scala), and add Oxford, the home of Inform 7. It may be possible to key on multiple fields, but as the table is small, here we take the brute-force approach of performing a symmetric scan.

<<test data>>=
Barcelona, Geneve, Lausanne, London, Marseille, Narbonne, Oxford, Paris, and Toulouse are nodes.
Table of Intercity Distances
src	dst	distance
Barcelona	Narbonne	250
Geneve	Lausanne	64
Geneve	Marseille	260
Geneve	Narbonne	550
Geneve	Paris	540
Geneve	Toulouse	700
Lausanne	Paris	536
London	Oxford	95
London	Paris	440
Marseille	Narbonne	260
Narbonne	Toulouse	150
Paris	Toulouse	680
To decide what number is the distance between (n - a node) and (m - a node):
	repeat through the Table of Intercity Distances begin;
		if the src entry is n and the dst entry is m, decide on the distance entry;
		if the src entry is m and the dst entry is n, decide on the distance entry;
	end repeat.

interaction

In order to provide output and accept user input, we must make a few more definitions. The recursion runs from the desired node back to the current node, but the output is generated upon return, yielding the path in-order from current to desired.

<<user interaction>>=	
Definition: a node is initial if it is the current node.
To slide the marker from (n - an initial node):
	say "You take the marker from [n] and slide it".
To slide the marker from (n - a node):
	slide the marker from the precedent of n;
	say " to [n]".
To slide the marker to (n - a node):
	slide the marker from the precedent of n;
	say ", winding up at [n].".
planning is an action applying to one visible thing.
understand "[a node]" as planning.
check planning:
	if the current node is the noun, say "The marker is already at [the current node]." instead.
carry out planning: 
	slide the marker to the noun;
	change the current node to the noun.

wrapping up

Finally we complete the game with the authoring boilerplate, an initial room for the player, some initialization code, and a small test-suite.

<<dijkstra.inform7>>=
"Dijkstra's Algorithm" by Dave
node properties
dijkstra's algorithm
test data
user interaction	
The Map Room is a room.
"You are looking at a roadmap centered on the south of France[line break]Say 'relations' to examine the current graph state[line break]Say 'city name' to plan a trip from [the current node].". 
The marker and the roadmap are scenery in the Map Room.
When play begins:
	repeat through the Table of Intercity Distances begin;
		now the src entry contacts the dst entry;
		now the dst entry contacts the src entry;
	end repeat;
	repeat with n running through the nodes begin;
		move n to the Map Room;
	end repeat;
	change the current node to Barcelona;
	run Dijkstra's algorithm.
Test me with "barcelona/lausanne/barcelona/paris/marseille"

A sample run is as follows:

Map Room
You are looking at a roadmap centered on the south of France
Say "city name" to plan a trip from Barcelona.
You can see Toulouse, Paris, Narbonne, Marseille, Lausanne, Geneve and Barcelona here.
> barcelona
The marker is already at Barcelona.
> lausanne
You take the marker from Barcelona and slide it to Narbonne to Marseille to Geneve, winding up at Lausanne.
> barcelona
You take the marker from Lausanne and slide it to Geneve to Marseille to Narbonne, winding up at Barcelona.
> paris
You take the marker from Barcelona and slide it to Narbonne to Toulouse, winding up at Paris.
> marseille
You take the marker from Paris and slide it to Geneve, winding up at Marseille.
>

Download code