On (sub)graph isomorphism

Question

[chernouhov sergey]

Hi all.

What tool and method do you use fo problems like

• to chech if 2 graphs are isomorphic?
• to find in a certain graph A its subgraphs that are isomorphic to given graph B?

As for me, I tryed to solve this problem by myself and suggested maximal non-branching paths approach to solve it (preprint in Russian is here: http://dx.doi.org/10.24108/preprints-3111977. The implementation is the function SubGraphsInscribed at my C++ free lib CBioInfCpp (works with both directed and undirected graphs, connected or not).

(1) Time estimating with examples for isomorphism testing is here: https://github.com/chernouhov/CBioInfCpp-0-/tree/master/TestsGraphIsomorphismInfo

Results (number of vertices - number of edges : duration): in case grahps are DIRECTED:

250 (vertices)-350(edges) : <1 sec examples of input graphs: A is in inA-250-350.txt, B is in inB-250-350.txt

250-3500 : 12 sec examples of input graphs: A is in inA-250-3500.txt, B is in inB-250-3500.txt

1250-1350 : 4 sec examples of input graphs: A is in inA-1250-1350.txt, B is in inB-1250-1350.txt

2500-3500 : 15 sec examples of input graphs: A is in inA-2500-3500.txt, B is in inB-2500-3500.txt

in case grahps are UNDIRECTED:

250 (vertices)-350(edges) : <1 sec examples of input graphs: A is in inA-250-350.txt, B is in inB-250-350.txt

250-3500 : 34 sec examples of input graphs: A is in inA-250-3500.txt, B is in inB-250-3500.txt

1250-1350 : 33 sec examples of input graphs: A is in inA-1250-1350.txt, B is in inB-1250-1350.txt

2500-3500 : 40 sec examples of input graphs: A is in inA-2500-3500.txt, B is in inB-2500-3500.txt

(2) Examples how it may find in a graph A its subgraphs that are isomorphic to some graph B is here: https://github.com/chernouhov/CBioInfCpp-0-/tree/master/TestsIsomorphicSubGraphsFinding

In the given example for the case didected graphs it will provide 36 subgraphs of A that are isomorphic to B, and in case undirected graphs - 216. Not all the possible but "inscribed" ones.

So

• if it may be useful for someone - please, use it
• if you have some practical problems in this field why not to try to communicate
• By the way, that tools do you use for similar tasks? Yes, Python lib NetworkX make graphs isomorphism checking faster (VF2 alg.) but here we may get isomorphic subgraphs too.

[Jean-Karim Heriche]

It may be useful but usually before using some software I like to understand what it's supposed to be doing and for this I normally like to read the description of the algorithm as well as some of its theoretical motivation and some sense of how it compares to other approaches (e.g. speed, accuracy, memory efficiency...). For me the paper being in a language I can't read is an obstacle. If you're trying to get wider adoption of your software, I would suggest to write the paper in English. You could submit a preprint to arXiv.org.

[chernouhov sergey]

Thanks, it is in plan. But you see, CBioInfCpp is a free open lib, you may see code (function SubGraphsInscribed in particular) and its readme and pdf (Rus and Eng) here just now: https://github.com/chernouhov/CBioInfCpp-0-.

Also if you have some interesting tasks or datasets we may try them via it.

[Jean-Karim Heriche]

Sorry, I am not able to determine the merits of an algorithm just by reading some code.

[chernouhov sergey]

Every function has its description too.

Also if someone have interesting task or dataset you are welcome.

Answer 1

[chernouhov sergey]

Nowadays algo is elaborated to find all (not only inscribed) isomorfic subgraphs in a given graph.

In particular, it founds

• for a directed graph B (15 vertices-20edged) - 4536 isomprphic subgraphs in directed graph A(250-350), ~ 3 sec,

• for a directed graph B (25-35) - 82546 isomprphic subgraphs in directed graph A (2500-3500), ~ 1 min 40 sec

• for an undirected graph B (15 vertices-20edged) - 69572 isomprphic subgraphs in undirected graph A(250-350), ~ 5 min

look for details A: CBioInfCpp.h as a C++ lib containing some functions for bioinformatics

PS Wish it will be developed by community as I have not much skills to elaborate the approach well.

Answer 2

[chernouhov sergey]

Some "How to" is here:

https://github.com/chernouhov/CBioInfCpp-0-/tree/master/HowTo

Answer 3

[chernouhov sergey]

Approbation

2021:

Function SubGraphsInscribed is used by https://graphonline.ru/ (https://github.com/UnickSoft/GraphOffline, https://github.com/UnickSoft/graphonline) for (sub)graph isomorphism problem solving.