Opened 5 years ago

Closed 5 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:

Status badges

Description (last modified by 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/.

Change History (18)

comment:1 Changed 5 years ago by dcoudert

  • Branch set to u/dcoudert/isapex
  • Commit set to ca66bdfa69b96de5e68870f43f5085c1a523a8d7

New commits:

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

comment:2 Changed 5 years ago by dcoudert

  • Description modified (diff)
  • Status changed from new to needs_review

Ready to be reviewed.

comment:3 Changed 5 years ago by git

  • Commit changed from ca66bdfa69b96de5e68870f43f5085c1a523a8d7 to 5559320ae415c93de5d70c599df37956164a9e65

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

5559320trac #21871: fix documentation

comment:4 Changed 5 years ago by dcoudert

  • Summary changed from Test if a graph is apx to Test if a graph is apex

comment:5 Changed 5 years ago by 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.

comment:6 Changed 5 years ago by jmantysalo

  • Status changed from needs_review to needs_work

Fails for immutable graphs --> needs_work.

comment:7 Changed 5 years ago by git

  • Commit changed from 5559320ae415c93de5d70c599df37956164a9e65 to 7f56f93832b68d7b6b7569c27541e71be0b85fb8

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

a2d6f68trac #21871: immutable graphs
7f56f93trac #21871: add feature to graph_classes

comment:8 Changed 5 years ago by 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.

comment:9 Changed 5 years ago by jmantysalo

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

Last edited 5 years ago by jmantysalo (previous) (diff)

comment:10 Changed 5 years ago by git

  • Commit changed from 7f56f93832b68d7b6b7569c27541e71be0b85fb8 to d6600e278a23039f1feac80545ffdaf67c727a80

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

6e65d41trac #21871: add seealso sections
d6600e2trac #21871: add method apex_vertices

comment:11 Changed 5 years ago by dcoudert

  • 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: Changed 5 years ago by jmantysalo

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

comment:13 Changed 5 years ago by git

  • Commit changed from d6600e278a23039f1feac80545ffdaf67c727a80 to 5fbdf8867de3cfd7bb0a237dc8ca979126e500d2

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

5fbdf88trac #21871: various corrections

comment:14 Changed 5 years ago by git

  • Commit changed from 5fbdf8867de3cfd7bb0a237dc8ca979126e500d2 to c3cc3690826d03815c20b9a0a7b98f49403ac09a

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

c3cc369trac #21871: improve copies

comment:15 in reply to: ↑ 12 ; follow-up: Changed 5 years ago by dcoudert

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

comment:16 in reply to: ↑ 15 Changed 5 years ago by jmantysalo

  • 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 5 years ago by dcoudert

Thank you for the review.

comment:18 Changed 5 years ago by vbraun

  • Branch changed from u/dcoudert/isapex to c3cc3690826d03815c20b9a0a7b98f49403ac09a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.