patternMinor
Generating Isomorphic Graphs
Viewed 0 times
generatinggraphsisomorphic
Problem
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?
Is there a way to generate graphs that are likely to be isomorphic?
Solution
- create a graph $G = (V, E)$ as you like
- generate a random permutation $\sigma\in \mathfrak{S}(V)$, for example with Knuth's algorithm
- create the graph $G' = (V, E')$ where $E' = \{(\sigma(u), \sigma(v))\mid (u, v)\in E\}$
- Tada! $G$ and $G'$ are isomorphic!
Context
StackExchange Computer Science Q#147892, answer score: 7
Revisions (0)
No revisions yet.