二部图匹配以匹配两组 [英] bipartite graph matching to match two sets

问题描述

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

I'm a newbie to igraph package in R. I have two sets A and B, each with N vertices (A1, A2, ..., AN) and (B1, B2, ..., BN). There is an edge between every element of A to every element of B, and I have a function fWgt(Ai, Bj) that returns the weights of the edge between Ai and Bj.

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

I have been trying to use the igraph package in R to do a weighted maximum bipartite matching, but I haven't been able to formulate the problem as per the igraph package. For instance, in the example given for maximum.bipartite.matching function in the igraph package:

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)

我不知道如何使用graph.formula重新设置我的问题(通过fWgt函数设置A，B，边)?示例中的str函数似乎可以设置边缘，但是对于我的情况，str函数等效于什么?

I couldn't figure out how to reformulate my problem (sets A, B, edges by fWgt function) using graph.formula? The str function in the example appears to set the edges, but what would be the equivalent of the str function for my case?

*编辑*

感谢您的答复.我只能在SO上选择一个.

Thanks for both your replies. I can only select one on SO.

推荐答案

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

I'm not familiar with the maximum.bipartite.matching function in the igraph package, but you can solve this as an assignment problem with the lp.assign function in the lpSolve package:

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，依此类推.

In this solution, the node 1 from A is assigned to node 8 from B, node 2 from A is assigned to node 7 from B, etc.

这篇关于二部图匹配以匹配两组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！