Improve max_bipartite_match()

[clpippel]

Suggested improvements.

Documentation
Link: https://igraph.org/r/html/1.3.5/matching.html

• The line V(g)$type <- c(FALSE,TRUE) is incorrect and should be :
  V(g)$type <- rep(c(FALSE,TRUE), length.out=vcount(g2)) as in the example for graph g2.
• Weights not strictly positive are converted to NA in $matching without warning.
• Nice to have: relevant citation to the push-relabel maximum flow algorithm.
• Describe the handling of multiple maximum matchings. Value is not a list of all maximum matchings.

Directed and undirected graphs
When umdirected, the function returns edges twice, e.g. x-y, y-x.
Is this intentional, compatible withe the C-core?
Or should it be like in as_edgelist(), each undirected edge is reported once?

Interfacing with other functions
Consider the following:

g3 <- make_full_bipartite_graph(3,2)
V(g3)$name   <- LETTERS[seq_along(g3)]
wts <- seq_along(E(g3)) + 10

E(g3)$label  <- wts
E(g3)$weight <- wts
E(g3)$color  <- "darkgrey"
E(g3)$width  <- 2
g3
#
# IGRAPH 41acddf UNWB 5 6 -- Full bipartite graph
# + attr: name (g/c), type (v/l), name (v/c), label (e/n), weight (e/n),
# | color (e/c), width (e/n)
# + edges from 41acddf (vertex names):
# [1] A--D A--E B--D B--E C--D C--E
#
plot(g3, layout=layout_as_bipartite)

match <- max_bipartite_match(g3)
match

This gives:

$matching_size
[1] 2

$matching_weight
[1] 29

$matching
  A   B   C   D   E 
 NA "E" "D" "C" "B" 

$matching represents the edges B-E, C-D, D-C, E-B.
Note that this fails if the graph is named and two vertices have the same name.
This representation is rather unusual and confusing. Interfacing with other igraph functions is not straightforward.
As an example lets assume we want to color the edges of the calculated covering.

cover <- match$matching

# The calculated vertices, interpreted pairwise, for (un)named graphs.
if (is_named(g3)) 
  vp    <- rbind(names(cover), cover) else
  vp    <- rbind(seq_along(g3), cover) 
vp <- c(vp[ , colSums(is.na(vp))==0]) # remove NA.

# The edge ids of the edges incident with vp.
eids              <- get_edge_ids(g3, vp)
E(g3)[eids]$color <- "red"          # Mark the cover edges.
E(g3)[eids]$width <- 3
plot(g3, layout=layout_as_bipartite)

Proposal
The format of the matching component differs from igraph conventions.
My proposal is to add (at least one of) the components:

• $vp, the incident vertices, interpreted pairwise as in make_graph().
• $eids, the sequence of edge ids as in subgraph.edges().

How to interface

match      <- max_bipartite_match(g3)
match$vp   <- vp    # proposal.
match$eids <- eids  # proposal.
dev.new(); make_graph(match$vp, directed=FALSE) |> simplify(remove.multiple = TRUE) |> plot()
dev.new(); (gs <- subgraph.edges(g3, match$eids, delete.vertices = TRUE)) |> plot()
data.frame(ends(gs, E(gs)), Weight = E(gs)$weight)  # Print weights
#
#   X1 X2 Weight
# 1  B  E     14
# 2  C  D     15

See also

• https://igraph.discourse.group/t/weighted-perfect-matching-e-g-blossom-algorithm/1934
• New feature: maximum matching of general graph #2550