2
$\begingroup$

I have a graph with a set of vertices $\mathcal{V}$ and a set of edges $\mathcal{E}$. There exists a path between every 2 vertices in the graph. To each edge there is an associated weight $w(e), e \in \mathcal{E}$. I define a (global) threshold $T$ such that if $w((u,v)) < T$ the two vertices $u,v \in \mathcal{V}$ are in the same group: $g \in \mathcal{V} \rightarrow \mathbb{Z}, g(v_1) = g(v_2)$. This behaviour is transitive. The goal is to label the distinct groups starting from zero (the order of the groups is irrelevant). I know that this can be achieved trivially with BFS or DFS, but I want to avoid using those.

The idea I came up with is to iterate over the vertices, go over their 1-ring neighbourhood, and create a new group every time that $w((u,v)) < T$ for any of the edges and neither $u$ nor $v$ have been assigned a group (for example $g(u) = g(v) = -1$). Additionally, each group is assigned a label, which is initially equal to the index of the group: $h:\mathbb{N} \rightarrow \mathbb{N}, h(g(u)) = g(u)$. If at some point $w((x,y)) < T$ and $w((y,z)) < T$, but $g(x) \ne g(z)$ then set $h(g(x)) \leftarrow \min(h(g(x)),h(g(z))$ and $h(g(z)) \leftarrow h(g(x))$. After this procedure it should hold: $h(g(u))=h(g(v)), u,v \in \mathcal{V}$ if there exists a path from $u$ to $v$: $\pi = e_1,...,e_n$ such that $w(e_i) < T$. Is the algorithm I came up with correct or did I miss something? As it is currently it requires $|\mathcal{V}|$ memory for each array $g,h$. Is there a way to optimize this further?

$\endgroup$
4
  • 1
    $\begingroup$ This relationship is not transitive (contrary to what you wrote): if there is an edge $(a,b)$ with weight 3 and an edge $(b,c)$ with weight 3 and a threshold $T=4$, then your definition sets $a,b$ into the same group and $b,c$ into the same group but does not put $a,c$ into the same group. Can you clarify your problem statement? $\endgroup$ – D.W. Jul 11 '20 at 18:28
  • 1
    $\begingroup$ Your requirements are not clear. What's wrong with DFS? If you don't tell us why you rejected it, then I worry you might reject any other suggestions we might have too. If you rejected it probably there is some requirement you have that it does not meet; please take the opportunity to reflect on what that requirement might be. $\endgroup$ – D.W. Jul 11 '20 at 18:29
  • 1
    $\begingroup$ In the example you gave, $a$ and $c$ will be in the same group since there exists a path between $a$ and $c$ such that every edge on the path has a weight less than $T$. In fact thinking back on it, the problem formulation is equivalent to removing all edges with $w(e) \geq T$ and then finding all connected components of the new graph (which is a well-studied problem). I wanted to avoid DFS since I was thinking of the recursive formulation and wanted to avoid it. But I guess I can just rewrite it in an iterative fashion with an array of size $\mathcal{V}$ serving as stack, and an array of the $\endgroup$ – lightxbulb Jul 11 '20 at 20:42
  • $\begingroup$ @D.W. groups that can double as "visited" vertices array. Ultimately it boils down to the same memory and runtime, but my previous algorithm would have required sorting at the end (since I wanted to re-enumerated groups from zero), while DFS doesn't. Anyways, your question was actually very helpful, since I guess sometimes a person just needs someone else to ask him a basic question to realize something obvious (the formulation with removed edges). $\endgroup$ – lightxbulb Jul 11 '20 at 20:46
1
$\begingroup$

As you highlight in your comments, a reasonable approach is to delete all edges with weight $\ge T$, then compute the connected components of the resulting graph (using any standard algorithm for computing connected components).

$\endgroup$
0
$\begingroup$

I believe my algorithm is correct. A sketch of the proof is presented below:

There are 2 cases: either $u \ne v \in \mathcal{V}$ need to be from the same group, or they need to be from different groups (depending on whether there exists a path between them such that $w(e) < T, \forall e \in \pi$). It needs to be shown that the algorithm produces the resulting groups (the proof for each case will be done by contradiction).

  1. Case 1: Let $u,v \in \mathcal{V}$ and there is a path from $u$ to $v$: $\pi=e_1,...,e_n$ such that $w(e_i) < T$. Then $h(g(u))$ should equal $h(g(v))$ for the algorithm to be correct.

  2. Assumption of algorithm incorrectness: Assume that this is not the case, and that $u$, $v$ belong to different groups based on the result of the algorithm. For simplicity assume that $\pi = \pi_1,x,y,z,\pi_2;\, x,y,z\in \mathcal{V}$ such that all vertices from $\pi_1,x$ belong to $h(g(u))$ and all vertices on $y,z,\pi_2$ belong to $h(g(v))$ based on the algorithm. The case following the above assumption will be proven, but it should be clear that the same will hold by induction even if $\pi$ is split into more groups based on the algorithm.

Proof by contradiction: From (1), it follows $w(x,y)<T, w(y,z)<T$, and from (2) it follows: $h(g(x)) \ne h(g(z))$. From the definition of the algorithm it follows that it never splits groups, and it merges two groups if $w(x,y) < T, w(y,z)<T$ but $h(g(x)) \ne h(g(z))$. Since the algorithm goes over all edges it should have merged $h(g(x))$ and $h(g(z))$.

  1. Case 2: $u,v \in \mathcal{V}$ and there is no path $\pi$ from $u$ to $v$ such that $w(e) < T, \forall e \in \pi$, then $h(g(u)) = h(g(v))$.

  2. Assumption of algorithm incorrectness: Assume $h(g(u)) = h(g(v))$.

Proof by contradiction: Both at group creation and at group merging (the only two ways for vertices to end up in the same group) there needs to exist a path between $u$ and $v$ such that $w(e)<T, \forall e \in \pi$. (3) states that no such path exists, then $h(g(u)) \ne h(g(v))$.

Clearly the proof is fairly informal, so I may have missed something. I will leave the question open for a while, because 1) somebody may come up with a better & more optimized algoritm, and 2) I may have some mistake in my proof.

$\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.