Opened 4 years ago

Closed 4 years ago

#22911 closed enhancement (fixed)

Reorganize some methods for loops

Reported by: dcoudert Owned by:
Priority: minor Milestone: sage-8.0
Component: graph theory Keywords:
Cc: Merged in:
Authors: David Coudert Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: fc65b8c (Commits, GitHub, GitLab) Commit: fc65b8ce08248f28497f35ae4d13f7f47513a6d5
Dependencies: Stopgaps:

Status badges

Description (last modified by dcoudert)

We have 2 methods for returning the loops of a (di)graph, loops and loop_edges, and one is faster than the other.

sage: G = Graph(10, loops=True)
sage: G.add_edges([(u,u) for u in G])
sage: %time L1 = G.loop_edges()
CPU times: user 68 µs, sys: 23 µs, total: 91 µs
Wall time: 73 µs
sage: %time L2 = G.loops()
CPU times: user 181 µs, sys: 50 µs, total: 231 µs
Wall time: 194 µs
sage: L1 == L2
True
sage: D = digraphs.DeBruijn(10,1)
sage: %time L1 = D.loop_edges()
CPU times: user 80 µs, sys: 18 µs, total: 98 µs
Wall time: 86.1 µs
sage: %time L2 = D.loops()
CPU times: user 333 µs, sys: 76 µs, total: 409 µs
Wall time: 344 µs
sage: L1 == L2
True

Note however that the slower (loops) has an extra parameter for edge labels. Let's try to clean that.

Change History (11)

comment:1 Changed 4 years ago by dcoudert

  • Branch set to u/dcoudert/22911
  • Commit set to fd7bf7ff53ea457128b02c24b893ec5448ea6c49
  • Description modified (diff)
  • Status changed from new to needs_review

So far I have let both methods and improved the loop_edges method.

I don't know what's the best option:

  1. deprecate one of the methods and ensure the fastest code is in the other one
  2. make the slowest method an alias for the fastest one and so let both names

Any advice / opinion is welcome. Option 2 is the easiest one, but...


New commits:

1521d8etrac #22911: reorder loop related methods
fd7bf7ftrac #22911: add parameter labels to loop_edges

comment:2 Changed 4 years ago by tscrim

I would not deprecate the method, but just make loops and alias for loop_edges (with the extra parameter).

Also, while you're moving methods around in the file (something I try to avoid doing because it can create trivial conflicts easily), I would clean up the docstrings Returns -> Return and

- ``labels`` -- whether returned edges have labels (``(u,v,l)``) or not (``(u,v)``)

comment:3 Changed 4 years ago by git

  • Commit changed from fd7bf7ff53ea457128b02c24b893ec5448ea6c49 to 85b7ef5915b0ac3d2dac5aba1d32155af6361b04

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

85b7ef5trac #22911: make loops an alias for loop_edges and fix doc strings

comment:4 Changed 4 years ago by dcoudert

Should be better now.

comment:5 Changed 4 years ago by tscrim

Last thing, we should move those doctests from loops into loop_edges as they cover a few other cases now not tested (at least from looking at the diff).

comment:6 Changed 4 years ago by git

  • Commit changed from 85b7ef5915b0ac3d2dac5aba1d32155af6361b04 to c22c50553ceed2fb3ac391648f78927279885980

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

c22c505trac #22911: merge doctests

comment:7 Changed 4 years ago by dcoudert

I have merged the doctests. Some cases are may be not covered, but I don't know which one.

comment:8 Changed 4 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

Hmm...maybe I misparsed the graphs in my mind. Thanks. Just remove the period in the INPUT: and you can set a positive review on my behalf.

comment:9 Changed 4 years ago by git

  • Commit changed from c22c50553ceed2fb3ac391648f78927279885980 to fc65b8ce08248f28497f35ae4d13f7f47513a6d5

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

fc65b8ctrac #22911: remove period in input

comment:10 Changed 4 years ago by dcoudert

  • Status changed from needs_review to positive_review

Thank you Travis.

comment:11 Changed 4 years ago by vbraun

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