| Title: | Maximum Matching for General Weighted Graph |
|---|---|
| Description: | Computes the maximum matching for unweighted graph and maximum matching for (un)weighted bipartite graph efficiently. |
| Authors: | Bowen Deng |
| Maintainer: | Bowen Deng <[email protected]> |
| License: | CC0 |
| Version: | 0.1.0 |
| Built: | 2024-11-06 05:42:35 UTC |
| Source: | https://github.com/cran/maxmatching |
Computes the weighted bipartite matching using Hungarian's algorithm
blossom(G, weighted = FALSE, maxcardinality = FALSE)blossom(G, weighted = FALSE, maxcardinality = FALSE)
G |
The graph to compute the maximum cardinality matching |
weighted |
Whether the graph is weighted, if true, weights should be obtained by E(G)$weight |
maxcardinality |
Whether the maximum weight should be computed over all maximum cardinality matchings |
Blossom's algorithm for maximum cardinality matching for general graph
Efficiently compute the maximum weighted biparitite matching using the Hungarian algorithm (TODO: citation) Almost a direct port of Joris van Rantwijk's python code at http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py
The maximum weighted matching for G, in a list of edges
Compute the maximum matching for undirected graph
maxmatching(G, weighted = FALSE, maxcardinality = FALSE)maxmatching(G, weighted = FALSE, maxcardinality = FALSE)
G |
undirected igraph object representing the input |
weighted |
whether the graph is weighted, if the graph is weighted, the weight should be able to be accessed with igraph::E(G)$weight |
maxcardinality |
Ignore if the graph is bipartite, and unmeaningful if the graph is unweighted. If the graph is non-bipartite and weighted, only computes the maximum weighted matching among all maximum cardinality matchings. |
maxmatching
TODO
The matchings in a list
# Unweighted general graph G1 <- igraph::graph(c(1, 2, 1, 3, 1, 4, 3, 4, 3, 5, 5, 6, 6, 7, 7, 8, 8, 9, 3, 8, 5, 8), directed = FALSE) maxmatching(G1, weighted = FALSE) # Unweighted bipartite graph G2 <- igraph::graph(c(1, 5, 1, 6, 1, 7, 2, 5, 2, 8, 3, 6, 3, 7, 3, 8, 4, 6, 4, 7, 4, 8), directed = FALSE) maxmatching(G2, weighted = FALSE) # Weighted bipartite graph G3 <- igraph::graph(c(1, 5, 1, 6, 1, 7, 2, 5, 2, 8, 3, 6, 3, 7, 3, 8, 4, 6, 4, 7, 4, 8), directed = FALSE) igraph::E(G3)$weight <- runif(length(igraph::E(G3)), 0, 1) maxmatching(G3, weighted = TRUE)# Unweighted general graph G1 <- igraph::graph(c(1, 2, 1, 3, 1, 4, 3, 4, 3, 5, 5, 6, 6, 7, 7, 8, 8, 9, 3, 8, 5, 8), directed = FALSE) maxmatching(G1, weighted = FALSE) # Unweighted bipartite graph G2 <- igraph::graph(c(1, 5, 1, 6, 1, 7, 2, 5, 2, 8, 3, 6, 3, 7, 3, 8, 4, 6, 4, 7, 4, 8), directed = FALSE) maxmatching(G2, weighted = FALSE) # Weighted bipartite graph G3 <- igraph::graph(c(1, 5, 1, 6, 1, 7, 2, 5, 2, 8, 3, 6, 3, 7, 3, 8, 4, 6, 4, 7, 4, 8), directed = FALSE) igraph::E(G3)$weight <- runif(length(igraph::E(G3)), 0, 1) maxmatching(G3, weighted = TRUE)