pnnl
Added New Hypergraph Matching Algorithms
This pull request introduces several enhancements and new features to the HyperNetX library:
-
New Matching Algorithms:
- Implemented three new hypergraph matching algorithms that provide better approximations than the greedy matching algorithm.
- Each algorithm accepts an additional parameter for a custom maximum matching function, allowing for flexibility in usage.
-
Iterated Sampling Algorithm:
- An implementation of the iterated sampling algorithm for hypergraph matching. This algorithm uses a probabilistic approach to find an approximate matching in hypergraphs.
-
HEDCS-Based Approximation Algorithm:
- Added the HEDCS-based approximation algorithm for hypergraph matching. This algorithm constructs a Hyper-Edge Degree Constrained Subgraph (HEDCS) to find a maximal matching.
-
Greedy Matching Algorithm:
- Enhanced the greedy matching algorithm to be more efficient and scalable.
-
Logging and Debugging:
- Added extensive logging to all algorithms to aid in debugging and performance analysis.
-
Experiments and Performance Comparison:
- Created scripts to run performance comparisons of the algorithms on large random inputs using the experiments_csv library.
- Generated and analyzed results to compare the size of the match and the running time of each algorithm.
Testing:
- Thoroughly tested the new algorithms with various input sizes and configurations.
- Added doctests to ensure the correctness and robustness of the algorithms.
Documentation:
- Updated the documentation to include descriptions and usage examples for the new algorithms.
Instructions for Reviewers:
- Please review the new algorithms for correctness and performance.
- Verify the logging outputs for clarity and usefulness.
Thank you for considering this contribution to the HyperNetX library.
@rotshira Thank you for the generous contribution. We are reviewing your request to see how best to integrate it. Do you have a Python tutorial (jupyter notebook) that could highlight your work and reference your publication? This will be required to add it to the library - we haven't stipulated this requirement yet in the contributions description as all contributors have done this automatically. We will update it now to support new contributors. It may take a week or two for us to review and comment. Feel free to send up comments or additional code/notebook in the meantime.
hey we just added a Python tutorial in tutorials/advanced/ we still get the error in the workflow that @erelsgl mentioned last week.
Hi @rotshira! Thank you for your contribution! It is very thorough and impressive. We are excited to get it implemented into HNX as a module. It seems that you have all the necessary files for us to put in a new module. The exact process (contribution guidelines) for the needed files and changes for us to review in a PR is documented here https://hypernetx.readthedocs.io/en/develop/contributions.html. If you could go over those contribution guidelines and resubmit the PR with just the needed files it would be appreciated. Specifically, we are looking for just the module (.py) file itself, a tutorial as a notebook, and a unit test file. If you would also like to provide an rst file for the documentation that would be great! specifically something like what was done for Modularity and Clustering (https://hypernetx.readthedocs.io/en/develop/modularity.html). Thank you again!
@myersau3 are there any other required changes?
@erelsgl So far this looks good to me! Thank you for making those changes! I'm going to go through everything in detail today and will get back to you soon if anything needs changed.
@erelsgl @nivmoti @rotshira I've created a branch called "hypergraph_matching" that I will be using to submit a PR for this module. I had to make a few minor changes to be compatible with our current format but overall everything looks good and runs! Thank you for all the work. I'll make sure that you all are credited with the contributions and will keep you updated! Thank you again!