Hi Ingo,

On 04/15/2012 06:06 PM, Ingo Lohmar wrote:

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 :)

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