Skip to content

Setup vf2pp files for expansion to subgraph problems#6230

Closed
dschult wants to merge 2 commits intonetworkx:mainfrom
dschult:vf2pp_setup
Closed

Setup vf2pp files for expansion to subgraph problems#6230
dschult wants to merge 2 commits intonetworkx:mainfrom
dschult:vf2pp_setup

Conversation

@dschult
Copy link
Copy Markdown
Member

@dschult dschult commented Nov 21, 2022

This PR sets up the VF2++ functions to allow easier addition of the subgraph versions of the problem.
The main change are to add the degree dicts to the namedtuple data structure and
make the return False statements in the main generator function more useful.

Notes:

  • Moved the degree dict creation to _initialize_parameters. Moved this call to before where the degrees are used.
  • added G1_degree and G2_degree degree dicts to the graph parameters namedtuple.
  • Reordered the intro of the main function vf2pp_all_isomorphisms.
    • Replaced return False (which doesn't do much inside a generator) with return "helpful string", which is the same as raise StopIteration("helpful string"). The string is only seen if you manually use next on the generator function. But that can be helpful for debugging why there is e.g. no isomorphism.
    • Inline the function _precheck_label_properties and make more readable.
  • Removed the degree dict input parameter from the _find_candidates helper function.
  • changed the name of utils.labels_different to utils.labels_many.
  • adjusted the tests accordingly.
  • Reworded, unified language and corrected the main module doc_strings.

If this is too much to review I can split it up. Most of the changes are due to the change in the namedtuple.

Notes:

- Reordered the intro of the main function vf2pp_all_isomorphisms.
  - Replace `return False` (which doesn't do much inside a generator)
    with `return "helpful string"`. The string is only seen if you manually
    use `next` on the generator functuion. But that can be helpful for debugging.
  - Moved the degree dict creation to `_initialize_parameters`. Moved this call
    to before where the degrees are used.
  - Inline the function `precheck_label_properties` and make more readable.
- added G1_degree and G2_degree degree dicts to the graph parameters namedtuple.
  Removed the degree dict input parameter to some helper functions.
- Reworded, unified language and corrected the main module doc_strings.
- changed the name of utils.labels_different to utils.labels_many.
- adjusted the tests accordingly.

Adding the features for "sub" and "mono" problem types should be easier after
these changes.

For the future:

The namedtuples are very hard to adjust throughout the code. It would be good
to have a central place instead of unpacking the namedtuple in each function.
But maybe there isn't a better way.

I think the Directed version of the helper functions can be eliminated with
code that checks during the function. I also believe the namedtuples could
be better used here, perhaps being different between graph and directed graph.

The multiedge calculation should be moved to _initialize_parameters
to avoid recalculation for MultiGraphs.
@jarrodmillman jarrodmillman removed this from the 3.2 milestone Jul 20, 2023
@MridulS
Copy link
Copy Markdown
Member

MridulS commented Dec 13, 2023

@dschult is this ready for review? I guess this has some conflicts after #6334 ?

@MridulS
Copy link
Copy Markdown
Member

MridulS commented Oct 26, 2025

Is this still relevant @dschult ?

@dschult
Copy link
Copy Markdown
Member Author

dschult commented Oct 29, 2025

I'm sprinkling these changes into a (currently) larger version that tries to do the same thing. So I am closing this. Thanks for the nudge!

@dschult dschult closed this Oct 29, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Development

Successfully merging this pull request may close these issues.

4 participants