A simple graph algorithm on a RISK game board

A simple graph algorithm on a RISK game board

This article looks at simple graph algorithm which I saw in the video Type driven testing in Haskell by Simon Peyton-Jones. The algorithm is translated to Clojure and visualized on an interactive RISK game board using the Apache Batik SVG library.

Graph representation

Graphs are represented as a map of nodes to its neigbours. For example, the graph

will be represented as

{:a #{:b :c :d :f :i}
 :b #{:a :d}
 :c #{:a :e}
 :d #{:a :b :e}
 :e #{:d :c}
 :f #{:a :g}
 :g #{:f :h}
 :h #{:g}
 :i #{:a :j}
 :j #{:i}}

With this representation it is trivial to find the neigbours of a node in a graph:

  (graph node)

Description of the algorithm

We shall define a function (shell node n graph) that returns the set of nodes that are exactly n steps away from a node in the graph. For example, (shell :a 2 graph), would return the set #{:e :j :g} as highlighted in the following illustration:

Note that :d is not in the 2-shell of :a even though you can get there in two steps via :b (there is a shorter path).

Recursive implementation

Here is the recursive implementation of shell:

(defn shell
  "The set of nodes that are n steps away from node in graph. 
   Returns nil if node is not in graph."
  [node n graph]
  (when (graph node)
    (case n
      0 #{node}
      1 (graph node)
      (let [n-1-shell (shell node (- n 1) graph)
            n-2-shell (shell node (- n 2) graph)]
	    (difference (reduce union (map graph shell-1))
                    shell-1
                    shell-2)))))

First of all, if the node is not actually in the graph, nil is returned, otherwise we do a case analysis on n:

• When n is zero, the singleton set #{node} is returned as that is the only node which is zero steps away from node.

• When n is one, The set of neigbours of the node is returned.

• Otherwise, shell is called twice recursively to get both the n-1-shell (read: n minus one shell) and the n-2-shell. The union of all the neigbours of the n-1-shell must be a superset of the desired answer and since we don't want any members of the previous shells we remove them (with the set operation difference).

There are, however, a few problems:

• The function is not tail recursive.
• The running time of the function is exponential! For every call to shell we recursively call it twice until we reach n = 0 or n = 1:

(shell node 5 graph)
|->(shell node 4 graph)
|  |->(shell node 3 graph)
|  |  |->(shell node 2 graph)
|  |  |  |->(shell node 1 graph)
|  |  |  |->(shell node 0 graph)
|  |  |->(shell node 1 graph)
|  |->(shell node 2 graph)
|     |->(shell node 1 graph)
|     |->(shell node 0 graph)
|->(shell node 3 graph)
   |->(shell node 2 graph)
   |  |->(shell node 1 graph)
   |  |->(shell node 0 graph)
   |->(shell node 1 graph)

A simple solution to the second problem is to memoize the function:

(alter-var-root #'shell memoize)

Now, when the function is called with a set of arguments it has seen before, it gets the return value from a cache instead of recomputing the body of the function:

(shell node 5 graph)
|->(shell node 4 graph)
|  |->(shell node 3 graph)
|  |  |->(shell node 2 graph)
|  |  |  |->(shell node 1 graph)
|  |  |  |->(shell node 0 graph)
|  |  |-> (shell node 1 graph) ;; fetch from cache
|  |-> (shell node 2 graph) ;; fetch from cache
|-> (shell node 3 graph) ;; fetch from cache

Antother implementation

Let's define a function (kernel node n graph) which returns the set of all nodes that are fewer than n steps away from a node in the graph:

(defn kernel [node n graph]
  (->> #{node}
       (iterate #(reduce union (map graph %)))
       (take n)
       (reduce union)))

The image below illustrates the 2-kernel of node :a in graph, (kernel :a 2 graph):

With the kernel helper function it's very easy to define shell:

(defn shell [node n graph]
  (if (zero? n)
    #{node}
    (let [kernel-nodes (kernel node n graph)]
      (difference (reduce union (map graph kernel-nodes))
                  kernel-nodes))))

An interactive GUI

I will not explain the implementation of the interactive GUI as I'm not familiar enough with the Batik library. Instead I'll only describe how to get it up and running. I believe that git and lein are the only requirements:

$ git clone [email protected]:jonase/mlx.git 
$ cd mlx 
$ lein deps 
$ lein repl 
user=> (use 'mlx.risk.gui) 
user=> (start) 

The previous set of commands should give you the following GUI to play with (click on the territories to see some action):