I have some code that works with simple directed graphs, but it is kinda slow.
So I converted it to use an adjacency matrix instead of keeping a list of pairs of nodes.
The code finds the equivalence classes of graphs (see here and here) by permuting the names of the nodes in the list of pairs. This works but is slow.
I was thinking one could use a permutation matrix to permute the nodes. So I tried to use p*m*p (where p is the permutation matrix and m is the adjacency matrix). This does not work very well as it seems to map edge 0->1 to 0->0.
Is there an easy way to permute the nodes of an adjacency matrix?
Let P be a permutation matrix such that $[x_1, ... x_n]P=[x_{\sigma^{-1}(1)},...,x_{\sigma^{-1}(n)}],$ where $\sigma$ is a permutation - that is, each row vector is sent to the one with $\sigma(i)^\text{th}$ component the original $i^\text{th}$ component. Then, treating a matrix $A$ as a row vector, $A_{ij}=(AP)_{i\sigma(j)}=(AP)^T_{\sigma(j)i},$ so $(PAP^T)_{\sigma(i)\sigma(j)}=((A^TP)^TP)_{\sigma(i)\sigma(j)}=(A^TP)^T_{\sigma(i)j}=(A^TP)_{j\sigma(i)}=A^T_{ji}=A_{ij}$. Therefore $PAP^T$ re-indexes $A$ by a permutation $\sigma$ of the indices, as required.
Since re-indexing the identity matrix's indices leaves it unchanged, a corollary is that $PP^T=\operatorname{id},$ so that $PAP^T=PAP^{-1}$ is similar to $A$.