38 views

Skip to first unread message

Dec 14, 2011, 2:04:03 PM12/14/11

to sage-devel

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

Dec 14, 2011, 2:29:59 PM12/14/11

to sage-devel

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.

> 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

Dec 14, 2011, 3:41:43 PM12/14/11

to sage-devel

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

Dec 14, 2011, 7:23:35 PM12/14/11

to sage-devel

On Dec 14, 12:41 pm, fidelbc <fidel.barr...@gmail.com> wrote:

> Here it is, ticket number 12155.

> 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

Dec 15, 2011, 3:36:30 AM12/15/11

to sage-...@googlegroups.com

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 :

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

Dec 15, 2011, 8:38:56 AM12/15/11

to sage-...@googlegroups.com

I think that sounds reasonable. +1.

Jason

Dec 16, 2011, 12:57:16 AM12/16/11

to sage-devel

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.

> 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.

Dec 18, 2011, 5:11:56 AM12/18/11

to sage-...@googlegroups.com

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

Nathann

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu