#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 )
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)
Change History (20)
comment:1 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
Minor change to allow loops in directed graphs.
comment:4 Changed 9 years ago by
Changed 9 years ago by
comment:5 Changed 9 years ago by
change of error message.
comment:6 Changed 9 years ago by
- Dependencies set to 12770
comment:7 Changed 9 years ago by
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
comment:8 follow-up: ↓ 9 Changed 9 years ago by
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
- 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
comment:11 Changed 9 years ago by
- Dependencies changed from 12770 to #12770
- Reviewers set to Nathann Cohen
Changed 9 years ago by
comment:12 Changed 9 years ago by
- 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
- 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
- Description modified (diff)
- Status changed from needs_review to positive_review
Well... As tests still pass :-)
Nathann
comment:15 Changed 9 years ago by
Thanks Nathann ;-)
comment:16 Changed 9 years ago by
- 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
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
Some running time examples.
Digraphs Before this patch
Digraphs With this patch
Graphs Before this patch
Graphs With this patch