#13503: Enhancement of `is_triangle_free' addition of `triangles_count' and a
minor
change in `spanning_trees_count'
----------------------------------------------------------+-----------------
Reporter: azi | Owner:
jason, ncohen, rlm
Type: enhancement | Status:
needs_review
Priority: minor | Milestone:
sage-5.4
Component: graph theory | Resolution:
Keywords: triangles, graphs, number of triangles | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Jernej Azarija, David Coudert | Merged in:
Dependencies: | Stopgaps:
----------------------------------------------------------+-----------------
Changes (by {'newvalue': u'Jernej Azarija, David Coudert', 'oldvalue': u'Jernej
Azarija'}):
* status: needs_work => needs_review
* reviewer: David Coudert =>
* author: Jernej Azarija => Jernej Azarija, David Coudert
Old description:
> The main change of this patch is to improve the `is_triangle_free'
> method. The introduced algorithm uses the fact that given that A is the
> adjacency matrix of a simple graph G, then the number of triangles in G
> is tr(A^3)/6.
>
> The change has been tested resulting in the following benchmarks:
>
> 1. Testing all graphs of order up to 10 for triangles: (old: 201m44.339s,
> new: '''87m38.146s''')
> 2. Testing all triangle-free graphs of order 12 for triangles: (old:
> 15m56.679s, new '''9m41.116s''')
> 3. Testing all graphs of order up to 10 that do contain triangles: (old:
> 0m10.305s, new : '''0m5.798s''')
>
> I can provide the test programs if needed.
>
> Since there are many applications in which one needs to count the number
> of triangles in a graph the named routine was also added.
>
> Finally a minor change has been made to the generic_graph function
> spanning_trees_count() which calls abs on a determinant that is always
> positive.
New description:
The main change of this patch is to improve the `is_triangle_free' method.
The introduced algorithm uses the fact that given that A is the adjacency
matrix of a simple graph G, then the number of triangles in G is
tr(A^3)/6.
The change has been tested resulting in the following benchmarks:
1. Testing all graphs of order up to 10 for triangles: (old: 201m44.339s,
new: '''87m38.146s''')
2. Testing all triangle-free graphs of order 12 for triangles: (old:
15m56.679s, new '''9m41.116s''')
3. Testing all graphs of order up to 10 that do contain triangles: (old:
0m10.305s, new : '''0m5.798s''')
I can provide the test programs if needed.
Since there are many applications in which one needs to count the number
of triangles in a graph the named routine was also added.
Finally a minor change has been made to the generic_graph function
spanning_trees_count() which calls abs on a determinant that is always
positive.
Apply:
* [attachment:trac_13503_triangles-v2.patch]
--
Comment:
I have included discussed improvements into the {{{is_triangle_free}}} and
the {{{triangles_count}}} methods, and added optional argument for
algorithm selection.
One could also add probabilistic test for triangle detection.
Could you benchmark the new functions to update the ticket description?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13503#comment:24>
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.
