search

fozziethebeat / S-Space

The S-Space repsitory, from the AIrhead-Research group
GNU General Public License v2.0
203 stars 106 forks source link

Subgraph Isomorphism #62

Closed yolapop closed 9 years ago

yolapop commented 9 years ago

Hi, is there anyway to calculate subgraph isomorphism? I've searched along the source code but there's only VF2State which is for graph isomorphism, not subgraph isomorphism.

Thank you.

davidjurgens commented 9 years ago

Hi Yolanda,

What do you mean by subgraph isomorphism? Are you testing for whether there exist subgraphs of two graphs that are isomorphic?

Thanks, David

On Mon, Apr 6, 2015 at 8:26 AM, Yolanda Septiana notifications@github.com wrote:

Hi, is there anyway to calculate subgraph isomorphism? I've searched along the source code but there's only VF2State which is for graph isomorphism, not subgraph isomorphism.

Thank you.

— Reply to this email directly or view it on GitHub https://github.com/fozziethebeat/S-Space/issues/62.

yolapop commented 9 years ago

By subgraph isomorphism I mean searching for occurence(s) of smaller graph (A) in the larger graph (B).

In the original vflib2, there are files vf2_sub_state.h and vf2_sub_state.cc and I've been trying to port that myself by looking at your library and those two files but I'm afraid there's some error because it took a long running time.

Another example is from boost graph library. In this library, it searches for all occurences of smaller graph A in larger graph B but I only want to search one occurence.

yolapop commented 9 years ago

Hi @davidjurgens,

I've done some testing between the original VFLib2 and Boost Graph. I found that VFLib2 is very slow compared to Boost Graph. Can you confirm this? I used small graph with 10 nodes and large graph with ~550 nodes. That's why when I tried S-Space, my code was running for days to search for subgraph iso.

If you need my source file, I'll gladly send it to you.

Thank you.

davidjurgens commented 9 years ago

Hi Yolanda,

I haven't used Boost Graph much so unfortunately, I can't really comment on the speed difference. We originally went with VFLib2 because it was the fastest at the time and was relatively straight-forward to port to Java.

Per your earlier question, we haven't really looked into subgraph matching like you describe. The current code was used for network motif detection but for relatively small motifs, so we never needed to port the full VF2 library code.

Thanks, David

On Mon, Apr 13, 2015 at 12:16 AM, Yolanda Septiana <notifications@github.com

wrote:

Hi @davidjurgens https://github.com/davidjurgens,

I've done some testing between the original VFLib2 and Boost Graph. I found that VFLib2 is very slow compared to Boost Graph. Can you confirm this? I used small graph with 10 nodes and large graph with ~550 nodes. That's why when I tried S-Space, my code was running for days to search for subgraph iso.

If you need my source file, I'll gladly send it to you.

Thank you.

— Reply to this email directly or view it on GitHub https://github.com/fozziethebeat/S-Space/issues/62#issuecomment-92200307 .

yolapop commented 9 years ago

Thanks for your reply.

Apparently I should use time hog approach which will terminate searches that are running above 100s.