Quick links
 Randomized depthfirst search
 Randomized depthfirst search with stack shaking
 Random spanning tree with Prim’s algorithm
 Random spanning tree using Kruskal’s algorithm
 Hybrid of depthfirst search and Kruskal’s algorithm
 Source code
 Online demo
Read original blogpost first
This is just an update to previous blogpost titled Kruskal, Kotlin, and Hex Tiles. I assume you read it, otherwise some things may not make sense.
Problem with “pure” algorithms
We already tried DepthFirst Search and Kruskal’s algorithm. They both have some disadvantages. DepthFirst Search has low branching factor, meaning that is does not branch unless it gets stuck, so it actually can create one very long path through the whole maze to the point where it is hard to call it “maze” anymore.
On the other side there is Kruskal’s algorithms which is all about branching. The problem with branching is that even if it creates a deadend the length of deadend branch is quite often low (let’s say one or two “rooms”) and is very easy to spot.
The “challenge” was to create algorithm which is a hybrid of DepthFirst Search and Kruskal’s algorithm.
A Trailblazer algorithm
For this I needed a DFS algorithm using the same domain model as previously implemented Kruskal’s algorithm. It assumed existence of nodes and edges, having no constraint on node (vertex) and expecting edge to be a pair of nodes (vertices):


Algorithm itself had very simple interface, it was taking a sequence of edges (most likely randomized), and provided a method called next()
returning next edge forming spanning tree. Please note that in languages with generators (Kotlin is not blessed with them, yet) it could be implemented as function taking a sequence of edges (Sequence<E>
) and a returning sequence of edges (Sequence<E>
). It had to define method next()
instead which just returns next edge (equivalent of yield return
) or null (kindof yield break
) if no more edges can be found:


This algorithm will have similar interface (although there is no explicitly defined interface
) returning sequence of edges:


I called it Trailblazer
because it is not exactly a DepthFirst Search as it does not have backtracking. Backtracking in DFS is used to handle deadends (by branching), while in this hybrid algorithm branching is handled by Kruskal’s algorithm, so trailblazer is expected to just push forward.
There is a slight impedance between model used by Kruskal’s algorithm and Trailblazer, so the latter will use some helper methods to adapt:


it will need a function (edges
) which will provide sequence of edges going out of given node. It will need a set of already visited nodes (visited
) and current location (head
).
Edges in “Kruskal’s” model are just a pairs of nodes, while for Trailblazer direction is very important. Therefore we will need a method to find “opposite end” of an edge:


we will also need mark visited nodes and optionally move head
to newly visited one. This method will also return true
if node has been just added (meaning has not been visited before):


This does not look pretty, I have to admit, but it helped keep next
method quite short:


I actually like val current = head ?: return null
syntax. Kotlin allow you to put control statements like return
, break
and continue
in places where you would expect expressions, when it makes expression value irrelevant. In this case it will extract value from nullable head
and put it into current
, or it will exit this method returning null
immediately. It’s kindof “something or die()” in PHP.
After that, it takes all edges
going out of current
node and finds first which opposite
end has not been visited yet. So it is exactly like DFS, it just does not have backtracking.
Bind two algorithms together
These two (Kruskal and Trailblazer) algorithms will have to work together, and they need to expose some methods for communication.
First, Kruskal, needs to expose ability to merge node sets (it is the most important concepts in Kruskal’s algorithm, so if you don’t know what I’m talking about please refer to previous blogpost):


On the other side of the fence, Trailblazer algorithm will need to be restarted every time Kruskal jumps from one location to another:


That’s all we need.
Let’s do the Hybrid
algorithm now. It will use the same “interface”, of course:


On top of usual stuff (sequence of edges) it will also take random number generator (rng
) and a threshold
which will control how biased towards Trailblazer (0.0
) or Kruskal (1.0
) it will be.
It will also need a function returning outgoing edges for Trailblazer. Let’s start with building a dictionary (map) of all edges:


It goes through all edges
and for both ends (nodes A
and B
) adds this edge as outgoing (link
). So, the result
is a dictionary from nodes to list of edges (Map<N, List<E>>
). There might be an important question to ask here, if those lists need to be shuffled again, but I assume that input sequence was already shuffled, so shuffling already shuffled sequence does not increase its randomness. Although, in this case, there is a chance I’m completely wrong.
We can use this dictionary to define function needed by Trailblazer algorithm (see Trailblazer’s constructor):


All those question marks are to handle potential misses (and propagate nulls instead of throwing exceptions). So, what this function does is finds a node in dictionary and returns a sequence of edges incidental to this node or, in case node was not in dictionary, it return empty sequence.
Hybrid algorithm encapsulates both algorithms, original Kruskal
and Trailblazer
algorithms:


it also combines next
functions from both:


which means: try Trailblazer first, and if it fails, try Kruskal’s. If both of them failed then that’s it.
First let’s implement about nextTrailblazer
:


As you can see, it makes a call if it should use Trailblazer algorithm in this step at all. For example, if threshold
is set to 0.1
there is a 10% chance on every step that Trailblazer will stop and switch back to Kruskal. Therefore for threshold
set to 1.0
it would be working exactly like original Kruskal and Trailblazer’s step would never be executed. For threshold
set to 0.0
it would strongly prefer Trailblazer switching to Kruskal only when Trailblazer hit deadend.
If it decided to use Trailblazer and Trailblazer actually found an edge, both ends of this edge are added to Kruskal’s disjointset, making Kruskal’s part of the algorithm aware of this edge being returned.
On the other side, nextKruskal
is implemented as follows:


It takes next edge from Kruskal’s algorithm and if it succeeded, adds marks both ends as visited for Trailblazer algorithm and resets Trailblazer’s starting location.
The presentation layer
There is not really too much to do in presentation layer, there are two lines which have been modified. Actually, it’s still one line too much. If Kruskal
and Hybrid
implemented same interface from the start it would just one line, but adding interface now is a little bit too late  I just want to make it run. Anyway, it there was an interface it would be interface Sequencer<T> { fun next(): T? }
.
So, the lines we need to change:


Effect
It seems that it does exactly what I intended. That’s how it looks after few steps:
Conclusion
I really liked OCP in action. I mean, it did require one line to be added to Kruskal’s algorithm to make it work, but arguably merge
method should be exposed from the beginning or disjointset (sets
) should be injected into it. Anyway, Kruskal
class has been completely reused, and new algorithm (Hybrid
) composes Kruskal
and pseudoDFS (Trailblazer
) quite nicely. I could polish it a little bit, but I think it is goodenough.
Sources
You can find sources here or you can just use online demo