Skip to main content
Computer Science

Return to Question

deleted 898 characters in body
Source Link
user_758
user_758
  • 13
  • 3

A directed acyclic graph $G$ is confluent, if any two vertices ${v_1},{v_2}$ in $G$ which have a common ancestor $u$ also have a common successor $w$. (I.e. if there are paths from some $u$ to both ${v_1}$ and ${v_2}$, then there are also paths from ${v_1}$ and ${v_2}$ to some $w$. Vertices $u,{v_1},{v_2}$ and $w$ do not need to be distinct, thus e.g. a single "line" of vertices is trivially confluent) Design a linear-time algorithm that determines whether a given DAG $G$ is confluent.

Is the "line" with $3$ vertices $u \to v \to w$ s.t. ${v_1} = {v_2}$ trivially confluent? Or is it nesseccary to have ${v_1} \ne {v_2}$ and thus the smallest number of vertices such line may have is $4$ $u \to {v_1} \to {v_2} \to w$?

Since the algorithm must be linear my idea is to run DFS from each leaf following the in-degree neighbors and propagating leaf id to detect when a visited vertex with a set leaf id will try to overwrite it with another id different from the one it has, which implies that there are non-overlapping paths with different leaves passing through such vertex.

However, I don't know how to characterize the confluence condition in terms of the leaves. What could be other examples of non-confluent and confluent DAG, apart from the one where we have a directed path starting from some ancestor $u$ reaching node $s$ and then splitting into disjoint branches maintaining the orientation. Every such branch will host some vertices which will have a common ancestor $u$ reachable via vertex $s$ but since each such branch will lead to the leaf and since there is no path between these leavesEdit: Solved the confluency condition is brokenproblem.

A directed acyclic graph $G$ is confluent, if any two vertices ${v_1},{v_2}$ in $G$ which have a common ancestor $u$ also have a common successor $w$. (I.e. if there are paths from some $u$ to both ${v_1}$ and ${v_2}$, then there are also paths from ${v_1}$ and ${v_2}$ to some $w$. Vertices $u,{v_1},{v_2}$ and $w$ do not need to be distinct, thus e.g. a single "line" of vertices is trivially confluent) Design a linear-time algorithm that determines whether a given DAG $G$ is confluent.

Is the "line" with $3$ vertices $u \to v \to w$ s.t. ${v_1} = {v_2}$ trivially confluent? Or is it nesseccary to have ${v_1} \ne {v_2}$ and thus the smallest number of vertices such line may have is $4$ $u \to {v_1} \to {v_2} \to w$?

Since the algorithm must be linear my idea is to run DFS from each leaf following the in-degree neighbors and propagating leaf id to detect when a visited vertex with a set leaf id will try to overwrite it with another id different from the one it has, which implies that there are non-overlapping paths with different leaves passing through such vertex.

However, I don't know how to characterize the confluence condition in terms of the leaves. What could be other examples of non-confluent and confluent DAG, apart from the one where we have a directed path starting from some ancestor $u$ reaching node $s$ and then splitting into disjoint branches maintaining the orientation. Every such branch will host some vertices which will have a common ancestor $u$ reachable via vertex $s$ but since each such branch will lead to the leaf and since there is no path between these leaves the confluency condition is broken.

A directed acyclic graph $G$ is confluent, if any two vertices ${v_1},{v_2}$ in $G$ which have a common ancestor $u$ also have a common successor $w$. (I.e. if there are paths from some $u$ to both ${v_1}$ and ${v_2}$, then there are also paths from ${v_1}$ and ${v_2}$ to some $w$. Vertices $u,{v_1},{v_2}$ and $w$ do not need to be distinct, thus e.g. a single "line" of vertices is trivially confluent) Design a linear-time algorithm that determines whether a given DAG $G$ is confluent.

Is the "line" with $3$ vertices $u \to v \to w$ s.t. ${v_1} = {v_2}$ trivially confluent? Or is it nesseccary to have ${v_1} \ne {v_2}$ and thus the smallest number of vertices such line may have is $4$ $u \to {v_1} \to {v_2} \to w$?

Edit: Solved the problem.

Source Link
user_758
user_758
  • 13
  • 3

Confluent directed acyclic graph

A directed acyclic graph $G$ is confluent, if any two vertices ${v_1},{v_2}$ in $G$ which have a common ancestor $u$ also have a common successor $w$. (I.e. if there are paths from some $u$ to both ${v_1}$ and ${v_2}$, then there are also paths from ${v_1}$ and ${v_2}$ to some $w$. Vertices $u,{v_1},{v_2}$ and $w$ do not need to be distinct, thus e.g. a single "line" of vertices is trivially confluent) Design a linear-time algorithm that determines whether a given DAG $G$ is confluent.

Is the "line" with $3$ vertices $u \to v \to w$ s.t. ${v_1} = {v_2}$ trivially confluent? Or is it nesseccary to have ${v_1} \ne {v_2}$ and thus the smallest number of vertices such line may have is $4$ $u \to {v_1} \to {v_2} \to w$?

Since the algorithm must be linear my idea is to run DFS from each leaf following the in-degree neighbors and propagating leaf id to detect when a visited vertex with a set leaf id will try to overwrite it with another id different from the one it has, which implies that there are non-overlapping paths with different leaves passing through such vertex.

However, I don't know how to characterize the confluence condition in terms of the leaves. What could be other examples of non-confluent and confluent DAG, apart from the one where we have a directed path starting from some ancestor $u$ reaching node $s$ and then splitting into disjoint branches maintaining the orientation. Every such branch will host some vertices which will have a common ancestor $u$ reachable via vertex $s$ but since each such branch will lead to the leaf and since there is no path between these leaves the confluency condition is broken.