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.

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.

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

Similar Questions

I'm quite new to SQL and have a question about matching names from two columns located within a table: Let's say I want to use the soundex() function to match two columsn. If I use this query: SELECT

I have a message composed of closely matching strings . I want to remove closely matching strings from message . By close i mean like if two strings match upto 80% of their total length , then one of

I seen examples of jgraph and jgrapht and there easy to follow but now sure how I would go about using the CompleteBipartiteGraph? How is the syntax to be used to instantiate the graph? http://jgrapht

I'm trying to make a HopcroftKarpBipartiteMatching but none of demos or I can't really find anything else to help me with using the library. I can't figure out from documentation how and what is requi

I have faced the following problem: there are two disjoint sets, A and B for each pair of elements (a, b) (a belongs to set A, where b belongs to set B) there a probability pij is known in advance. I

I have a data.frame which describes a bipartite graph with a very large (millions) and a reasonably small (hundreds) independent sets. I want to get the bipartite projection of the graph on the smalle

So I'm passing a ClientID to my DB and using that to look up all their details, then I want to use those details to also get all other users closely matching the details. I have all this written but m

Let's say I have two sets: (n_1, n_2, ...) and (m_1, m_2, ...) and a matching function match(n, m) that returns a value from 0 to 1. I want to find the mapping between the two sets such that the follo

I'm trying to create a bipartite graph w/ R's igraph package, but having a devil of a time. Can anyone tell me why this works: g <- graph.bipartite( rep(0:1,length=10), c(0,1,2,3,4,5,6,7,8,9)) But

I have two sets: #{1 2 3} and #{7 8 3} and I'd like to create a function that returns just the shared values of each set, 3. I can't use intersection; it doesn't work with my current version of clojur

Let's say I have two kinds of items data Item1 = A | B | C data Item2 = D | E | F And two sets set1 = [A,B,C] set2 = [D,E,F] I would like to find all unique ways of matching the items from two sets

Problem: I want to suggest the top 10 most compatible matches for a particular user, by comparing his/her 'interests' with interests of all others. I'm building an undirected weighted graph between us

I have two time series of share prices, Price1 and Price2. Tday is the time series of the dates which match for both prices. Now I am trying to match the prices of each to the newly established tday (

In regards to Operating System concepts... Can a process to have two working sets, one that represents data and another that represents code?

I would like to create bipartite networks in R. For example, if you have a data.frame of two types of species (that can only interact across species, not within species), and each species has a trait

Consider the following Scala code. val a = both a match { case both | foo => println (foo) // case 1 case both | bar => println (bar) // case 2 } I would like match to work so tha

#\b^([0-9]{7,8}(\s/[0-9]{4})?|Charges|[\-]{3}|UNIVERSAL\sCONNECTIVITY-DCS|FEDERAL\sREGULATORY\sFEE-DCS|PROPERTY\sTAX\sALLOTMENT-DCS|ADMINISTRATIVE\sEXPENSE\sFEE-DCS)\b#m I'm trying to do a match on a

Say I have two sets var Set1 = new[] { A, B, C }; var Set2 = new[] { 1, 2, 3 }; To concat these two sets usually i do foreach (string itm1 in Set1 ) { foreach (string itm2 in Set2) { Cons

I am working on concept of semantic noun match between source and target languages. I need to retrieve an individual noun from target language based on matching of property-values between source a

I'm looking for a concise way to compare two arrays for any match. I am using this comparison to apply a particular style to any table cell that has matching content. One array is a static list of co

I want to do a calculation using two different datasets, but I cant seem to do it in the expression field. Any ideas on how I can add, multiply or divide using the two datasets? In the Fields, I added

Two model classes AUser - name AGroup - users Groups and Users share a many-to-many relationship. I wish to check whether two sets share the exact same users (not more users or less users) But unfort

I'm fairly new to F# and I wanted to compare two values with the (match ... with ...) syntax The problem arises when I attempt to compare two values like this: let value1 = 19 let isValue1 y = match y

I am trying to translate the following imperative code to a functional solution in Haskell. I want to compare the members of set s with members of set s' and update sets t and t' based on the comparis

For example, let us take two sets of nodes n1, n2 in left column and n3, n4 in the right column Now there are edges between (n1,n3) and (n1,n4). Node n2 has no edges. Is such a graph bipartite graph ?

Problem: We are given two arrays A & B of integers. Now in each step we are allowed to remove any 2 non co-prime integers each from the two arrays. We have to find the maximal number of pairs that

I'm having trouble with a query I'm trying to do. I'm trying to select values that come up in to result sets. I'm currently dealing with two queries: A) SELECT /*+ RULE */ pi.compressed_name, pi.phn,

I've found matching { this kind of stuff } to be a piece of cake: {stuff}.match(/{([^}]*)}/)[1] But that'll stop after the first closing brace. I can't figure out how to get it to ignore matching

I can't figure out what does this regex match: A: \\/\\/c\\/(\\d*) B: \\/\\/(\\d*) I suppose they are matching some kind of number sequence since \d matches any digit but I'd like to know an examp

I have the following code which is an implementation of BPM (bipartite matching, from graph theory) #include <iostream> #include <cstring> using namespace std; #define M 128 #define N 128

This question already has an answer here: Elegant way to merge two arrays as key value pairs in PHP? 4 answers I have two arrays with matching keys and I need to merge the values of both into a

I have this data in a LONGTEXT column (so the line breaks are retained): Paragraph one Paragraph two Paragraph three Paragraph four I'm trying to match paragraph 1 through 3. I'm using this code: pre

Please could someone explain to me why this regex does not match anything, when it should: preg_match('@<title>([^<].)</title>@',$meta,$match); I'm trying to match everything between t

How do you construct a csv for a bipartite graph. I have the following data set: ID, Source, Target, Weight 1,00ash00,t3_ascto,-1 2,00ash00,t3_asll7,1 3,00ash00,t3_atawm,1 4,00ash00,t3_avosd,1 5,0-0,t

I'm having some problems trying to plot two different data sets from stdin in gnuplot... This is the command I'm testing with: % gnuplot -persist <<EOF plot '-' index 0 with points, \ '' index

I am building a small project for spelling correction, this is not homework. Given two strings str1 and str2. One has to find out the number of characters matching between two strings. For example if

Given bipartite graph. Each vertex has some integer value - weight. Is it possible to find maximum weighted independent vertex set in this graph in polynomial time? If such solution exists, what is

Drake and Hougardy find a simple approximation algorithm for the maximum weighted matching problem. I think my understanding of academic papers is above my capabilities so I'm looking for an easy impl

In a bipartite graph, there are n nodes on the left and m nodes on the right. Nodes are ordered from 1 to n and 1 to m. A node on the left is connected to the node on the right. All the nodes are not

I want to combine two separate sets of conditions,like (A) OR (B AND c AND d) in Google Analytics Data Query Filter This is what i want exclude all visits: *coming from the US* OR *`coming from sourc

I have two articles ( plain text ), i am looking to match the first article with the second article and highlight the matched data. SCENARIO: ARTICLE(A) Lorem Ipsum is simply dummy text of the printin

I've come across a situation where I would like to pattern match on operators. However, this throws a Pattern match(es) are overlapped error with GHC. I can't figure out why. Is pattern matching on op

is there some jQuery code to swap 2 sets of elements with animation? i only found Move list item to top of unordered list using jQuery but its too limited (only slide element to top and not accounting

Given two sets, each containing integer values, how could one find a set containing all possible pair-wise ORs of the values of those two sets? E.g. (all numbers are binary) {1, 10} x {100, 1000} = {1

I am looking for two consecutive lines matching a certain pattern, say containing word 'pat' using sed and have noticed that I am able to detect it sometimes with this command: sed -n 'N; /.*pat.*\n.*

I have a lot of strings which have characters like [anything] where the word anything == any kind of characters, such as ~!@#$%^&*() what will be the preg_match() code for matching such string

After some tests I observer that the stamp_times visitor is the problem: typedef adjacency_list <vecS, vecS, undirectedS> Graph; typedef graph_traits <Graph>::edge_descriptor Edge; typedef

In undertaking web site design/programming projects, I was wondering if it is common for the gurus to keep two sets of files. One for development, and one for production as in jQuery. The reason is th

I want to be able to extract two sets of data in one script with a total of 15 records. In my scenario, I extract members from a certain town which for example could return 3 records, and then I want

trying to understand preg_match, struggling to understand how to write and how to access what it has matched. For example: Every single movie name I have is in the format-- MOVIE NAME (YEAR) e.g. Alic