#12791: Running time improvements of some (di)graphs products
-------------------------------------------+--------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.0
Component: graph theory | Resolution:
Keywords: graph, digraph, product | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
-------------------------------------------+--------------------------------
Changes (by dcoudert):
* status: new => needs_review
Old description:
> This patch improves the running time of: !`tensor_product`,
> !`lexicographic_product`, !`strong_product`, !`disjunctive_product`.
>
> The !`cartesian_product` function is part of patch #12770 (solving a
> bug).
New description:
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).
--
Comment:
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
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12791#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
