bipartite graph matching to match two sets

Question

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.

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)

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?

* EDIT *

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

Answer 1

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

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.

Answer 2

The igraph package comes with a nice built-in function graph.full.bipartite which you could use to create your bipartite graph, instead of graph.formula. Note that str is not setting the edges, it is a way to inspect that the graph you create is indeed what you wanted.

Once you have created the bipartite graph and set the edge weights, it is just a one line to get the maximal matching.

Here's an example with N=5. (Total of 10 vertices, 5 on each side.)

#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"