Skip to content

Conversation

@friedagerharz
Copy link
Collaborator

@friedagerharz friedagerharz commented Aug 7, 2023

Implementation of the sequential b-Suitor algorithm by Khan et al. and required b-matching classes.

  • BMatching.hpp represents basic properties of a b-matching data structure. It has a similar functionality as the Matching.hpp class. (They could be merged or inherit as 1-matching from b-matching if the performance remains stable.)
  • BMatcher.hpp is the abstract base class for b-matching algorithms.
  • BSuitorMatcher.hpp adds the sequential b-Suitor with a b-function. It can be used to compute a b-matching for a given undirected weighted graph and any b. E.g.:
auto G = METISGraphReader{}.read("input/tiny_02.graph");
const int b = 2;
BSuitorMatcher bsm(G, b);
bsm.run();
const auto M = bsm.getBMatching();

computes the 2-matching for the tiny_02 graph

3 2  2 1
1 1 
1 2  5 3 
7 5  6 2 
3 3 
4 2  7 6 
4 5  6 6

in (vertex_neighbor,edge_weight) METIS-like format with a weight of 19.

@friedagerharz friedagerharz force-pushed the frieda/b-suitor branch 3 times, most recently from 1d26d92 to bccb01f Compare August 10, 2023 14:48
@friedagerharz friedagerharz force-pushed the frieda/b-suitor branch 4 times, most recently from f8d17a9 to c7fde94 Compare August 23, 2023 22:10
@friedagerharz friedagerharz force-pushed the frieda/b-suitor branch 2 times, most recently from d342c99 to b993e0e Compare September 15, 2023 00:23
@friedagerharz friedagerharz force-pushed the frieda/b-suitor branch 4 times, most recently from 7e34f0b to 18f97b0 Compare September 25, 2023 08:17
@friedagerharz friedagerharz mentioned this pull request Sep 25, 2023
1 task
@friedagerharz friedagerharz marked this pull request as ready for review September 25, 2023 10:52
@friedagerharz friedagerharz force-pushed the frieda/b-suitor branch 4 times, most recently from aae6c0c to c66a1fe Compare September 29, 2023 11:36
@fabratu
Copy link
Member

fabratu commented Sep 10, 2024

This PR will be finalized in #1255.

@fabratu fabratu closed this Sep 10, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

7 participants