Opened 14 months ago

Closed 14 months ago

Last modified 14 months ago

#26432 closed enhancement (fixed)

clean graph.py

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-8.5
Component: graph theory Keywords:
Cc: tscrim, chapoton Merged in:
Authors: David Coudert Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 20bf46b (Commits) Commit: 20bf46b414286047b944d34026a6cf9ff0cd40db
Dependencies: Stopgaps:

Description (last modified by dcoudert)

We do as much cleaning as possible: alignments, PEP8, avoid many vertex comparisons or sorting, etc.

Change History (18)

comment:1 Changed 14 months ago by dcoudert

  • Branch set to u/dcoudert/26432_clean_graph_py
  • Commit set to 9067797d03b4cbd8fce83d39389b4f0e461258ad

New commits:

9067797trac #26432: first round of improvements

comment:2 Changed 14 months ago by git

  • Commit changed from 9067797d03b4cbd8fce83d39389b4f0e461258ad to 672b173dcdbf4ef8b7e60c96da6869045d8118c9

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

672b173trac #26432: more improvements

comment:3 Changed 14 months ago by dcoudert

  • Cc tscrim chapoton added
  • Description modified (diff)
  • Status changed from new to needs_review

So far, remaining issues are:

  • sorting of output in cliques_maximal and vertex_cover. Should we put a deprecation ? (could be done in a specific ticket)
  • sorting in examples of cliques_number_of, cliques_vertex_clique_number, cliques_containing_vertex. This can be changed here.
  • recursion on method DFS of ear_decomposition. I can do it here or in specific ticket.

Any advise is more than welcome.

comment:4 Changed 14 months ago by jhpalmieri

Edit: sorry, I was wrong about this. It does not help with the homology doctests.

Last edited 14 months ago by jhpalmieri (previous) (diff)

comment:5 Changed 14 months ago by tscrim

Small things that I think should be fixed before a positive review:

sorted(V.keys()) -> sorted(V).

While I understand why, it still looks ugly

+        A snark has chromatic index 4 hence its line graph has chromatic number
+        4::

probably better to also move down number and maybe also chromatic.

The bullet points are over-indented:

         Here are two very simple modules :
 
-            * A connected component `C` (or the union of some --but
-              not all-- of them) of a disconnected graph `G`, for
-              instance, is a module, as no vertex of `C` has a
-              neighbor outside of it.
+            * A connected component `C` (or the union of some --but not all-- of
+              them) of a disconnected graph `G`, for instance, is a module, as
+              no vertex of `C` has a neighbor outside of it.
 
-            * An anticomponent `C` (or the union of some --but not
-              all-- of them) of an non-anticonnected graph `G`, for
-              the same reason (it is just the complement of the
-              previous graph !).
+            * An anticomponent `C` (or the union of some --but not all-- of
+              them) of an non-anticonnected graph `G`, for the same reason (it
+              is just the complement of the previous graph !).

I would move off on the ear_decomposition changes to a separate ticket as this one is big enough (and likely to have conflicts). However, I would probably consider doing the sorting here.

comment:6 Changed 14 months ago by git

  • Commit changed from 672b173dcdbf4ef8b7e60c96da6869045d8118c9 to 868135138dcc4e101fbd44be042bfbf4a8cede9c

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

4685538trac #26432: reviewer's comments
8681351trac #26432: other corrections

comment:7 follow-up: Changed 14 months ago by dcoudert

Thanks for all the comments. I will modify ear_decomposition in a separate ticket.

I have removed sorting from several example. Was not needed.

Concerning the sorting of output in cliques_maximal and vertex_cover. Should we put a deprecation warning ? if so, a dedicated ticket is certainly better (easier to check), no ?

comment:8 in reply to: ↑ 7 Changed 14 months ago by tscrim

Replying to dcoudert:

Concerning the sorting of output in cliques_maximal and vertex_cover. Should we put a deprecation warning ? if so, a dedicated ticket is certainly better (easier to check), no ?

I would say it is fine. There is not a decent reason I can think of why someone should be assuming the output is sorted. Nor was it documented that the output was sorted.

comment:9 Changed 14 months ago by git

  • Commit changed from 868135138dcc4e101fbd44be042bfbf4a8cede9c to 9a648e7c4c64f8f7f3e26bc03871f1711e27e721

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

5b0c7b4trac #26432: remove sorting in vertex_cover and cliques_maximal
d27d578trac #26432: more care in input blocks
9a648e7trac #26432: further corrections

comment:10 Changed 14 months ago by git

  • Commit changed from 9a648e7c4c64f8f7f3e26bc03871f1711e27e721 to 9e5ebb3ba07770cf30daf5082f88f2575afd68c5

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

9e5ebb3trac #26432: spaces in lambda declarations

comment:11 Changed 14 months ago by dcoudert

Concerning the removal of sorting. It was easier than expected and I have not noticed any impact on other methods.

After that I did additional improvements in INPUT blocks and lambda statements.

Further improvements are certainly possible like moving references to the global file, but I suggest to do that only after the giant patch #26423 is closed.

comment:12 Changed 14 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Thanks. LGTM.

comment:13 Changed 14 months ago by dcoudert

  • Status changed from positive_review to needs_review

The python3_py test of the patchbot indicates the following issue

+ @@ -2141,34 +2117,40 @@ class Graph(GenericGraph):
+        for u,d in six.iteritems(H.degree(labels=True)):
Python3 incompatible code inserted on 1 non-empty lines

I'm pushing a small change to fix that.

comment:14 Changed 14 months ago by git

  • Commit changed from 9e5ebb3ba07770cf30daf5082f88f2575afd68c5 to 20bf46b414286047b944d34026a6cf9ff0cd40db

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

20bf46btrac #26432: py3 compatibility

comment:15 Changed 14 months ago by tscrim

  • Status changed from needs_review to positive_review

What was there was correct and works on python3, that is what six does. However, in this case, this makes the code a little easier to understand, although not by much. So I will keep the change.

comment:16 Changed 14 months ago by dcoudert

Thank you.

comment:17 Changed 14 months ago by vbraun

  • Branch changed from u/dcoudert/26432_clean_graph_py to 20bf46b414286047b944d34026a6cf9ff0cd40db
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:18 Changed 14 months ago by embray

  • Milestone changed from sage-8.4 to sage-8.5

This should be re-targeted for 8.5.

Note: See TracTickets for help on using tickets.