Ask Your Question
0

Testing planarity on embedding gives wrong result

asked 2015-03-24 06:19:41 -0500

mitchondra gravatar image

updated 2015-03-24 07:36:28 -0500

tmonteil gravatar image

Hi, i've got planar embedding of K_4 which is not planar, but when I test it with is_planar(on_embeding=emb), it says that it is planar. Code:

g = graphs.CompleteGraph(4)
g.is_planar(set_embedding=True)
True
emb = {0 : [2,3,1], 1: [2,3,0], 2: [1,3,0], 3:[0,1,2]}
g.is_planar(on_embedding=emb)
True

So, what am I doing wrong?

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
0

answered 2015-03-24 07:28:51 -0500

Nathann gravatar image

Hello !

You did nothing wrong, and just came across a bug. I fixed it in ticket 18045 [1], but this code will only make it into Sage when somebody will have taken the time to review it (everybody can do it).

If you use this code often, it would help if you could learn our workflow a bit to help us. The 'embedding/planarity' part of Sage's graph code has been written a long time ago, and while I fix it from time to time I never use it myself and do not know the code very well.

Have fuuuuuuuuuuuuuun,

Nathann

[1] http://trac.sagemath.org/ticket/18045

edit flag offensive delete link more

Comments

Thanks! This was the second time I used Sage for planarity testing, so I thought it was rather my mistake. By the way, why were the computations run on cached embedding, instead of mine? (I did't get from the report)

mitchondra gravatar imagemitchondra ( 2015-03-24 07:57:56 -0500 )edit

Because some subfunction of Sage accepts True/False or a dictionary for on_embedding. When checking if the value is equal to True the code read "if on_embedding", but that branch was also taken when on_embedding was a dictionary (i.e. when an embedding is provided). I just moved the test for a dictionary before the test for boolean answers, and that was the end of it. This, and some documentation fixes ;-)

Nathann gravatar imageNathann ( 2015-03-24 08:07:50 -0500 )edit

Ah, I see, thanks. So, do you have any idea how much I can trust this this function (the version before you made it right)? I'm trying to Boyer-Myrvold in C++ and I wanted to use Sage for checking output of my program.

mitchondra gravatar imagemitchondra ( 2015-03-25 16:38:09 -0500 )edit

If you remove set the cached embedding explicitly to be equal to the one you want to test, there should be no problem. Use Graph.set_embedding. This way the computations will run on that one.

Nathann gravatar imageNathann ( 2015-03-28 10:07:46 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2015-03-24 06:19:41 -0500

Seen: 89 times

Last updated: Mar 24 '15