Opened 6 years ago
Closed 6 years ago
#21871 closed enhancement (fixed)
Test if a graph is apex
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  David Coudert  Reviewers:  Jori Mäntysalo 
Report Upstream:  N/A  Work issues:  
Branch:  c3cc369 (Commits, GitHub, GitLab)  Commit:  c3cc3690826d03815c20b9a0a7b98f49403ac09a 
Dependencies:  Stopgaps: 
Description (last modified by )
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/.
Change History (18)
comment:1 Changed 6 years ago by
 Branch set to u/dcoudert/isapex
 Commit set to ca66bdfa69b96de5e68870f43f5085c1a523a8d7
comment:2 Changed 6 years ago by
 Description modified (diff)
 Status changed from new to needs_review
Ready to be reviewed.
comment:3 Changed 6 years ago by
 Commit changed from ca66bdfa69b96de5e68870f43f5085c1a523a8d7 to 5559320ae415c93de5d70c599df37956164a9e65
Branch pushed to git repo; I updated commit sha1. New commits:
5559320  trac #21871: fix documentation

comment:4 Changed 6 years ago by
 Summary changed from Test if a graph is apx to Test if a graph is apex
comment:5 Changed 6 years ago by
I think that just if certificate:
would be good. It is how many certificateoptions 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.
comment:6 Changed 6 years ago by
 Status changed from needs_review to needs_work
Fails for immutable graphs > needs_work.
comment:7 Changed 6 years ago by
 Commit changed from 5559320ae415c93de5d70c599df37956164a9e65 to 7f56f93832b68d7b6b7569c27541e71be0b85fb8
comment:8 Changed 6 years ago by
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.
comment:9 Changed 6 years ago by
I would prefer adding apex_vertices()
. (With SEEALSOcrosslinks in docstrings of course. I would also crosslink is_planar
<> is_apex
.)
comment:10 Changed 6 years ago by
 Commit changed from 7f56f93832b68d7b6b7569c27541e71be0b85fb8 to d6600e278a23039f1feac80545ffdaf67c727a80
comment:11 Changed 6 years ago by
 Status changed from needs_work to needs_review
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.
comment:12 followup: ↓ 15 Changed 6 years ago by
 Reviewers set to Jori Mäntysalo
 Status changed from needs_review to needs_work
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 sagedevel, 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 toapex_vertices()
. len(apex)>=k
should belen(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.
comment:13 Changed 6 years ago by
 Commit changed from d6600e278a23039f1feac80545ffdaf67c727a80 to 5fbdf8867de3cfd7bb0a237dc8ca979126e500d2
Branch pushed to git repo; I updated commit sha1. New commits:
5fbdf88  trac #21871: various corrections

comment:14 Changed 6 years ago by
 Commit changed from 5fbdf8867de3cfd7bb0a237dc8ca979126e500d2 to c3cc3690826d03815c20b9a0a7b98f49403ac09a
Branch pushed to git repo; I updated commit sha1. New commits:
c3cc369  trac #21871: improve copies

comment:15 in reply to: ↑ 12 ; followup: ↓ 16 Changed 6 years ago by
 Status changed from needs_work to needs_review
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 sagedevel, 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 toapex_vertices()
.
done
len(apex)>=k
should belen(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.
comment:16 in reply to: ↑ 15 Changed 6 years ago by
 Status changed from needs_review to positive_review
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.
comment:17 Changed 6 years ago by
Thank you for the review.
comment:18 Changed 6 years ago by
 Branch changed from u/dcoudert/isapex to c3cc3690826d03815c20b9a0a7b98f49403ac09a
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #21871: add method to test if a graph is apex