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: | sage-7.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 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.
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 SEEALSO-crosslinks 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 follow-up: ↓ 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 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 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 ; follow-up: ↓ 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 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 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