How to obtain isomorphic subgraphs rather than subgraph isomorphism mappings?

[lichengzhang1]

I am considering an example: finding all isomorphic copies of the claw $K_{1,3}$ as subgraphs in the complete multipartite graph $K_{2,2,2,2}$, and, of course, counting their number.

claw:

4
3 1 2 3
1 0
1 0
1 0

$K_{2,2,2,2}$

8
6	2	3	4	5	6	7
6	2	3	4	5	6	7
6	0	1	4	5	6	7
6	0	1	4	5	6	7
6	0	1	2	3	6	7
6	0	1	2	3	6	7
6	0	1	2	3	4	5
6	0	1	2	3	4	5

Using Mathematica, we know that there are a total of 160 such subgraphs. (FindIsomorphicSubgraph[CompleteGraph[{2, ,2,2,2}], CompleteGraph[{1, 3}], All])

I obtained 960 subgraph isomorphisms using ./build/glasgow_subgraph_solver --format lad --count-solutions --print-all-solutions --parallel claw K2222>sol.txt And we will see: solution_count = 960

I believe that there are mappings correspond to some subgraphs that are the same. I want to obtain all the distinct subgraphs that are different from each other.

But how to do?

[ciaranm]

Currently there's no specific way of finding "unlabelled" isomorphisms, so your best bet is to count all solutions, and then divide by the size of the automorphism group of the pattern graph.

If you happen to have the GAP computer algebra package installed, then you can use the --pattern-symmetries command line argument, but this will have a large startup cost and might not make things faster at all. In the long term, we have plans to switch to the DejaVu library for symmetry handling.