Digraph vertices: classification by counting outgoing walks
Let $A$ be the adjacency matrix of the graph, let $\mathbf 1$ be the all-ones vector, and let $\delta_v$ be the indicator of vertex $v$. Then
$$
W_v(t) = \delta_v A^t \mathbf 1.
$$
It follows that $v \sim u$ iff for all $t$,
$$
(\delta_u - \delta_v) A^t \mathbf 1 = 0.
$$
Let $n = |V|$. The Cayley–Hamilton theorem shows $A^t$ is always a linear combination of $A^0,\ldots,A^{n-1}$. Therefore
$$
v \sim u \Longleftrightarrow (\delta_u - \delta_v) A^0 \mathbf{1} = \cdots = (\delta_u - \delta_v) A^{n-1} \mathbf{1} = 0.
$$
The latter property can be checked in polynomial time, so the partition can be computed in polynomial time. This procedure can be optimized by computing the kernel of the matrix
$$
\begin{bmatrix}
A^0 \mathbf{1} \\
\cdots \\
A^{n-1} \mathbf{1}
\end{bmatrix}
$$
and then finding all $\delta_u-\delta_v$ that belong to it.