Hi there. I’m just looking for some advise, given two graphs G and H, on how to find the largest subgraph of G which is isomorphic to some subgraph of H. I know nothing about the VF2 algorithm, which I found about by looking topology.subgraph_isomorphism documentation. I’m wondering if there is some easy way to take advantage of that function for my purpose… Or, perhaps, there is some other function that does what I want, which I have somehow missed? Appreciate any comments. Thanks!
Rodrigo
There’s no such function implemented in graph-tool, and I don’t think there’s a fast way of implementing it.
A brute force attempt would be to start with G and search for it in H, and if not found, go through all single vertex removals of G and try again, and then every two vertex removals, and so on. But this approach will not scale well for G and H that are not very small.
OK, thanks for your comments. Just in case it could be useful for someone
else, I found about the concept of “maximum common induced subgraph” which
is particularly useful in cheminformatics, so algorithms are implemented in
packages like, for instance, MolecularGraph.jl.
Just for reference, this is a NP-Hard problem with no easy approximation. As I mentioned, algorithms such as those implemented in MolecularGraph.jl are only feasible for very small networks (such as those representing molecules), but are not practical for larger networks.