2
$\begingroup$

My goal is to algorithmically take a list of relations between nodes (in other words, a list of undirected edges between nodes of a graph) and label each group of nodes such that all nodes that have a path between them have the same label (I believe the term for this is a "connected component") and nodes that do not have a path between them have different labels. Put another way, each connected component has a unique label.


NOTE: I haven't done all that much in the way of discrete math proofs since college, so hopefully you can bear with me and correct my terminology/methods if necessary.

To clarify, the data is in the form of a list of pairs of connected nodes.

For example:

n_1, n_3
n_3, n_5
n_5, n_7
n_5, n_9
n_2, n_4
n_4, n_6

In this <contrived> example, the odd-numbered nodes all belong to the same group, and the even-numbered nodes belong to another group.

I believe the way to do this is to process each item in the list according to the following rules:

  • Maintain an ordered list (call it "encounteredNodes") of all encountered nodes and the group label they have been assigned to
  • Maintain an integer variable (call it "nextLabel") that is incremented and returned each time a new unique label is needed
  • For each item in the list, determine if either node has been encountered yet.
    • If neither node has been encountered, get a new unique label from nextLabel and add both the nodes to encounteredNodes with this new uniqueLabel
    • If one node has been encountered but not the other, assign the label of the previously-encountered node to that of the unencountered node.
    • If both nodes have been previously encountered, take the lesser label of the two and use it to replace the label of all nodes in encounteredLabels that have the greater label of the two.

After one pass of this "for loop" through all the nodes, the algorithm is complete and the nodes have been grouped according to the goal. I believe the proof can be shown in this way:

Lemma 1: None of the operations can result in 2 previously encountered nodes that already have the same label being assigned to different labels. Because of this, already encountered nodes never "split off" from their group of nodes with the same labels, and once two nodes have the same label, they will never have differing labels (though they may change together to the same new label) for the remainder of the algorithm.

Assume there are two nodes that have a path between them via the list of edges, yet after the algorithm finishes, they have different labels (call them $L_1$ and $L_2$. If that's the case, then either...

  1. They each contain a node (and these two nodes are directly connected), or...
  2. there is a "chain" formed of groups of nodes where each group has the same label and the chain can be traversed to get from $L_1$ to $L_2$.

However neither of these scenarios can occur based on the algorithm. In the case of 1, there would have to have been a pair of connected nodes in the list where one node belongs to $L_1$ and one node belongs to $L_2$. However, after the algorithm processed this connection, both nodes would have the same label, and because of Lemma 1, they would have the same label until the end of the algorithm. In the case of 2, the neighbouring links in the chain could not exist because of the first case. Thus. This is a proof by contradiction.

Is this all sound? Also, I was never that great at algorithm runtime calculations, but I think it would be $O(n \log{n})$ because iterating the list of connections is linear time, but each iteration requires a search of ordered lists. Is this correct?

$\endgroup$
  • 1
    $\begingroup$ Your question is very long and I admit that I didn't read it all. But, if you're trying to compute the connected components of a graph, there are well-known algorithms for doing that and well-known proofs that they work. I suggest you search for those rather than trying to roll your own. $\endgroup$ – David Richerby Aug 18 '16 at 8:30
  • 1
    $\begingroup$ You seem to have rediscovered this algorithm $\endgroup$ – adrianN Aug 18 '16 at 9:18
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Aug 18 '16 at 10:46
  • $\begingroup$ @adrianN Do you have a better reference than a post on Stack Overflow? $\endgroup$ – Raphael Aug 18 '16 at 10:46
  • $\begingroup$ @Raphael perhaps the first few of these slides? $\endgroup$ – adrianN Aug 18 '16 at 11:28
2
$\begingroup$

You should look into DFS and BFS, which can solve this problem in $O(n+m)$ time where $n$ is the number of nodes and $m$ is the number of edges.

The performance of the algorithm you described is much worse than you think, because you potentially have to relabel nodes many times. Consider the edges presented in this order:

$v_{2k},v_{2k+1}$

$\vdots$

$v_2, v_3$

$v_0, v_1$

$v_{2k}, v_{2k-1}$

$\vdots$

$v_3, v_4$

$v_2, v_1$

The introduction of the edge $v_{2k}, v_{2k-1}$ requires relabeling $v_{2k}$ and $v_{2k+1}$, introducing $v_{2k-2}, v_{2k-3}$ requires relabeling $v_{2k-2}, v_{2k-1}, v_{2k}$ and $v_{2k+1}$. Finally, introducing $v_2,v_1$ requires relabeling $v_2,\ldots,v_{2k+1}$. This ends up being quadratic in $n+m$.

The idea behind your algorithm is somewhat valid though, and you can implement it much more efficiently using the Union-Find data structure which, if you will, can "defer" the relabeling.

$\endgroup$
1
$\begingroup$

Your bound is right, but there is faster.

This question looks to be implementing the Disjoint-set algorithm. The fastest algorithm for doing this is actually virtually linear. It uses a different data structure that flattens the groups out more efficiently so that you don't have to update as much when merging groups.

I wont repeat the algorithm here, but I will point out that it's actual time bound is $O(\alpha(n))$ where $\alpha(x) = A(x, x)$ and $A$ is the inverse Ackermann function. I mention it because the Ackermann function is a particularly fun sequence to look at. It grows really really really really fast.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.