Dynamic Connectivity Problem: Explained

Explained: Dynamic Connectivity Problem
Explained: Dynamic Connectivity Problem

According to Wikipedia, in computing and graph theory, a dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph.

Introduction

In other words, a Dynamic connectivity Problem is a problem in which we have to find there is a connected path or not for an object.

union_find
Image Source: Case Study: Union-Find (princeton.edu)

The set V of vertices of the graph is fixed, but the set E of edges can change. The three cases, in order of difficulty, are:

  • Edges are only added to the graph (this can be called incremental connectivity)
  • Edges are only deleted from the graph (this can be called decremental connectivity)
  • Edges can be either added or deleted (this can be called fully dynamic connectivity)

What is Dynamic Connectivity?

Given an initially empty graph G on N nodes.

There are M queries of the following forms:

  • Add an edge connecting some of the nodes
  • Remove an edge connection to some of the nodes (provided that it exists)
  • Find the number of the connected components in the graph; check whether there’s a path between two given nodes; find the size of the connected component containing the given node; etc

There is a number of real-world applications where the dynamic connectivity problem is applicable. From Friends in a social network, pixels in a digital photo, computers on a network, web pages on the internet, transistors on a computer chip, or variable name equivalents (different variables pointing to the same object), Metallic sites in a composite system, variable names in Fortran program, Elements in a mathematical set are all examples of dynamic connectivity.

Example:

There are the following Seven objects.

BL_BLOGPOST
Image Source: BP Blogspot

Union commands on two objects will take or join all the objects without any duplicate elements if any.
Following union command will apply on these objects:

  • union(1,3)
  • union(2,4)
  • union(6,7)
  • union(0,1)
  • union(5,7)
  • union(4,5)

And then object connectivity will become:

BP_BLOGPOST
Image Source: BP Blogspot

Now connected commands would work as:
connected(0,3) true
connected(2,7) true
connected(0,2) false

Establishing a problem model:

Given a collection/group of N objects. The basic operations which are required for the problem, in general, are given as follows:

  • Union: Connect between two objects
  • (Find/connected) The query of connectivity: Query to find out whether there is a connected path between two objects

From the following figure is clearly visible that the Union(x,y) command is used to establish a connection path between several objects; use the connected (x,y) command to check whether two objects are connected.

BP_BLOGSPOT
Image Source: BP Blogspot

Basically, our motive for solving is to efficiently implement these two commands for a given set of objects. Because the one thing to note is that the merge command and the connect command are cross-mixed, we also have a task that our solution can support the efficient processing of a huge number of objects and a large number of hybrid operations.

Now to solve this problem the following two approaches are given below:

  1. Quick Find:-  A simple object index integer array id[](size = n) (Consider the case when two objects p and q are the same id in the array, then they are connected).

Figure: Element 0, 5, 6 in a connected component; 1, 2, 7 in a connected component; 3, 4, 8, 9 connected.

QUICK_FIND

Here is a brief overview of how this quick-find works.

BP_BLOGSPOT

Find: Find the id of p or q

Union: Merging/joining the two connected components of two given objects, i.e. altering the id value of all objects with the same id as one of the given objects (p) to the id value of another given object (q)

As shown in union(6,1)By combining the id values ​​of all objects (0, 5, 6) in the connected components where 6 and 1, 6 are located, the id value of 1 becomes (1). The main issue with this algorithm is that when the merge operation takes place then the more operations that need to be changed the id value afterward.

ID_BP

Here is java implementation for the same:

public class QuickFindUF
{
    private int[] id;
         / / Create a privatized integer array, and set the index item of the corresponding index as an index value
    public QuickFindUF(int Number)
    {
        id = new int[Number];
        for (int i = 0; i < Number; i++)
        id[i] = i;
    }
 //Connected judgment: whether the id values of two array items are equal
    public boolean connected(int p, int q)
    { return id[p] == id[q]; }
//Merge operation: Take the id value of the two parameters, traverse the entire array, find the id item with the same value of the first parameter id, and then finally assign all the values to the id value of the second parameter.
    public void union(int p, int q)
    {
        int pid = id[p];
        int qid = id[q];
        int n= id.length
        for (int i = 0; i < n; i++)
        if (id[i] == pid) id[i] = qid;
    }
}  
  1. Quick -Union [Lazy approach]:-  Quick lookups are too slow to handle huge problems, so the first attempt is to replace them with a fast merge algorithm. The algorithm for fast merging uses “lazy strategy”, which is basically used to avoid calculations until it has to be calculated. 

The array here is treated like a jungle (like a collection of trees), and each item present in the array contains its parent node in the tree.

The given figure below it is clearly showing that the parent node of 3 is 4, the parent node of 4 is 9, and the parent node of element 9 is itself, that is, element 9 is the parent of the tree. Starting from an object, you can look for the root node all the way starting from the parent node. • Root of i is id[id[id[…id[i]…]]] keep going until it doesn’t change.

I_D
BP_BLOGSPOT

Thus,

Find: Here we will find the root node of p or q (root)

Union: joins the connected components of two objects which ultimately sets the value of the root node of p to the value of the root node of q.

As shown in the figure, when we take union(3,5) is the id value of the root node (6) whose id value of the root node (9) of 3 is set to 5. Thus, the connected component where 3 is located is merged with the connected component where 5 is found.

BP_BLOGSPOT
MERGED_ARRAY

From the above scenario, we go to know that merging two connected components only needs to be changed one value in the array, but searching the root node will require more operations.

Here is a quick overview of the quick-union algorithm:

UNION_ALGORITHUM

Here is the java implementation for the same:

public class QuickUnionUF
{
    private int[] id;
    //The constructor is the same as Quick-find
    public QuickUnionUF(int N)
    {
        id = new int[N];
        for (int i = 0; i < N; i++) id[i] = i;
    }
 // Private method root () through the backtracking implementation to find the root node
    private int root(int i)
    {
        while (i != id[i]) i = id[i];
        return i;
    }
// Through the private method to achieve the lookup operation (whether connected operations). Return by finding if the root nodes of the two objects are the same
    public boolean connected(int p, int q)
    {
        return root(p) == root(q);
    }
// Merge operation is so that we are able to find out the root node of the two objects, and set the id value of the first root node to second object
    public void union(int p, int q)
    {
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }
} 

Performance Analysis:-

1. Quick- find

One thing to note down in Quick-find is that both the initialization of the constructor and the merge operation need to traverse the entire array, so they must access the array with a constant which is directly proportional to N times (growth magnitude is N). The search operation is very fast, only need to make a constant comparison (the growth level is 1)

The one major characteristic of the algorithm is that the search is really very fast, but the cost of the merge is too large. If it is required or needed to perform N merge operations on N objects, accessing the array needs an operation of increasing the order of magnitude of N, which is unreasonable. The magnitude of the square is too slow. As we too know that Square time algorithms are not accepted for large problems as they will give you the worst error of your life i.e. T.L.E (Time Limit Exceeded).

As computers get faster, the square-time algorithm gets really slow. Always think that if computers can execute billions of operations per second, there are billions of items in their main memory, about a second. The fast search algorithm will be required to access the array about 10 times of 18 times, which is almost equal to 30 years of time needed for computing.

2. Quick- Union

One important thing about the Quick-find algorithm is that it may take ~MN steps to process M union command/operations on N objects

One thing to note is that the algorithm for the fast merge is slow. There could be a disadvantage of fast lookups like the tree may be too high, which costs too much for the lookup operations required, and the worst-case requires N times the whole group access to find the root node of an object.

COKPLEXITY_NUMBERS

Now here this thing forces us to think that can we improve it? Let’s leave this question to you and see maybe if you could find a better approach to optimize it because we all know one thing that finding a solution to the problem is not enough but also optimizing it is also necessary.

Frequently Asked Questions

1. What are some real life examples of dynamic connectivity problem?

People on the social media platforms, pixels in photos, computers in the network (LAN/WAN) are connected objects.

2. What is the goal of quick find and quick union algorithm?

To find if any elements are connected and if not then connect them.

3. Which algorithm out of two is based on lazy approach?

Quick Union

Conclusion

From Dynamic Connectivity Problem, we get to know we are connected in real-world like in Facebook friends.

If you didn’t get in detail about how this quick-union or quick-find is working then you’ll need a basic understanding of the disjoint-set data structure. Read here Explained: Disjoint-Set Data Structure | Coding Ninjas Blog and Learning Disjoint Set Union (Union Find) | Coding Ninjas Blog it’ll help you in building basics.

By Yogesh Kumar