Given any complete directed weighted graph $G$ with $n$ vertices and matrix of non-unique weights $W$, find a weak ordering $T(G, W)$ on the vertices of the graph satisfying the following conditions:
$T(G, W)$ is invariant under permuting the vertices
For any two vertices $u$ and $v$, $u = v$ in $T$ if and only if there is some automorphism $f:V(G) \rightarrow V(G)\ $ such that $f(u) = v$ and $f(v) = u$
The reason I want such a thing is to have some consistent but arbitrary way to order the vertices of a graph that is invariant under permutation, as a tie-breaker for more meaningful orderings, when the vertices are actually distinct, which will usually be the case. If two vertices cannot be distinguished, picking whichever one happens to be first in my representation is fine.
I expect this problem is in $NP$, as it seems like there's some way to compute graph isomorphisms with it, but my graphs are small and I can precompute the ordering once, so it would still be useful to figure out how to do it.