Class BSuitorMatcher¶

Nested Relationships¶

Inheritance Relationships¶

Class Documentation¶

class BSuitorMatcher : public NetworKit::BMatcher¶

B-Suitor matching finding algorithm.

Public Functions

BSuitorMatcher(const Graph &G, const std::vector<count> &b)¶

Computes a 1/2-approximate maximum weight b-matching of an undirected weighted Graph G

using the sequential b-Suitor algorithm published by Khan et al. in “Efficient Approximation

Algorithms For Weighted B-Matching”, SIAM Journal on Scientific Computing, Vol. 38, Iss. 5 (2016).

Parameters:

• G – An undirected graph.

• b – A vector of b values that represents the max number of edges per vertex v in the b-Matching (b.at(v)).

BSuitorMatcher(const Graph &G, count b = 1)¶

Parameters:

• G – An undirected graph.

• b – A value b that represents the max number of edges per vertex in the b-Matching. Defaults to the ordinary 1-Matching.

BSuitorMatcher(const Graph &G, std::string_view &path)¶

Parameters:

• G – An undirected graph.

• path – A path to a file containing b values that represents the max number of edges per vertex in the b-Matching.

~BSuitorMatcher() override = default¶

virtual void run() override¶

Runs the algorithm.

Protected Functions

std::vector<count> readBValuesFromFile(count size, std::string_view &path) const¶

Reads values from a file at path into the vector of b-values.

Parameters:

• size –

• path –

Returns:

std::vector<count>

void findSuitors(node u)¶

Iterates up to b times over the heaviest neighbors of node u and makes them to suitors if eligible.

Parameters:

u –

MatchingNode findPreferred(node u)¶

Finds the heaviest unmatched neighbor that u has not yet proposed to if it exists. For equally weighted edges w(u, t), w(u, v) and t < v, w(u, t) is considered smaller than w(u, v) to break ties.

Parameters:

y –

Returns:

Node

void makeSuitor(node u, edgeweight w, node v)¶

Makes v a suitor of u and recursively calls itself for previous worse suitors of u that got replaced with their new best match.

Parameters:

• u –

• w –

• v –

bool isSymmetrical() const¶

Checks the symmetry of pairs of nodes. It must hold that v is in suitors(u) iff u is in suitors(v).

Protected Attributes

std::vector<MatchingNodeInfo> suitors¶

std::vector<MatchingNodeInfo> proposed¶

const std::vector<count> b¶

struct MatchingNode¶

Public Functions

inline MatchingNode()¶

inline MatchingNode(node n, edgeweight w)¶

inline std::partial_ordering operator<=>(const MatchingNode &other) const¶

bool operator==(const MatchingNode &other) const = default¶

Public Members

node id¶

edgeweight weight¶

struct MatchingNodeInfo¶

Public Functions

MatchingNodeInfo() = default¶

inline MatchingNodeInfo(count b)¶

inline bool hasPartner(node u) const¶

inline MatchingNode popMinIfFull()¶

inline void insert(const MatchingNode &u)¶

inline void remove(node u)¶

Public Members

std::vector<MatchingNode> partners¶

MatchingNode min¶

count max_size¶