Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#26567 closed enhancement (fixed)

clean dense_graph.pyx

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

Status badges

Description (last modified by dcoudert)

The big change in this ticket is to use yield in iterators instead of first building a list and then returning an iterator over that list. This should speed up methods using these iterators.

On the way, I have put try.. except TypeError around the 2 sorted operations.

We also do PEP8 cleaning.

Change History (9)

comment:1 Changed 4 years ago by dcoudert

  • Branch set to public/26567_dense_graph
  • Cc tscrim chapoton added
  • Commit set to 56cd44fce3f7739f17fa4b06f968a2ef4800582e
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

56cd44ftrac #26567: clean dense_graph.pyx and use yield in iterators

comment:2 Changed 4 years ago by tscrim

On the error messages, please remove the !.

I think a better way to do

                            v, u = sorted((self.vertex_label(v_int),
                        except TypeError:
                            v = self.vertex_label(v_int)
                            u = self.vertex_label(u_int)

is to do

                        v = self.vertex_label(v_int)
                        u = self.vertex_label(u_int)
                            if u < v:
                                v, u = u, v
                        except TypeError:

as it does not create an intermediary objects (the tuple and the resulting list), I would guess one comparison is faster than calling sorted, and we only change things if we need to.

comment:3 Changed 4 years ago by git

  • Commit changed from 56cd44fce3f7739f17fa4b06f968a2ef4800582e to 32e15a0dfae38e2adb3c9b438d71671b83e49683

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

cbc0528trac #26567: Merged with 8.5.beta1
aadaf14trac #26567: implement reviewers comments
32e15a0trac #26567: correct error

comment:4 Changed 4 years ago by git

  • Commit changed from 32e15a0dfae38e2adb3c9b438d71671b83e49683 to 043388831f22a50333fd140823dedaf29de222cc

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

0433888trac #26567: improvements

comment:5 Changed 4 years ago by dcoudert

All comment's implemented.

comment:6 Changed 4 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

Thanks. I just want to wait for a green patchbot. Once one comes back (morally) green, we can set a positive review.

comment:7 Changed 4 years ago by tscrim

  • Status changed from needs_review to positive_review

The doctest failures seem unrelated.

comment:8 Changed 4 years ago by vbraun

  • Branch changed from public/26567_dense_graph to 043388831f22a50333fd140823dedaf29de222cc
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:9 Changed 4 years ago by jhpalmieri

  • Commit 043388831f22a50333fd140823dedaf29de222cc deleted

Are there any plans for similar changes to sparse_graph.pyx, in particular to iterator_edges? I tried doing something similar, but it led to other problems, so it would be better if someone who knows the graph theory stuff better to do it. The code in sparse_graph.pyx leads to Python 3 doctest failures with simplicial complexes.

Note: See TracTickets for help on using tickets.