Opened 13 years ago

Closed 6 months ago

#6604 closed enhancement (fixed)

Polish the use of iterators in C graphs

Reported by: rlm Owned by: rlm
Priority: major Milestone: sage-9.5
Component: graph theory Keywords:
Cc: gh-kliem, tscrim Merged in:
Authors: David Coudert Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: c7dc1b1 (Commits, GitHub, GitLab) Commit: c7dc1b1f01ad53ef1e7e1e1be3e926ae714d18f5
Dependencies: Stopgaps:

Status badges

Change History (15)

comment:1 Changed 13 years ago by rlm

  • Description modified (diff)

comment:2 Changed 13 years ago by ncohen

  • Cc ncohen added
  • Report Upstream set to N/A

comment:3 Changed 12 years ago by rlm

I am right now watching a talk on closures in Cython, which are all but finished. Then, yield statements in Cython will soon follow! So don't work on this ticket for now...

comment:4 Changed 12 years ago by jason

  • Type changed from defect to enhancement

comment:5 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:9 Changed 6 months ago by dcoudert

  • Authors set to David Coudert
  • Branch set to public/graphs/6604_iterators
  • Cc gh-kliem tscrim added; ncohen removed
  • Commit set to 07d52d955bd71c87bcb175814b155c5d0c57b3a6
  • Milestone changed from sage-6.4 to sage-9.5
  • Status changed from new to needs_review

It seems there is little remaining to do for iterators in backends now, so let's do it.

Before

sage: a = DiGraph(graphs.CompleteGraph(100))
sage: b = a._backend
sage: %timeit L = list(b.iterator_nbrs(30))
28.3 µs ± 1.44 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

After

sage: a = DiGraph(graphs.CompleteGraph(100))
sage: b = a._backend
sage: %timeit L = list(b.iterator_nbrs(30))
18.6 µs ± 698 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

New commits:

07d52d9trac #6604: polish some iterators in backends

comment:10 Changed 6 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

That is quite a decent speedup and will likely have effects in other methods. Looks like some trivial failures due to slight differences in how the iteration is done:

sage -t --long --random-seed=210304412354021215508062896360889570175 src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 10654, in sage.graphs.generic_graph.GenericGraph.neighbor_iterator
Failed example:
    list(D.neighbor_iterator(0))
Expected:
    [1, 2, 3]
Got:
    [3, 1, 2]
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 17591, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    list(D.depth_first_search(1, ignore_direction=True, edges=True))
Expected:
    [(1, 4), (4, 5), (5, 6), (5, 2), (4, 3)]
Got:
    [(1, 3), (3, 4), (4, 5), (5, 6), (5, 2)]

This one I am not sure if it is because of the random seed or this ticket:

sage -t --long --random-seed=210304412354021215508062896360889570175 src/sage/schemes/toric/sheaf/klyachko.py
**********************************************************************
File "src/sage/schemes/toric/sheaf/klyachko.py", line 950, in sage.schemes.toric.sheaf.klyachko.KlyachkoBundle_class.random_deformation
Failed example:
    Vtilde.cohomology(dim=True, weight=(0,))
Expected:
    (1, 0)
Got:
    (0, 0)

in either case, it should be a trivial fix.

comment:11 Changed 6 months ago by git

  • Commit changed from 07d52d955bd71c87bcb175814b155c5d0c57b3a6 to c7dc1b1f01ad53ef1e7e1e1be3e926ae714d18f5

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

c7dc1b1trac #6604: fix doctests in genenric_graph.py

comment:12 Changed 6 months ago by dcoudert

I fixed the doctests in generic_graph.py.

I cannot reproduce the error in klyachko.py. It occurs in method random_deformation. Some help might be helpful here.

comment:13 Changed 6 months ago by dcoudert

Actually, this random error in klyachko.py has already been reported in #32773.

comment:14 Changed 6 months ago by tscrim

  • Status changed from needs_review to positive_review

Thank you. LGTM.

comment:15 Changed 6 months ago by vbraun

  • Branch changed from public/graphs/6604_iterators to c7dc1b1f01ad53ef1e7e1e1be3e926ae714d18f5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.