r - 二分图匹配以匹配两个集合

Question

我是 R 中 igraph 包的新手。我有两组 A 和 B，每组都有 N 顶点 (A1, A2, ..., AN) 和 (B1, B2, ..., BN)。 A 的每个元素到 B 的每个元素之间都有一条边，我有一个函数 fWgt(Ai, Bj) 返回Ai 和 Bj 之间的边的权重。

我一直在尝试使用 R 中的 igraph 包进行加权最大二分匹配，但我无法按照 igraph 包裹。例如，在为 igraph 包中的 maximum.bipartite.matching 函数给出的示例中:

Usage: 

maximum.bipartite.matching(graph, types = NULL, weights = NULL,
   eps = .Machine$double.eps) 

Example: 

g2 <- graph.formula( a-b-c-d-e-f-g )
V(g2)$type <- rep(c(FALSE,TRUE), length=vcount(g2))
str(g2, v=TRUE)
maximum.bipartite.matching(g2)

我不知道如何使用 重新表述我的问题(通过 fWgt 函数设置 A、B、边)图.公式?示例中的 str 函数似乎设置了边缘，但对于我的情况，什么与 str 函数等效？

* 编辑 *

感谢您的回复。我只能在 SO 上选择一个。

Answer 1

我不熟悉 igraph 包中的 maximum.bipartite.matching 函数，但您可以使用 lp 将其作为赋值问题来解决lpSolve 包中的 .assign 函数:

library(lpSolve)
set.seed(144)
# For example, generate random weights
fWgt <- function(Ai, Bj) runif(1)
N <- 10
wts <- sapply(1:N, function(col) sapply(1:N, function(row) fWgt(row, col)))
res <- lp.assign(wts, "max")
res$solution
#       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#  [1,]    0    0    0    0    0    0    0    1    0     0
#  [2,]    0    0    0    0    0    0    1    0    0     0
#  [3,]    0    0    0    0    0    0    0    0    0     1
#  [4,]    0    0    0    1    0    0    0    0    0     0
#  [5,]    0    0    0    0    0    0    0    0    1     0
#  [6,]    0    0    1    0    0    0    0    0    0     0
#  [7,]    0    0    0    0    0    1    0    0    0     0
#  [8,]    1    0    0    0    0    0    0    0    0     0
#  [9,]    0    1    0    0    0    0    0    0    0     0
# [10,]    0    0    0    0    1    0    0    0    0     0
res$objval
# [1] 8.557704

在此解决方案中，A 中的节点 1 被分配给 B 中的节点 8，A 中的节点 2 被分配给节点 7来自 B 等