Bug when taking complement of bipartite graph?

[fidelbc]

Hi all,

I'm running sage 4.7.2. While trying the matching polynomial function
for graphs I found the following

sage: g=graphs.CompleteBipartiteGraph(3,3)
sage: g.matching_polynomial()
...
RuntimeError: Edge vertices must lie in different partitions.

After reading the documentation I tried

sage: g.matching_polynomial(False)
x^6 - 9*x^4 + 18*x^2 - 6

And I think the problem arises when taking complement.

sage: g.complement()
...
RuntimeError: Edge vertices must lie in different partitions.

Perhaps the complement is constructed as a bipartite graph too, which
is not true in general.

Thanks,
Fidel

[Rob Beezer]

On Dec 14, 11:04 am, fidelbc <fidel.barr...@gmail.com> wrote:
> And I think the problem arises when taking complement.
>
> sage: g.complement()
> ...
> RuntimeError: Edge vertices must lie in different partitions.
>
> Perhaps the complement is constructed as a bipartite graph too, which
> is not true in general.

Yes, it would appear that the generic complement() method is adding
edges to a bipartite graph object and the error is coming from the
bipartite graph routines complaining about an illegitimate edge. I
would imagine that temporarily you could convert your bipartite graph
to a generic graph before taking the complement.

Long-term, maybe the bipartite graph object should implement its own
complement, which creates a generic graph and then calls the generic
complement on that? (Though I have not studied the situation too
carefully.) Can you make a Trac ticket and point back to this
discussion?

Thanks,
Rob

Rob

[fidelbc]

Here it is, ticket number 12155.

http://trac.sagemath.org/sage_trac/ticket/12155

> Yes, it would appear that the generic complement() method is adding
> edges to a bipartite graph object and the error is coming from the
> bipartite graph routines complaining about an illegitimate edge.  I
> would imagine that temporarily you could convert your bipartite graph
> to a generic graph before taking the complement.
>
> Long-term, maybe the bipartite graph object should implement its own
> complement, which creates a generic graph and then calls the generic
> complement on that?  (Though I have not studied the situation too
> carefully.)  Can you make a Trac ticket and point back to this
> discussion?

It appears that BipartiteGraph (bipartite_graph.py) is using the
complement method from Generic graph (generic_graph.py), which when
constructing the complement G of self on line 11933 does

G=copy(self)

Maybe here is where the bipartite property gets transferred to G.

If my counting is right, there are only 8 bipartite graphs whose
complements are also bipartite (and each of them has at most 4
vertices). Would it be useful to preserve the bipartiteness property
when taking complement in any of these instances? If so, maybe
implement this in the BipartiteGraph complement method. I am also
thinking that the complement method in the BipartiteGraph could just
do something like

return Graph(self.edges()).complement()

Thanks,
Fidel

[Rob Beezer]

On Dec 14, 12:41 pm, fidelbc <fidel.barr...@gmail.com> wrote:
> Here it is, ticket number 12155.

Thanks.

> G=copy(self)
>
> Maybe here is where the bipartite property gets transferred to G.

I'd say so.

> If my counting is right, there are only 8 bipartite graphs whose
> complements are also bipartite (and each of them has at most 4
> vertices). Would it be useful to preserve the bipartiteness property
> when taking complement in any of these instances? If so, maybe
> implement this in the BipartiteGraph complement method.

That's a good thing to think about, but with so few graphs, and all so
tiny, it doesn't strike me as worth the effort or the side effect of
returning objects of slightly varying types.

> I am also
> thinking that the complement method in the BipartiteGraph could just
> do something like
>
> return Graph(self.edges()).complement()

Note the following alternative, which has the bonus of preserving some
of the naming of the graph. This would at least fix the bug.

sage: G=graphs.CompleteBipartiteGraph(3,3)
sage: Graph(G).complement()
complement(Complete bipartite graph): Graph on 6 vertices
sage: Graph(G.edges()).complement()
complement(): Graph on 6 vertices

However, in either case it seems very inefficient to create all of the
original edges, just to turn around and destroy them all right away.
I'm not finding a method that converts a BipartiteGraph into a Graph
with very little overhead. Maybe the present example illustrates the
need for such a thing.

Rob

[Nathann Cohen]

However, in either case it seems very inefficient to create all of the
original edges, just to turn around and destroy them all right away.
I'm not finding a method that converts a BipartiteGraph into a Graph
with very little overhead.  Maybe the present example illustrates the
need for such a thing.

Oh, I answered on the other thread :

https://groups.google.com/forum/#!topic/sage-devel/UrPU-0xzzGc

Well, I'd vote for the solution : "do not return BipartiteGraph instances when not explicitely asked", as is the case here. When a bipartite graph is created nothing ensures that the user wants to keep it this way, and even though he may some methods inherited by BipartiteGraph class may not think about it the same way.

Nathann

[Jason Grout]

I think that sounds reasonable. +1.

Jason

[Rob Beezer]

On Dec 15, 12:36 am, Nathann Cohen <nathann.co...@gmail.com> wrote:
> Well, I'd vote for the solution : "do not return BipartiteGraph instances
> when not explicitely asked", as is the case here.

That sounds good to me too.

[Nathann Cohen]

Keeping the thread updated --> here is the patch : http://trac.sagemath.org/sage_trac/ticket/12155

Nathann