Inspired by yode's latest question I was playing around with RelationGraph
and found that BipartiteQ
seems to be unable to detect certain bipartite results.
As an example, I was looking at the graph where each vertex is a 1- or 2-digit integer, and edges indicate whether a 2-digit integer starts or ends with a 1-digit integer. This is clearly a bipartite graph (and GraphLayout -> "BipartiteEmbedding"
shows this), since there are no edges between 2-digit numbers and no edges between single digits. And up to n = 19
this works fine:
g = RelationGraph[(StringEndsQ[#1, #2] || StringStartsQ[#2, #])
&& # != #2 &, ToString /@ Range[0, 19],
GraphLayout -> "BipartiteEmbedding", VertexLabels -> "Name"]
BipartiteGraphQ @ g
(* True *)
But as soon as I get to 20:
g = RelationGraph[(StringEndsQ[#1, #2] || StringStartsQ[#2, #])
&& # != #2 &, ToString /@ Range[0, 20],
GraphLayout -> "BipartiteEmbedding", VertexLabels -> "Name"]
BipartiteGraphQ @ g
(* False *)
The problem seems to be something internal to the result of RelationGraph
, since extracting the edges and reconstructing the graph works:
BipartiteGraphQ @ Graph @ EdgeList @ g
(* True *)
We can however localise the problem a bit by computing the graph on a smaller set of vertices. It's possible to remove all but 6 vertices/edges and still reproduce the problem:
g = RelationGraph[(StringEndsQ[#1, #2] || StringStartsQ[#2, #])
&& # != #2 &, ToString /@ {0, 1, 2, 10, 12, 20},
GraphLayout -> "BipartiteEmbedding", VertexLabels -> "Name"]
BipartiteGraphQ @ g
(* False *)
Removing any further edges "resolves" the problem.
Is this a bug in BipartiteGraphQ
? Am I misunderstanding something about bipartite graphs?
I'm using Mathematica 10.4 on Windows 10.
GraphLayout -> "BipartiteEmbedding"
still worked without an issue. $\endgroup$IGBipartiteQ
precisely for this reason. <del>But you should know that it is much slower than the built-in function because converting a Mathematica graph to an igraph one is a huge overhead.</del> ... Well, I just tested, and for huge graphs it is in fact faster thanBipartiteGraphQ
despite that conversion overhead!! $\endgroup$