Weisfeiler-Leman.tex (904B)
1 \begin{algorithmic} 2 \Function{Weisfeiler--Leman}{} 3 \FunctionInputs{} \(G=(V, E)\) graph 4 \FunctionInputs*{} \(k\) dimensionality 5 \FunctionOutput{} \(\chi_\infty\) coloring of \(k\)-tuples 6 \State 7 \LComment{Initialization} 8 \State \(\ell\gets 0\) 9 \ForAll{\(\vctr{x}\in V^k\)} 10 \State \(\chi_0(\vctr{x}) \gets \operatorname{iso}(\vctr{x})\) 11 \EndFor 12 \LComment{Main Loop} 13 \Repeat 14 \State \(\ell\gets \ell+1\) 15 \State \(\symfrak{I}_\ell\gets \text{new color index}\) 16 \ForAll{\(\vctr{x}\in V^k\)} 17 \State \(c_\ell(\vctr{x}) \gets \lMultiBrace\,\chi_{\ell-1}(\vctr{y}) \middlerel{|} \vctr{y}\in\gfneighbors^k(\vctr{x})\,\rMultiBrace\) 18 \State \(\chi_\ell(\vctr{x}) \gets \text{index of }(\chi_{\ell-1}(\vctr{x}), c_\ell(\vctr{x})) \text{ in } \symfrak{I}_\ell\) 19 \EndFor 20 \Until{\(\chi_\ell = \chi_{\ell-1}\)} 21 \State \Output \(\chi_\ell\) 22 \EndFunction 23 \end{algorithmic}