Opened 9 years ago

Closed 9 years ago

Last modified 8 years ago

#12791 closed enhancement (fixed)

Running time improvements of some (di)graphs products

Reported by: dcoudert Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords: graph, digraph, product
Cc: Merged in: sage-5.0.beta14
Authors: David Coudert Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

This patch improves the running time of: tensor_product, lexicographic_product, strong_product, disjunctive_product. It also adds missing tests in these functions.

The cartesian_product function is part of patch #12770 (solving a bug).

Apply :

Attachments (3)

trac_12791_products.patch (16.0 KB) - added by dcoudert 9 years ago.
trac_12791-review.patch (2.8 KB) - added by ncohen 9 years ago.
trac_12791-edge-iterator.patch (2.6 KB) - added by dcoudert 9 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 9 years ago by dcoudert

  • Description modified (diff)
  • Status changed from new to needs_review

Some running time examples.

Digraphs Before this patch

sage: G = digraphs.DeBruijn(2,4)
sage: H = digraphs.Kautz(3,3)
sage: %timeit G.tensor_product(H)
5 loops, best of 3: 848 ms per loop
sage: %timeit G.lexicographic_product(H)
5 loops, best of 3: 955 ms per loop
sage: %timeit G.strong_product(H)
5 loops, best of 3: 2.29 s per loop
sage: %timeit G.disjunctive_product(H)
5 loops, best of 3: 1.62 s per loop

Digraphs With this patch

sage: G = digraphs.DeBruijn(2,4)
sage: H = digraphs.Kautz(3,3)
sage: %timeit G.tensor_product(H)
25 loops, best of 3: 34.7 ms per loop
sage: %timeit G.lexicographic_product(H)
5 loops, best of 3: 327 ms per loop
sage: %timeit G.strong_product(H)
5 loops, best of 3: 55.8 ms per loop
sage: %timeit G.disjunctive_product(H)
5 loops, best of 3: 522 ms per loop

Graphs Before this patch

sage: G = graphs.GridGraph([5,5])
sage: H = graphs.PappusGraph()
sage: %timeit G.tensor_product(H)
5 loops, best of 3: 550 ms per loop
sage: %timeit G.lexicographic_product(H)
5 loops, best of 3: 605 ms per loop
sage: %timeit G.strong_product(H)
5 loops, best of 3: 1.44 s per loop
sage: %timeit G.disjunctive_product(H)
5 loops, best of 3: 1.07 s per loop

Graphs With this patch

sage: G = graphs.GridGraph([5,5])
sage: H = graphs.PappusGraph()
sage: %timeit G.tensor_product(H)
25 loops, best of 3: 15.2 ms per loop
sage: %timeit G.lexicographic_product(H)
5 loops, best of 3: 111 ms per loop
sage: %timeit G.strong_product(H)
25 loops, best of 3: 26.4 ms per loop
sage: %timeit G.disjunctive_product(H)
5 loops, best of 3: 237 ms per loop

comment:2 Changed 9 years ago by dcoudert

  • Authors set to David Coudert

comment:3 Changed 9 years ago by dcoudert

Minor change to allow loops in directed graphs.

comment:4 Changed 9 years ago by dcoudert

Addition of a more interesting test on the tensor product: DeBruijn?(d1, D) product DeBruijn?(d2, D) = DeBruijn?( d1*d2, D). It allows to test digraphs with loops.

Changed 9 years ago by dcoudert

comment:5 Changed 9 years ago by dcoudert

change of error message.

comment:6 Changed 9 years ago by ncohen

  • Dependencies set to 12770

comment:7 Changed 9 years ago by ncohen

My GOD ! This code really needed to be rewritten :-D

Ok, the patch is good to go, but I just add a few modifications so that the math in the documentation appear as maths in the HTML file.

Nathann

Changed 9 years ago by ncohen

comment:8 follow-up: Changed 9 years ago by dcoudert

Yes, the code was... to be fully rewritten. It was the same for patch #12770 in which the example I gave was impossible to run with original code.

With your review patch the doc is well displayed. So the patch is also good to go for me.

However, I don't understand the dependency with patch #12770 since I can install this patch independently of patch #12770.

I let you conclude on this patch.

comment:9 in reply to: ↑ 8 Changed 9 years ago by ncohen

  • Status changed from needs_review to positive_review

However, I don't understand the dependency with patch #12770 since I can install this patch independently of patch #12770.

Oh well, you mentionned it in the ticket and I thought it was better to apply this patch after the other one (can the other one be applied after this one, though ?)

Anyway it does not change much, as both of them are now... reviewed :-)

Nathann

comment:10 Changed 9 years ago by dcoudert

Yes, I'm able to install patch #12770 after this one. But it makes no difference, so you can let it as it is.

Thanks for the review. Now we have an elegant test with DeBruijn? digraphs products ;-)

comment:11 Changed 9 years ago by jdemeyer

  • Dependencies changed from 12770 to #12770
  • Reviewers set to Nathann Cohen

Changed 9 years ago by dcoudert

comment:12 Changed 9 years ago by dcoudert

  • Status changed from positive_review to needs_work

This additional patch uses edge_iterator instead of edges(). This is slightly faster.

comment:13 Changed 9 years ago by dcoudert

  • Dependencies #12770 deleted
  • Status changed from needs_work to needs_review

I'm removing the dependency on patch #12770 since the patchs are independents.

comment:14 Changed 9 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_review to positive_review

Well... As tests still pass :-)

Nathann

comment:15 Changed 9 years ago by dcoudert

Thanks Nathann ;-)

comment:16 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.0.beta14
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:17 Changed 8 years ago by ncohen

For some reason trac_12791-edge-iterator.patch has not been added to Sage with the other patches from this ticket. This is fixed in #13699.

Nathann

Note: See TracTickets for help on using tickets.