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 -- Tiago de Paula Peixoto <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
