# Incorrect/Inconsistent subgraph identification when using get\_subisomorphisms\_vf2? **URL:** \ **Category:** Usage\ **Tags:** Python\ **Created:** [20 February 2024 04:35 UTC](https://igraph.discourse.group/t/incorrect-inconsistent-subgraph-identification-when-using-get-subisomorphisms-vf2/1755 "2024-02-20T04:35:56Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![dagwd](https://avatars.discourse-cdn.com/v4/letter/d/54ee81/32.png) [@dagwd](https://igraph.discourse.group/u/dagwd)\ **Post date:** [20 February 2024 04:35 UTC](https://igraph.discourse.group/t/incorrect-inconsistent-subgraph-identification-when-using-get-subisomorphisms-vf2/1755/1 "2024-02-20T04:35:56Z")
```auto from igraph import Graph G1 = Graph() G2 = Graph() G1.add_vertices(5) G2.add_vertices(4) G1.add_edge(0, 1) G1.add_edge(1, 2) G1.add_edge(2, 3) G1.add_edge(3, 0) G1.add_edge(3, 4) G2.add_edge(0, 1) G2.add_edge(1, 2) G2.add_edge(2, 3) isomorphisms = set() for i in G1.get_subisomorphisms_vf2(G2): isomorphisms.add(tuple(sorted(i))) print(isomorphisms) ``` If you run the above code you end up with 3 unique subisomorphisms of G2 on G1. However, there should only be two (you will get this result if you use the VF2 implementation found in networkx). What appears to be happening is that it is finding that G2 a line of 4 vertices is isomorphic to the subgraph on G1 given by vertices (0, 1, 2, 3), but this is a square. I find this behavior very confusing as igraph correctly says a square and G2 are not isomorphic yet they somehow are subgraph ismorphisms? Does anyone have any insight into why this is happening and if there is a workaround/fix? I’d like to figure this out so I can keep using igraph and don’t have to go with the slower option of networkx. ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [20 February 2024 10:31 UTC](https://igraph.discourse.group/t/incorrect-inconsistent-subgraph-identification-when-using-get-subisomorphisms-vf2/1755/2 "2024-02-20T10:31:31Z")
The result is correct, and consistent with the customary use of the term “subgraph” in graph theory. `0-1-2-3` is a _subgraph_ of G1, but it is not an [_induced subgraph_](https://en.wikipedia.org/wiki/Induced_subgraph). If you need only induced subgraphs, use `get_subisomorphisms_lad()` with `induced=True`. Here’s a visual check of the result with Mathematica: ![image](https://global.discourse-cdn.com/free1/uploads/igraph/original/2X/4/4da47e047b72dbfdb674cd21997077331957589c.png) ---
**Author:** ![dagwd](https://avatars.discourse-cdn.com/v4/letter/d/54ee81/32.png) [@dagwd](https://igraph.discourse.group/u/dagwd)\ **Post date:** [20 February 2024 14:24 UTC](https://igraph.discourse.group/t/incorrect-inconsistent-subgraph-identification-when-using-get-subisomorphisms-vf2/1755/3 "2024-02-20T14:24:52Z")
Ah ok, my bad. I was thinking strictly in terms of induced subgraphs. Unfortunately, in my use case I can have weighted edges that effect the isomorphisms which only the VF2 algorithm can handle (unless I am missing something in the docs). Thanks for your quick response. ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [20 February 2024 14:43 UTC](https://igraph.discourse.group/t/incorrect-inconsistent-subgraph-identification-when-using-get-subisomorphisms-vf2/1755/4 "2024-02-20T14:43:42Z")
You mean coloured edges? You can construct an appropriate `domain` parameter for LAD to handle those. > [@subgraph\_isomorphisms for considering absent edge](https://igraph.discourse.group/t/subgraph-isomorphisms-for-considering-absent-edge/1697/4): > > Yes, you can achieve the same by using an appropriate domains argument. For each vertex, give the list of other vertices with the same colour. See the documentation for details. I’m sorry, I don’t have time to write an example now. I would like to have an alternative interface for LAD that takes vertex and edge colours directly, as I did in igraph’s Mathematica interface, but we’re not there yet. So you’ll have to construct the domain manually for now. ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [20 February 2024 14:47 UTC](https://igraph.discourse.group/t/incorrect-inconsistent-subgraph-identification-when-using-get-subisomorphisms-vf2/1755/5 "2024-02-20T14:47:39Z")
I’m sorry, I responded in too much of a hurry. It may not be possible to handle _edge_ colours with LAD, only vertex colours. However, you can filter the matches returns by VF2 and keep only induced subgraphs. I don’t have the time to write an example now, or even to check if the most convenient functions are exposed in Python … in C I’d use `igraph_induced_subgraph_edges()` to count if the induced subgraph has as many edges as the pattern. I’m sure Python should have function to get an induced subgraph at least as a graph, if not a list of edges (which is more performant). ---
**Author:** ![dagwd](https://avatars.discourse-cdn.com/v4/letter/d/54ee81/32.png) [@dagwd](https://igraph.discourse.group/u/dagwd)\ **Post date:** [21 February 2024 03:07 UTC](https://igraph.discourse.group/t/incorrect-inconsistent-subgraph-identification-when-using-get-subisomorphisms-vf2/1755/6 "2024-02-21T03:07:34Z")
Thanks for the idea! That should totally work. ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [22 February 2024 10:52 UTC](https://igraph.discourse.group/t/incorrect-inconsistent-subgraph-identification-when-using-get-subisomorphisms-vf2/1755/7 "2024-02-22T10:52:13Z")
Feel free to open an issue for adding support for finding induced-only subgraphs with VF2 here: > **[Build software better, together](https://github.com/igraph/igraph/issues/new/choose)** > > GitHub is where people build software. More than 100 million people use GitHub to discover, fork, and contribute to over 420 million projects. Doing the filtering in C would be more performant than relying on Python for this. It won’t be as performant as modifying VF2 for this purpose, but better than nothing.