匹配两组的二部图匹配

Question

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

我一直试图使用R中的igraph包来进行加权最大二分匹配，但是我还无法按照igraph包来描述这个问题。例如，在maximum.bipartite.matching包中为igraph函数提供的示例中：

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)

我想不出如何用A重新构造问题(用fWgt函数设置graph.formula、B、edges )？示例中的str函数似乎设置了边，但是对于我的情况，str函数的等效性是什么呢？

*编辑*

谢谢你们两位的答复。我只能在上面选一个。

Answer 1

我不熟悉igraph包中的igraph函数，但您可以将此作为lpSolve包中的lp.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被从B分配给节点7，等等。

Answer 2

igraph包附带了一个很好的内置函数graph.full.bipartite，您可以使用它来创建二分图，而不是graph.formula。请注意，str没有设置边缘，这是一种检查您创建的图形是否确实符合您所需的方法。

一旦你创建了二分图并设置了边权，它只是得到最大匹配的一条线。

下面是一个N=5的例子。(总共有10个顶点，每个边5个。)

#create the graph
N <- 5
g3 <- graph.full.bipartite (N,N)
#Name the vertices A1...AN and B1..BN
V(g3)$name <- c(paste0("A", 1:N), paste0("B", 1:N))
#set the edge weights
set.seed(122)
E(g3)$weight <- sample(10,N^2, replace=T) #use your fWgt function here instead

#verifty if we did things right
str(g3, TRUE)
is.bipartite(g3)

maximum.bipartite.matching(g3)
#$matching_size
#[1] 5
#
#$matching_weight
#[1] 37
# 
#$matching
#  A1   A2   A3   A4   A5   B1   B2   B3   B4   B5 
#"B1" "B2" "B4" "B3" "B5" "A1" "A2" "A4" "A3" "A5"