Test if a graph is apex

[dcoudert]

A graph is apex if it can be made planar by the removal of a single vertex. See ​`the wikipedia article on Apex graph` for more details.

I wrote this method after reading ​`this question` on ​https://ask.sagemath.org/.

[dcoudert]

New commits:

​ca66bdf

trac #21871: add method to test if a graph is apex

[dcoudert]

Ready to be reviewed.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5559320

trac #21871: fix documentation

[jmantysalo]

I think that just if certificate: would be good. It is how many certificate-options are currently done, i.e. for example P.dimension(certificate=[]) works a poset P. It is "pythonic" way to code.

I am not sure about the design where certificate kind of returns list of all possible "certificates". I would make two functions, other to be apex_vertices() or something like that. But maybe others can comment this too.

[jmantysalo]

Fails for immutable graphs --> needs_work.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a2d6f68	trac #21871: immutable graphs
​7f56f93	trac #21871: add feature to graph_classes

[dcoudert]

So far I fixed the issue with immutable graphs, and I also added the feature to graph_classes. So we can write:

sage: G = graphs.PetersenGraph()
sage: G in graph_classes.Apex
False
sage: G = graphs.Grid2dGraph(5,5)
sage: G in graph_classes.Apex
True
sage: G = graphs.RandomBarabasiAlbert(100,2)
sage: G = G.copy(immutable=True)
sage: G.is_immutable()
True
sage: G in graph_classes.Apex
False
sage: G.is_apex()
False
sage: G = graphs.Grid2dGraph(5,5)
sage: G.add_path([(1,1),'x',(3,3)])
sage: G = G.copy(immutable=True)
sage: G in graph_classes.Apex
True

Now, concerning the behavior of certificate. You are right that it is too complex. What I could do is either to return the list of apex vertices when set to True, or to remove that parameter from method is_apex and add a method apex_vertices. Let me know what you prefer.

David.

[jmantysalo]

I would prefer adding apex_vertices(). (With SEEALSO-crosslinks in docstrings of course. I would also crosslink is_planar <-> is_apex.)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6e65d41	trac #21871: add seealso sections
​d6600e2	trac #21871: add method apex_vertices

[dcoudert]

I have added method apex_vertices with a parameter to limit the number of returned apex vertices. This is mostly useful for the is_apex method which only ask for one apex vertex.

I have also added the see also sections.

[jmantysalo]

OK, this works. One note about code and some bikeshedding:

Why

H = Graph([e for e in self.edge_iterator(labels=0)], immutable=False)

and not just H = self.to_simple()?

• Exception string should start with lowercase and not end to a dot. I don't like it, but this was discussed in sage-devel, and this is how plain Python does.
• Example "A 2D grid is apex, and it remains apex when adding a universal vertex" is odd at is_apex(), when you do not add the apex vertex. Maybe that example could be removed, and left only to apex_vertices().
• len(apex)>=k should be len(apex) >= k. This is some PEP whose number I don't remember.
• Input parameter "k: when" should be "k -- when", copy the format from some existing function.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5fbdf88

trac #21871: various corrections

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c3cc369

trac #21871: improve copies

[dcoudert]

Replying to jmantysalo:

OK, this works. One note about code and some bikeshedding:

Why

H = Graph([e for e in self.edge_iterator(labels=0)], immutable=False)

and not just H = self.to_simple()?

I could use self.to_simple(immutable=False). However, here we don't care of labels and the to_simple method only proposes to keep all, min or max labels. No clear option is proposed to remove labels. So I prefers to use H = Graph(self.edges(labels=0), immutable=False, loops=False, multiedges=False) to get a clean and light copy.

• Exception string should start with lowercase and not end to a dot. I don't like it, but this was discussed in sage-devel, and this is how plain Python does.

ok.

• Example "A 2D grid is apex, and it remains apex when adding a universal vertex" is odd at is_apex(), when you do not add the apex vertex. Maybe that example could be removed, and left only to apex_vertices().

done

• len(apex)>=k should be len(apex) >= k. This is some PEP whose number I don't remember.

Well, it would be weird to remember all these numbers ;)

• Input parameter "k: when" should be "k -- when", copy the format from some existing function.

Right, I forgot.

Thanks for the comments.

[jmantysalo]

Thanks. No more comments.

Replying to dcoudert:

the to_simple method only proposes to keep all, min or max labels. No clear option is proposed to remove labels.

Ah, OK. I guess it should have an option for that, but that's a place for another ticket.

[dcoudert]

Thank you for the review.