clean graph.py

[dcoudert]

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

CC: @tscrim @fchapoton

Component: graph theory

Author: David Coudert

Branch/Commit: 20bf46b

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/26432

[dcoudert]

Commit: 9067797

[dcoudert]

New commits:

9067797

trac #26432: first round of improvements

[dcoudert]

Branch: u/dcoudert/26432_clean_graph_py

[sagetrac-git]

Changed commit from 9067797 to 672b173

[sagetrac-git]

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

672b173

trac #26432: more improvements

[dcoudert]

comment:3

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.

[jhpalmieri]

comment:4

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

[tscrim]

comment:5

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.

[sagetrac-git]

Changed commit from 672b173 to 8681351

[sagetrac-git]

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

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

[dcoudert]

comment:7

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 ?

[tscrim]

comment:8

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.

[sagetrac-git]

Changed commit from 8681351 to 9a648e7

[sagetrac-git]

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

5b0c7b4	trac #26432: remove sorting in vertex_cover and cliques_maximal
d27d578	trac #26432: more care in input blocks
9a648e7	trac #26432: further corrections

[sagetrac-git]

Changed commit from 9a648e7 to 9e5ebb3

[sagetrac-git]

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

9e5ebb3

trac #26432: spaces in lambda declarations

[dcoudert]

comment:11

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.

[tscrim]

comment:12

Thanks. LGTM.

[tscrim]

Reviewer: Travis Scrimshaw

[dcoudert]

comment:13

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.

[sagetrac-git]

Changed commit from 9e5ebb3 to 20bf46b

[sagetrac-git]

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

20bf46b

trac #26432: py3 compatibility

[tscrim]

comment:15

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.

[dcoudert]

comment:16

Thank you.

[vbraun]

Changed branch from u/dcoudert/26432_clean_graph_py to 20bf46b

[embray]

comment:18

This should be re-targeted for 8.5.