MaxMatching {rlemon}

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