0 like 0 dislike
29 views
What is a causal (topological) ordering?
| 29 views

0 like 0 dislike
Given a $D A G \mathcal{G}$, we call a permutation, that is, a bijective mapping,
$\pi:\{1, \ldots, p\} \rightarrow\{1, \ldots, p\},$
a causal ordering (sometimes one says topological ordering) if it satisfies
$\pi(i)<\pi(j) \text { if } j \in \mathbf{D E}_i^{\mathcal{G}} .$
Because of the acyclic structure of the DAG, there is always a topological ordering. But this order does not have to be unique. The node $\pi^{-1}(1)$ does not have any parents and is therefore a source node, and $\pi^{-1}(p)$ does not have any descendants and is thus a sink node.
by Platinum (141,884 points)

0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
1 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
1 like 0 dislike
0 like 0 dislike
1 like 0 dislike
0 like 0 dislike
0 like 0 dislike