pnnl / HyperNetX

Python package for hypergraph analysis and visualization.
https://hypernetx.readthedocs.io
Other
506 stars 86 forks source link

Added New Hypergraph Matching Algorithms #157

Open rotshira opened 2 weeks ago

rotshira commented 2 weeks ago

This pull request introduces several enhancements and new features to the HyperNetX library:

  1. 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.
  2. 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.
  3. 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.
  4. Greedy Matching Algorithm:

    • Enhanced the greedy matching algorithm to be more efficient and scalable.
  5. Logging and Debugging:

    • Added extensive logging to all algorithms to aid in debugging and performance analysis.
  6. 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:

Documentation:

Instructions for Reviewers:

Thank you for considering this contribution to the HyperNetX library.

brendapraggastis commented 1 week ago

@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.