Closed kittobi1992 closed 1 year ago
Merging #140 (8a5df10) into master (5befa92) will decrease coverage by
1.02%
. The diff coverage is57.27%
.:exclamation: Current head 8a5df10 differs from pull request most recent head b3400d0. Consider uploading reports for the commit b3400d0 to get more accurate results
@@ Coverage Diff @@
## master #140 +/- ##
==========================================
- Coverage 83.42% 82.40% -1.02%
==========================================
Files 139 142 +3
Lines 14814 14998 +184
Branches 6038 6052 +14
==========================================
+ Hits 12358 12359 +1
- Misses 2456 2639 +183
Impacted Files | Coverage Δ | |
---|---|---|
mt-kahypar/datastructures/connectivity_info.h | 85.22% <ø> (-1.05%) |
:arrow_down: |
mt-kahypar/datastructures/dynamic_graph.h | 88.47% <ø> (-11.53%) |
:arrow_down: |
mt-kahypar/datastructures/dynamic_hypergraph.h | 84.86% <ø> (ø) |
|
mt-kahypar/datastructures/graph.h | 94.44% <ø> (-0.16%) |
:arrow_down: |
mt-kahypar/datastructures/hypergraph_common.h | 100.00% <ø> (ø) |
|
mt-kahypar/datastructures/partitioned_hypergraph.h | 86.97% <ø> (ø) |
|
mt-kahypar/datastructures/sparse_pin_counts.h | 89.44% <ø> (-7.49%) |
:arrow_down: |
mt-kahypar/datastructures/static_graph.h | 87.40% <ø> (+1.11%) |
:arrow_up: |
mt-kahypar/datastructures/static_hypergraph.h | 79.55% <ø> (ø) |
|
mt-kahypar/macros.h | 100.00% <ø> (ø) |
|
... and 83 more |
... and 8 files with indirect coverage changes
:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more
Fixed graph version
In Mt-KaHyPar, we implement different graph and hypergraph data structures specifically designed for some partitioning configurations (preset). For each of these data structures, we then build one executable that can run a subset of our configurations. A wrapper is then responsible for calling the correct binary for a given preset. We use a similar approach for our C and Python library interface. As it has turned out that having exchangable (hyper)graph data structures is a great design feature of Mt-KaHyPar, it slows down the compile time since we have to build for each data structure a seperate executable and library interface.
This change introduces the underlying partitioning data structures of a configuration as a template parameter in all relevant classes. This removes the wrapper workaround solution as we can now build the whole partitioning suite in one executable and also provide only one C and Python library interface. It also speeds up compilation since the different configurations share many features. Moreover, the different partitioning configurations can be switched off for faster compilation. This can be beneficial during development or for a fast CI build.
I compared the quality and running time of all configurations of my Dissertation and the Latest commit in this PR.
Here are the running times for graph partitioning: It seems that all configurations are a bit faster (except for Mt-KaHyPar-D-F). This could be due the simplifaction of the move synchronization mechanism in the partitioned graph class.
Here are the running times for hypergraph partitioning: It seems that our n-level algorithm is a bit faster than our previous version. However, Mt-KaHyPar-D-F seems a bit slower (7%), but still acceptable.
The performance profiles look like the plot below for all configuration, which means that the change does not affect the solution quality.