4
$\begingroup$

Is there a way of generating random isomorphic graphs for the purposes of testing tools like Nauty or BLISS? Every paper I've found says the authors had a database of certain isomorphic graphs, but I don't know how they constructed them or where I find test sets for graph isomorphism algorithms. I expect the answer to this question is no.

Is there a way to generate graphs that are likely to be isomorphic?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$
  1. create a graph $G = (V, E)$ as you like
  2. generate a random permutation $\sigma\in \mathfrak{S}(V)$, for example with Knuth's algorithm
  3. create the graph $G' = (V, E')$ where $E' = \{(\sigma(u), \sigma(v))\mid (u, v)\in E\}$
  4. Tada! $G$ and $G'$ are isomorphic!
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ You can also use this approach to create a graph pair which is almost isomorphic, by introducing small errors in the permutation. $\endgroup$
    – Discrete lizard ♦
    Jan 5, 2022 at 8:17
4
$\begingroup$

While Nathaniel's response answered my question perfectly, part of my question also asked about where to find testsets for graph isomorphism algorithms. As such, I thought I'd start a list.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.