Dynamic Connectivity Problem

Pixels in a digital photo, Computers in a network, People on a social network are all connected objects.

OMAR ELGABRY
Jan 5, 2017 · 7 min read
Connected Objects

Given a set of N objects, connect two objects, or ask if two objects are connected (directly or in-directly).

The problem is to be able to implement two commands; union and connected.

union(2, 5)        // connect object 2 with object 5
connected(1 , 6) // is object 1 connected to object 6?

Connection Properties

  • Reflexive →p is connected to p.
  • Symmetric →If p is connected to q, then q is connected to p.
  • Transitive →If p is connected to q, and q is connected to r, then p is connected to r.

Implementing The Operations

  • Connected: Are objects p and q in the same component?
  • Union: Connect two components containing objects p and q (if not already).
Union-Find — algs4.cs.princeton.edu

Connected components are subsets, each consists of connected objects.

Union-Find Data Type

It can be implemented by several different algorithms. We are going to explore two algorithms; Quick Find & Quick Union.

Quick Find

Initialize

for (int i = 0; i < n; i++)
id[i] = i; // set id of the object at index i

Union

if (pID == qID) return;   // already connected?for (int i = 0; i < id.length; i++)
if (id[i] == pID)
id[i] = qID;
Quick Find

Connected

return id[p] == id[q];

Analyzing

  • Initialize & Union →O(N)
  • Connected→O(1)

Quick Union

Initialize

Now, we can imagine the data structure consists of trees, each tree has connected objects, and, trees mightn’t be connected together.

for (int i = 0; i < n; i++)
parent[i] = i; // set parent of the object at index i

Root

while (p != parent[p])
p = parent[p];
return p;

Union

int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) return; // already connected?
parent[rootP] = rootQ;
Quick Union

Connected

return root(p) == root(q);

Analyzing

  • Initialize & Union & Connected → O(N).

Quick Union Improvements

1. Weighted Quick Union

Weighted Quick Union— algs4.cs.princeton.edu

We will add an extra array denotes the size(or depth) of the subtree formed by each node.

// union by size (initially size[i] = 1)
if (size[rootP] < size[rootQ]) {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
// union by depth (initially depth[i] = 0)
if (depth[rootP] < depth[rootQ])
parent[rootP] = rootQ;
else if (depth[rootP] > depth[rootQ])
parent[rootQ] = rootP;
else {
parent[rootQ] = rootP;
depth[rootP]++;
}

Analyzing

Proof: When T1 is merged to T2, where T1 ≤T2, the depth of T1 will increase by 1. Now, the depth of T2(after merging) will increase by 1 if merged with T3, where T3 ≥ T2. So, every time, we need a tree X ≥ tree Y, to increase the depth of tree Y by 1. Therefore, the size of T1 can increase at most LogN.

  • Union & Connected→O(LogN)

2. Path Compression

Path Compression — algs4.cs.princeton.edu

This will decrease number of steps to get to the root object from the current object.

// path compression by linking to the root
int root = p;
while (root != parent[root])
root = parent[root];
while (p != root) {
int newp = parent[p];
parent[p] = root;
p = newp;
}
// path compression by linking to grandparent(halving the depth)
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}

Analyzing

  • Union & Connected→O(LogN) (amortized)

Summary

  • Quick Union → O(N).
  • Weighted Quick Union →O(LogN).
  • Quick Union and Path Compression → O(LogN) (amortized).
  • Weighted Quick Union with Path Compression → O(Log*N) (amortized).

Log*N is the iterated logarithm of N, usually read “log star”.

Other Related Problems (Percolation)

The percolation problem is given a grid of N x N elements, colored with white if open, blue if connected to any element at top row, and black if closed. Is the system percolates?. In other words, Is the top row is connected to the bottom row through open elements?.

Percolation problem shows up in electricity, fluid flow, social interactions, many other.

Percolation — introcs.cs.princeton.edu

With a grid of N x N elements, to check if any element at the first row connected with any element at the bottom. This will require N² calls to connected command.

The trick we can use is to connect all elements on the first row to a “virtual” element, and we will do the same thing for all the elements at the bottom row.

Percolation — introcs.cs.princeton.edu

Now, to know if the system percolates, we check if the virtual element at the top is connected to that at the bottom. So, it’s a more efficient algorithm since it only requires one call to connected command.

Watch out for this bug!

Now, whenever another element B at the bottom row gets opened, it will be also colored with blue, Why? Since it’s also connected to element A(through the virtual bottom element), which in turn connected to the top virtual node.

Percolation — introcs.cs.princeton.edu

Solutions

Or, use one grid with only top virtual element, and whenever we open an element at the last row, and it’s connected to any node at the top, mark the system as percolates.

OmarElGabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

OMAR ELGABRY

Written by

Software Engineer. Going to the moon 🌑. When I die, turn my blog into a story.

OmarElGabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade