Opened 4 years ago

Closed 4 years ago

#19662 closed enhancement (fixed)

Less wasteful management of edge labels

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.10
Component: graph theory Keywords:
Cc: dcoudert, borassi Merged in:
Authors: Nathann Cohen Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: 1b97eb1 (Commits) Commit: 1b97eb1147e804d6d506d0ef94e0de09c6cd58e9
Dependencies: Stopgaps:

Description (last modified by ncohen)

I hate loops, I hate multiple edges, I hate edge labels.

A colleague of mine recently reported very slow performances with our graphs, and he was using edge labels. There were.... Let's say "obvious loss of performances" to stay calm.

If you are sensitive to bad algorithms, be warned -- what you will see while reviewing this branch may shock you.

As an illustration. Before

sage: %time Graph([(u,v,1) for u,v in combinations(range(200),2)])
CPU times: user 1.82 s, sys: 0 ns, total: 1.82 s
Wall time: 1.83 s
Graph on 200 vertices

After

sage: %time Graph([(u,v,1) for u,v in combinations(range(200),2)])
CPU times: user 88 ms, sys: 12 ms, total: 100 ms
Wall time: 86.6 ms
Graph on 200 vertices

Nathann

Change History (5)

comment:1 Changed 4 years ago by ncohen

  • Branch set to u/ncohen/19662
  • Commit set to dc8f4b5f001d340c8f2fc8c0d354bceafae0a469
  • Status changed from new to needs_review

New commits:

dc8f4b5trac #19662: Less wasteful management of edge labels

comment:2 Changed 4 years ago by git

  • Commit changed from dc8f4b5f001d340c8f2fc8c0d354bceafae0a469 to 1b97eb1147e804d6d506d0ef94e0de09c6cd58e9

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1b97eb1trac #19662: Less wasteful management of edge labels

comment:3 Changed 4 years ago by novoselt

  • Reviewers set to Andrey Novoseltsev
  • Status changed from needs_review to positive_review

Would be nice to have here an example of shocking increase in performance, but after my experience with graph equality I feel you.

comment:4 Changed 4 years ago by ncohen

  • Description modified (diff)

Thank you for the review. I added a small example, and you can increase the number to get a speedup factor as large as you wish.

Nathann

comment:5 Changed 4 years ago by vbraun

  • Branch changed from u/ncohen/19662 to 1b97eb1147e804d6d506d0ef94e0de09c6cd58e9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.