Dynamic connectivity with Ruby

Maze

The dynamic connectivity problem is about finding a path between two objects in a graph.

This article is written as my notes taken from the Algorithms course by Robert Sedgewick, but using Ruby for the examples.

Looking at the image, finding quickly a path between p and q is too complex for a human, but a computer algorithm could find it in a matter of seconds.

This has many applications, such as pixels in a digital photo, computers in a network, friends in a social network, or variable names in a computer program, to name a few.

We will use the union-find algorithm to solve this problem. As its name states, the only two things it does is to connect two objects (union) and to find a path between them (find). It does not provide the path as such, only the existence of the asked connection.

It does not matter what objects we use, so we will use numbers for simplicity.

Overview

So for 10 objects, we apply these union commands:

 

And we end up with this graph:

Graph 1

Now if we ask for these connections:

Even if objects 8 and 9 are not directly connected, the algorithm can follow the path between them to see that they indeed are.

Let’s build more connections:

And the graph now looks like this:

Graph 2

We can query the algorithm for a more complex path:

How can we implement this algorithm? The most simple way is by using integers as an array index. Since the name for each object is also an integer, it will be much easier to access the information.

Modeling the connections

What kind of connections can we find?

  • Reflexive: p is connected to itself.
  • Symmetric: p is connected to q, and vice versa.
  • Transitive: if p is connected to q and q is connected to r, then p is connected to r.

As a group of connections we have the concept of component: a set of objects mutually connected. Example:

Graph 3

So we have 3 components here:

Implementing the operations

We have two operations:

  • Find query: check if two objects are in the same component
  • Union command: replace components containing two objects with their union

So if we apply this union command to the previous graph:

We will create a connection between 2 and 5:

Graph 4

So we have now two components:

Dynamic connectivity client

To use the algorithm we will implement this client:

We can send this file:

So pairs that are already connected will not be printed after running the program.

First implementation: Quick-find (eager approach)

We will build a first implementation using the quick-find algorithm, which is an eager approach.

It uses an array of integers as the data structure, having the objects as the values. In this data structure, p and q are connected if they both have the same id.

For instance, to represent this graph:

Graph 5

We use this array:

Array 1

Now it’s easy to check connections:

  • 0, 5 and 6 are connected, because they have the value 0
  • 1, 2 and 7 are also connected, because they have the value 1
  • The rest is connected using the value 8

What if we want to make an union of 6 and 1? They belong to different components, so we have to merge them changing all entries whose id equals ids[p] to ids[q]. So we will change all objects in the same component 6 is to the value of 1:

Array 2

This can be very time consuming, because a lot of values can change, but as a benefit it is easy to implement.

Let’s go for the implementation.

 

Notes:

  • We use a simple array (ids) to support the implementation. The constructor will initialize it using sequential numbers.
  • The connected? method is the actual find operation. It just checks if the objects have the same value in the array.
  • The union method iterates over the array comparing the current value to p_id, and applying q_id if they equal.

Since the union method has to go through the entire array, it is expensive. The worst case would imply having N union commands on N objects, and that would take quadratic time in squared time, which is unacceptable for large problems, because it will not scale (a faster computer will have a bigger memory but the algorithm would be much slower).

In a future article about dynamic connectivity, I will improve the union method.

Did you like it? Please share it:

Get my ebook for free

10 ideas that helped me become a better developer (and may help you too)

Subscribe to my mailing list and get my ebook on 10 ideas that helped me become a better developer.

About Me

David Morales

David Morales

I'm David Morales, a computer engineer from Barcelona, working on projects using Ruby on Rails and training on web technologies.

Learn More