-
Notifications
You must be signed in to change notification settings - Fork 325
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Make isomorphism algorithm generic and add subgraph isomorphism check #369
Conversation
…ype at compile-time
…somorphism functions
Wow, amazing. On the quick look it is good, but I need more time to read it thoroughly and test. Good job! |
@XVilka ping me if you need me to rebase / change anything 😉 |
Please next time don't include whitespace changes - it makes review process harder, especially with those huge graph maps of 1 and 0. |
Sorry about that, my editor removes trailing whitespaces and I always notice it too late. |
Hi there!
I refactored the code in
isomorphism.rs
to make the algorithms generic, and I also added functions to check for subgraph isomorphism as requested in #48.Added
petgraph::visit::EdgeCount
trait to get the edge count for a graph (which is needed to check for the edge count before actually the VF2 matching algorithm), which is implemented for all graph implementations.petgraph::algo::is_isomorphic_subgraph
that checks if a graph is isomorphic to a subgraph of another graph (andpetgraph::algo::is_isomorphic_subgraph_matching
for the semantic matching variant)Changed
petgraph::algo::is_isomorphic
is now generic over its two input graphs, meaning that they don't even have to be of the same concrete type. There is however a check at compile time to make sure both graphs are eitherDirected
orUndirected
.node_match
andedge_match
callbacks are properly typed.is_isomorphic
is now properly encapsulated, whereas the old code was doing everything in one big function with inline closures.NodeIndexable
trait as not doing so had an impact on performance (the generic code usesto_index
andfrom_index
methods much more)Benchmarks
graph.bench
are benchmarks with the code from themaster
branch,generic.bench
with the code from this PR.To do
Figure out a way foris_isomorphic
not to require the input to beDataMap
(probably by changing theSemanticMatcher
trait).Figure out a way to perform semantic feasibility validation for edges in a generic manner: currently the code needs to access an edge given its two endpoints, (this is causing theiso_matching
test to fail currently)Figure out a way foris_isomorphic
not to requireIntoEdgesDirected
for the semantic validation of edges (IntoNeighborsDirected
only is required for the rest of the algorithm).