1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Yes, the "line" $u \to v \to w$ is trivially confluent, and so are the empty graph, the graph with a single node, and the "line" $u \to w$. In the case of a graph with a single node $v$ there is only one case to consider, with $v_1 = v_2 = v$. The common ancestor is then $v$ itself, and the common successor is also $v$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Any examples of non-confluent DAG? $\endgroup$
    – user_758
    Commented May 16, 2018 at 9:09
  • 1
    $\begingroup$ Take any non-trivial tree oriented toward the leaves! For example $u \leftarrow v \rightarrow w$. Here $u$ and $w$ have $v$ as a common ancestor, and no common successor since they are leaves. $\endgroup$
    – Rodolphe Lepigre
    Commented May 16, 2018 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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