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:

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:

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.aG.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

\

\

-> 2G 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

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

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