subgraph_isomorphism bug: misses occurrences

graph-tool
1

Hi Tiago,

I was puzzled by some results of my tests failing when compared to
subgraph_isomorphism. Finally I've narrowed it down to a (fairly) small example:

2

Hi Ingo,

I was puzzled by some results of my tests failing when compared to
subgraph_isomorphism. Finally I've narrowed it down to a (fairly) small example:

#####
from graph_tool.all import *

sub = Graph()
sub.add_vertex(3)
sub.add_edge(sub.vertex(0), sub.vertex(1))
sub.add_edge(sub.vertex(0), sub.vertex(2))

G = Graph()
G.add_vertex(4)
G.add_edge(G.vertex(0), G.vertex(1))
G.add_edge(G.vertex(0), G.vertex(2))
G.add_edge(G.vertex(1), G.vertex(2))
G.add_edge(G.vertex(3), G.vertex(2))
G.add_edge(G.vertex(1), G.vertex(3))

vmap, emap = subgraph_isomorphism(sub, G, random=False)
for e in G.edges(): print G.edge_index[e], e
for vm, em in zip(vmap, emap): print vm.a, em.a

G.add_vertex()
G.add_edge(G.vertex(1), G.vertex(4))

vmap, emap = subgraph_isomorphism(sub, G, random=False)
for e in G.edges(): print G.edge_index[e], e
for vm, em in zip(vmap, emap): print vm.a, em.a
#####

We search for sub,

0 --> 1
\
  \
   -> 2

G first looks like this:

0 --> 1 --> 3
\ | /
  \ v /
   -> 2 <-

when subgraph_isomorphism gets both occurrences correctly. But after
adding a link (1, 4), it gets the two new occurrences involving vertex 4,
but suddenly misses the one with edges [(1,3), (1,2)].

Yes, this is of course a bug. The fix is quite simple, and is already in
the git version. Your example works as it should now, and produces all
the matches.

Thanks for finding this, and providing a small example!

Also, I would be grateful for some clarification:

1) subgraph_isomorphism is supposed to deliver all (not only the induced)
occurrences, right?

Correct.

(If you want induced subgraphs, you can use the motifs function.)

2) Does it give several subgraphs which are isomorphic to each other as
separate occurrences or not? My tests suggest this is not consistent
between different situations.

Yes, different valid mappings which are isomorphic should occur
separately. This not happening was a manifestation of the bug you
found. For instance, with the correct algorithm, I get the following
result for the first graph in your example:

[1 3 2] [4 2]
[1 2 3] [2 4]
[0 1 2] [0 1]
[0 2 1] [1 0]

I.e. each match happens "twice".

3) What is the purpose of the random=True default? It bit me badly when
I first tried the function :slight_smile:

This is actually more useful if n_max > 0, in particular n_max = 1, in
order to return a random subgraph. I have modified the default to False,
since I agree it may be more expected.

Cheers,
Tiago

3

Hi Tiago,

Thank you very much for your super-quick fix! My tests all pass as expected
now. Also, thanks for the helpful answers to my questions.

Cheers,
Ingo