[WIP] Louvain algorithm for undirected graphs

[jpacold]

I finally had some time to work on #1141, so far only on the Rust side and only for undirected graphs. Opening this for feedback on how the Rust code is organized, and maybe to restart the discussion on whether this should go here or in petgraph.

The big additions here are:

• metrics.rs

  • Modularity: a trait for graphs for which we can compute modularity (by extension this means we can apply the Louvain method)
  • modularity: computes the modularity, given a graph and a set of subsets.
  • Partition: a struct holding a graph partition. This mainly exists to keep the implementation of modularity organized.

• louvain.rs

  • InnerGraph: at each level of the algorithm we work with an aggregated graph, where each node of this graph corresponds to one of the communities that were identified in the previous level). InnerGraph keeps track of this correspondence.
  • LouvainAlgo: helper functions for updating the Partition at each level of the algorithm.
  • one_level_undirected: most of the business logic is in here since it constructs the new communities at each level, roughly equivalent to _one_level in the networkx implementation.
  • louvain_communities: repeatedly calls one_level_undirected, stopping either after a fixed number of iterations or if the modularity improvement falls below the given threshold.

I realize this is a lot to review at once and can go into more detail about each piece if necessary.

[jpacold]

• Fixed two mistakes in the modularity gain calculation (I am actually a little surprised that the tests passed earlier and need to come up with some more)
• Addressed some of the comments

It looks as if the CI is failing because I used associated type bounds.

[IvanIsCoding]

• Fixed two mistakes in the modularity gain calculation (I am actually a little surprised that the tests passed earlier and need to come up with some more)
• Addressed some of the comments

It looks as if the CI is failing because I used associated type bounds.

Indeed our current MSRV is Rust 1.70 from June 2023. Rust 1.79 is from June 2024. In the past we used to follow Debian stable's Rustc which believe it or not is in 1.63 still.

I'd try rewriting it before we discuss bumping MSR, 1.79 might break a couple people that install from source

[coveralls]

Pull Request Test Coverage Report for Build 10877937563

Warning: This coverage report may be inaccurate.

This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.

• For more information on this, see Tracking coverage changes with pull request builds.
• To avoid this issue with future PRs, see these Recommended CI Configurations.
• For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

• 0 of 293 (0.0%) changed or added relevant lines in 4 files are covered.
• No unchanged relevant lines lost coverage.
• Overall coverage decreased (-1.5%) to 94.344%

---

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
rustworkx-core/src/community/mod.rs	0	6	0.0%
rustworkx-core/src/community/utils.rs	0	10	0.0%
rustworkx-core/src/community/metrics.rs	0	81	0.0%
rustworkx-core/src/community/louvain.rs	0	196	0.0%
<!--	Total:	0	293

Totals
Change from base Build 10672676557:	-1.5%
Covered Lines:	17999
Relevant Lines:	19078

---

💛 - Coveralls