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:

1 2 3 4 5 | union 4, 3 union 3, 8 union 6, 5 union 9, 4 union 2, 1 |

And we end up with this graph:

Now if we ask for these connections:

1 2 | connected? 0, 7 # false connected? 8, 9 # true |

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:

1 2 3 4 | union 5, 0 union 7, 2 union 6, 1 union 1, 0 |

And the graph now looks like this:

We can query the algorithm for a more complex path:

1 | connected? 0, 7 # true |

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:

So we have 3 components here:

1 2 3 | { 0 } # as a reflexive connection { 1 4 5 } # we find symmetric connections here { 2 3 6 7 } # symmetric and transitive connections |

## 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:

1 | union 2, 5 |

We will create a connection between 2 and 5:

So we have now two components:

1 2 | { 0 } { 1 2 3 4 5 6 7 } |

### Dynamic connectivity client

To use the algorithm we will implement this client:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | # read in number of objects N from standard input n = gets.to_i uf = UF.new(n) # read repeatedly in pair of integers from standard input while input = gets do values = input.split ' ' p = values[0].to_i q = values[1].to_i # unless connected, connect them and print out pair unless uf.connected? p, q uf.union p, q puts "#{p} #{q}" end end |

We can send this file:

1 2 3 4 5 6 7 8 9 10 11 12 | 10 4 3 3 8 6 5 9 4 2 1 8 9 <-- already connected 5 0 7 2 6 1 1 0 <-- already connected 6 7 <-- already connected |

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:

We use this array:

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:

1 | union 6, 1 |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | # Quick-find (union find) class QuickFindUF attr_reader :ids # build the data structure def initialize(n) @ids = Array.new(n) # set id of each object to itself (N array access) @ids.map!.with_index { |id, index| index } end # check whether p and q are in the same component (2 array accesses) def connected?(p, q) ids[p] == ids[q] end def union(p, q) p_id = ids[p] q_id = ids[q] ids.map! { |id| id == p_id ? q_id : id } end end |

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.