Kind of subgraphs matched by VF3

[bkj]

Hi --

Running the example command

./bin/vf3 ./test/bvg1.sub.grf ./test/bvg1.grf -s

gives you the following matches

0,0:19,1:12,2:17,3:
0,0:19,1:12,2:5,3:
0,0:2,1:12,2:17,3:
0,0:2,1:12,2:5,3:
0,0:2,1:5,2:12,3:
0,0:2,1:5,2:17,3:
13,0:9,1:14,2:16,3:
13,0:9,1:16,2:14,3:
5,0:0,1:7,2:19,3:
6,0:18,1:11,2:9,3:
6,0:18,1:9,2:11,3:
7,0:5,1:11,2:18,3:
7,0:5,1:18,2:11,3:

However, both edges 0 17 and 17 0 exist in the target graph, so the subgraph induced by 0 12 17 19 has four edges:

0 17
0 12
17 0
19 0

What kinds of subgraphs is VF3 trying to match? I thought it was "find a set of nodes in target s.t. the subgraph they induce is isomorphic to query" -- but the above example suggests it may be something different.

As another example -- the subgraph induced by 0,0:19,1:12,2:5,3: is not isomorphic to query -- there's an edge 5 19 in target that isn't in query.

(FWIW -- the VF2 implementation in networkx does not return either of the above examples, which IMO is the expected behavior.)

Thanks!

[shaofengzeng]

0,0:19,1:12,2:5,3: is isomorphic to the query. You may confuse the homomorphism with isomorphism.

[bkj]

@shaofengzeng -- thanks for your reply. Can you give your definition of homomorphism and isomorphism?

And when you say

0,0:19,1:12,2:5,3: is isomorphic to the query

do you mean "the subgraph induced by 0 19 12 5 is isomorphic to the query"? Or something else?

[shaofengzeng]

@shaofengzeng -- thanks for your reply. Can you give your definition of homomorphism and isomorphism?

And when you say

0,0:19,1:12,2:5,3: is isomorphic to the query

do you mean "the subgraph induced by 0 19 12 5 is isomorphic to the query"? Or something else?

I'm sorry, i'm also confused about the results now. I haved tried the following command,
./bin/vf3 ./test/bvg1.sub.grf ./test/bvg1.grf -s
However, i didn't find the results you list above, for example, 0,0:19,1:12,2:5,3:

[bkj]

$ git clone https://github.com/MiviaLab/vf3lib
$ cd vf3lib
$ make clean
$ make
$ ./bin/vf3 ./test/bvg1.sub.grf ./test/bvg1.grf -s > tmp
$ fgrep "0,0:19,1:12,2:5,3:" tmp | head
0,0:19,1:12,2:5,3:
0,0:19,1:12,2:5,3:
...

should work

[shaofengzeng]

$ git clone https://github.com/MiviaLab/vf3lib
$ cd vf3lib
$ make clean
$ make
$ ./bin/vf3 ./test/bvg1.sub.grf ./test/bvg1.grf -s > tmp
$ fgrep "0,0:19,1:12,2:5,3:" tmp | head
0,0:19,1:12,2:5,3:
0,0:19,1:12,2:5,3:
...

should work

It's very strange that I get different results on different computers. I can get the same results with g++ 5.4, and get different results with g++7.5

[vincarlet]

Sorry, I should have found the bug related to the wrong usage of a flag added in the last release to select between induced and non-induced subgraph isomorphism.