MaxMatching: Solver for Maximum Weighted Matching

In rlemon: R Access to LEMON Graph Algorithms

Solver for Maximum Weighted Matching

Description

Finds the maximum weighted matching in graphs and bipartite graphs. Each algorithm in this set returns different outputs depending on different situations, like PerfectMatching or PerfectFractionalMathing.

Usage

MaxMatching(
  arcSources,
  arcTargets,
  arcWeights = NULL,
  numNodes,
  algorithm = "MaxWeightedMatching"
)

Arguments

arcSources	Vector corresponding to the source nodes of a graph's edges
arcTargets	Vector corresponding to the destination nodes of a graph's edges
arcWeights	Vector corresponding to the weights of a graph's edges. Default is NULL for unweight matching.
numNodes	The number of nodes in the graph
algorithm	Choices of algorithm include "MaxWeightedMatching", "MaxWeightedPerfectMatching", "MaxWeightedFractionalMatching", and "MaxWeightedPerfectFractionalMatching". "MaxWeightedMatching" is the default.

Details

For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00615.html.

Value

A named list containing two entries: 1) "value": the matching value, 2) "edges": the edges of the final graph, in a list of (node, node) pairs

rlemon documentation built on Feb. 16, 2023, 5:33 p.m.