Changes between Initial Version and Version 11 of Ticket #30665


Ignore:
Timestamp:
Sep 26, 2020, 2:57:13 PM (2 years ago)
Author:
gh-kliem
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #30665

    • Property Commit changed from to 1a85353a799f43804ade03a18afc9603c773abea
    • Property Branch changed from to u/gh-kliem/graphs_improve_edge_iterator

  • Ticket #30665 – Description

    initial v11  
    44
    55In case of multiple edges, it might be desirable to create lists of all arcs from `u` to `v`. Otherwise we might risk segmentation faults, if messing with the graph while iterating through it.
     6
     7We expose an unsorted edge iterator.
     8
     9Before:
     10
     11{{{
     12sage: G = Graph(loops=False, multiedges=False)
     13....: G.add_edges([(i, (i+85)%100) for i in range(100)])
     14....: G.add_edges([(i, (i+37)%100) for i in range(100)])
     15....: G.add_edges([(i, (i+83)%100) for i in range(100)])                                                                                                                                                                                                                                                                                             
     16sage: %timeit edges = list(G.edge_iterator())                                                                                                                                                                                                                                                                                                                             
     17103 µs ± 10.4 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
     18sage: H = G.copy()
     19sage: %timeit H == G                                                                                                                                                                                                                                                                                                                                                       
     20268 µs ± 2.43 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     21
     22sage: G = Graph(loops=False, multiedges=False, sparse=False)
     23....: G.add_edges([(i, (i+85)%100) for i in range(100)])
     24....: G.add_edges([(i, (i+37)%100) for i in range(100)])
     25....: G.add_edges([(i, (i+83)%100) for i in range(100)])                                                                                                                                                                                                                                                                                                           
     26sage: %timeit edges = list(G.edge_iterator())                                                                                                                                                                                                                                                                                                                             
     27228 µs ± 40.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     28sage: H = G.copy()
     29sage: %timeit H == G                                                                                                                                                                                                                                                                                                                                                       
     30380 µs ± 2.07 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     31
     32
     33sage: G = Graph(loops=False, multiedges=True)
     34....: G.add_edges([(i, (i+85)%100, j) for j in range(20) for i in range(100)])
     35....: G.add_edges([(i, (i+37)%100, j) for j in range(20) for i in range(100)])
     36....: G.add_edges([(i, (i+83)%100, j) for j in range(20) for i in range(100)])                                                                                                                                                                                                                                                                                             
     37sage: %timeit edges = list(G.edge_iterator())                                                                                                                                                                                                                                                                                                                             
     382.22 ms ± 412 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
     39sage: H = G.copy()
     40sage: %timeit H == G                                                                                                                                                                                                                                                                                                                                                       
     412.94 ms ± 51.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
     42}}}
     43
     44After:
     45
     46{{{
     47sage: G = Graph(loops=False, multiedges=False)
     48....: G.add_edges([(i, (i+85)%100) for i in range(100)])
     49....: G.add_edges([(i, (i+37)%100) for i in range(100)])
     50....: G.add_edges([(i, (i+83)%100) for i in range(100)])                                                                                                                                                                                                                                                                                                                   
     51sage: %timeit edges = list(G.edge_iterator())                                                                                                                                                                                                                                                                                                                             
     5266.2 µs ± 693 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
     53sage: %timeit edges = list(G.edge_iterator(unsorted=True))                                                                                                                                                                                                                                                                                                                 
     5450.1 µs ± 404 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
     55sage: H = G.copy()                                                   
     56sage: %timeit H == G                                                                                                                                                                                                                                                                                                                                                       
     57244 µs ± 13.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     58
     59
     60sage: G = Graph(loops=False, multiedges=False, sparse=False)
     61....: G.add_edges([(i, (i+85)%100) for i in range(100)])
     62....: G.add_edges([(i, (i+37)%100) for i in range(100)])
     63....: G.add_edges([(i, (i+83)%100) for i in range(100)])                                                                                                                                                                                                                                                                                                                   
     64sage: %timeit edges = list(G.edge_iterator())                                                                                                                                                                                                                                                                                                                             
     65125 µs ± 597 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
     66sage: %timeit edges = list(G.edge_iterator(unsorted=True))                                                                                                                                                                                                                                                                                                                 
     67112 µs ± 1.22 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
     68sage: H = G.copy() 
     69sage: %timeit H == G                                                                                                                                                                                                                                                                                                                                                       
     70318 µs ± 44.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     71
     72sage: G = Graph(loops=False, multiedges=True)
     73....: G.add_edges([(i, (i+85)%100, j) for j in range(20) for i in range(100)])
     74....: G.add_edges([(i, (i+37)%100, j) for j in range(20) for i in range(100)])
     75....: G.add_edges([(i, (i+83)%100, j) for j in range(20) for i in range(100)])                                                                                                                                                                                                                                                                                             
     76sage: %timeit edges = list(G.edge_iterator())                                                                                                                                                                                                                                                                                                                             
     771.05 ms ± 3.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     78sage: %timeit edges = list(G.edge_iterator(unsorted=True))                                                                                                                                                                                                                                                                                                                 
     791.02 ms ± 40.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     80sage: H = G.copy() 
     81sage: %timeit H == G                                                                                                                                                                                                                                                                                                                                                       
     822.81 ms ± 725 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
     83}}}