Union Find Algorithm

article

Is there a path between A and B?

Tags: Grid Graph Reachability Union Find Coursera  Java 2015 

1Introduction

I encounterd this useful algorithm during a course at coursera.org. It has many applications, and I hope this article is useful to you.

Consider a pathfinding problem on a undirected grid graph. We want to get from (A) to (B). It would be nice to check if a path exists at all, before launching any time-consuming attempts.

We don't need the path itself, just an answer to the question:

grid graph reachability

Is B reachable from A?

There is a simple, fast and beautiful algorithm with great scalability that answers this question, called: Union-Find


2Resources

This algorithm is part of a course given Kevin Wayne & Robert Sedgewick from Princeton University.
You can follow this course for FREE at

COURSERA - Algorithms Part I

Union Find explained - a must read

Union-Find Java example code:

BitBucket Repository

3Usage example

To investigate two points, (A) and (B), on a grid graph.

  1. Construct a "grid" of nodes
  2. Connect each node with it's neighbors, if the path is not blocked between them
  3. Query reachability

The Union-Find code example is able to tell wether 2 nodes are connected. Either directly or through neighbours.

Write a class that instantiates a Union-Finder. Make room for N nodes, where

N = length x width
.

1) Visualise the node ordering like follows:

Node order

2) Connect nodes using the union method, use ID's considering the ordering above. To make a vertical connection between node-3 and node-10:

EXAMPLE
finderInstance.union(3, 10);

 

3) Query reachabillity between (A) and (B) through the command

finderInstance.connected(idA, idB);


4Further reading and thoughts

The above algorithm is more specifically called:"Weighted quick-union with path compression". The amortized cost [?] per operation for this algorithm is known to be bounded by a function known as the inverse Ackermann function and is less than 5 for any conceivable practical values of N.

 

Alternatives

An alternative solution is given in the paper "Optimal decremental connectivity in planar graphs", by Jakub Łącki, Piotr Sankowski. Which is said to run in constant time per query/operation. PDF download is at the right. Anyone tried this? Please let us know in the comments below.

 

Application in Vector Racer

The above can be applied to VectorRacer as well. For instance: to check if a track is valid before computing AI paths.

Consider the car accelerating and then immediatly braking each time. Moving 1 position and then comming to a full stop.
This stop-and-go driving removes the momentum from the equation and simplifies to the above grid graph problem.

You wouldn't be fast riding like this, but for that we have different algorithms :)