is_bipartite() is confusing / problematic

[szhorvat]

Before you read further, please guess what you think the is_bipartite() function does, if you are not already familiar with it.

---

No, it's not the same as igraph_is_bipartite() in C, .is_bipartite() in Python or IGBipartiteQ[] in Mathematica. Those functions decide if the graph is bipartite (i.e. 2-colourable) in the graph theoretical sense.

is_bipartite() in R simply checks whether a graph has a type vertex attribute. This is documented, but in a way that is somewhat confusing, and easy to miss. It's at the bottom of the doc page:

is_bipartite() checks whether the graph is bipartite or not. It just checks whether the graph has a vertex attribute called type.

In plain words, the term "bipartite" in R/igraph is used differently than just about anywhere else. We should consider changing this terminology in igraph 2.0, so it lines up better with common usage.

2-colourability is checked by bipartite_mapping().

[ghost]

The problem being discussed is regarding the is_bipartite() function in the R/igraph package. As opposed to its name, the function doesn't determine whether a graph is 2-colorable or bipartite. Instead, it only checks whether the graph has a vertex attribute called "type".

To address this issue, it has been recommended to change the terminology used in R/igraph to better align with common usage. It has also been suggested that the bipartite_mapping() function be used instead to determine if a graph is 2-colorable or bipartite in the graph theoretical sense.

I hope this explanation helps clarify the issue at hand.

[schochastics]

We should definitely work on this, because I 100% agree with you that this is problematic and confusing. I think is_bipartite() in its current form is pretty useless and should rather forward to the real bipartite check

[szhorvat]

See what I wrote here:

https://github.com/igraph/rigraph/issues/520#issuecomment-2690092787

If we want to keep the functionality of the current is_bipartite() perhaps we can start by coming up with another name for the concept, such as "two-mode network" and rename it to is_two_mode()?

Or do we want to drop this functionality entirely? That would probably break too many things.

[schochastics]

The distinction of bipartite/two-mode is something many practitioners don't understand. They use the terms interchangeable although that is very wrong (Every two-mode network is a bipartite graph but not every bipartite graph is a two-mode network). I wonder how much confusion it would create if these terms are now distinguished. I think for the start, it is enough to also check for "true" bipartivity in is_bipartite but also keep the type check. But I will need to think about this more. I think it is not a trivial issue

[schochastics]

The docs of is_bipartite() do actually reflect what the function does better than what is written above.

#' @description It does not check whether the graph is bipartite in the
#'  mathematical sense.  Use [bipartite_mapping()] for that.

[schochastics]

use in R packages on CRAN:

tidygraph: (just a wrapper)

multinets (needs TRUE/FALSE types) https://github.com/cran/multinets/blob/3b10deb72cee6b3331864a1c361426f027a0c91b/R/is_multilevel.R#L36-L59

is_multilevel <- function(x){
  if (!inherits(x, 'igraph')){
    stop("Not a graph object")
  } else {
    if(igraph::is_bipartite(x)){
      falsos <- which(igraph::vertex_attr(x, "type") == FALSE)
      vizinhanca <- igraph::ego(x, nodes = igraph::V(x)[falsos])

manynet

is_twomode.igraph <- function(.data) {
  igraph::is_bipartite(.data)
}

grand (needs TRUE/FALSE type)

 if (bipartite) {
    G$grand$vertex1 <- scan2(cat("This network contains", sum(igraph::V(G)$type==FALSE), "top nodes. What type of entity do these represent (e.g., people)?"), type = "character")
    G$grand$vertex2 <- scan2(cat("This network contains", sum(igraph::V(G)$type==TRUE), "bottom nodes. What type of entity do these represent (e.g., people)?"), type = "character")
  }

incidentally (bipartivity check)

if (igraph::is_bipartite(G)) {stop("G must be unipartite")}

ghypernet (bipartivity check)

if(igraph::is_bipartite(graph)){
    adj <- igraph::get.incidence(graph = graph, sparse = FALSE)
  } else{
    adj <- igraph::get.adjacency(graph = graph, type = "upper", sparse = FALSE)

apart from that, there are ~100 hits on GitHub, none seem crucial if we break stuff