Digraphs Subgraph isomorphism solving?

I believe digraphs doesn't currently do subgraph isomorphism.

Probably the best open source subgraph isomorphism solver around is https://github.com/ciaranm/glasgow-subgraph-solver . I was wanting to use it from GAP, but I wondered if digraphs would be a good place for it to live.

One minor problem -- it does require C++20, is that more than digraphs currently requires / wants to require?

Oct 18 '22 15:10 ChrisJefferson

Thanks for the comments @ChrisJefferson. A couple of comments:

Digraphs does have subgraph isomorphism via DigraphEmbedding https://digraphs.github.io/Digraphs/doc/chap7_mj.html#X7AD04CC186E86CCA
I'd be happy to incorporate the solver you mention, the README says that it requires C++17. I'd also be happy to switch to C++17. I'd be reluctant to switch to C++20 after the experiences we had with using C++11 in 2014/15 (somewhat limited compiler support, false claims of having all the features of C++11 in some versions of some compilers, and/or people using old compilers). If C++17 will do it, then happy to update to that.

Oct 18 '22 16:10 james-d-mitchell

I will look at the other solver. It might be worth adding "subgraph isomorphism" to the index in the help, I was looking in GAP packages for subgraph isomorphism, and didn't spot DigraphEmbedding

We have now been using DigraphEmbedding and it's good and fast, but there seems to be a limit of 512 vertices -- is this easy to get past?

Oct 19 '22 09:10 ChrisJefferson

We have now been using DigraphEmbedding and it's good and fast,

Great, good to hear!

but there seems to be a limit of 512 vertices -- is this easy to get past?

You could try changing 512 to a higher value in the following lines, but I'm not sure if this will work:

src/bitarray.h:31:#define MAXVERTS 512 src/perms.h:28:#define MAXVERTS 512

also this will increase the amount of memory allocated by Digraphs as mentioned in #433.

Maybe there's a better solution? Any ideas what that might be?

Oct 19 '22 12:10 james-d-mitchell