search

aplbrain / grandiso-networkx

Performant, pure-Python subgraph isomorphism and monomorphism search (aka "motif search")
Apache License 2.0
56 stars 10 forks source link

support edge hop #33

Closed khoale88 closed 1 year ago

khoale88 commented 1 year ago

many tests fail, apparently, I missed something

one of the biggest changes is candidate_nodes now can have the current next_node if the min_hop is 0. Additionally, get_next_backbone_candidates now returns a list of (candidate, last_node) so that I know what is the last node. If there is a triangle in the motif, I think I'm going to miss the last edge if it has any hopping.

I feel like I'm talking more and more about edges, while the algor care more about nodes. Can you take a look and see how it can be better, @j6k4m8 ?

khoale88 commented 1 year ago

I found out a hole in my PR. I will think of a better way to support edge hopping. Closing this PR.

j6k4m8 commented 1 year ago

Got it — I'm happy to chat more about this implementation together if you like!

One major concern I have is I don't want this to add runtime cost to the "base" case of the no-hop version of the algorithm. I have a potential thought on how we might be able to do this by only modifying the structural validation check, but I need to brainstorm on it a bit more to make sure it'll work...