#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: new
Priority: minor | Milestone: sage-5.4
Component: graph theory | Keywords: triangles, graphs, number of
triangles
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies:
Stopgaps: |
----------------------------+-----------------------------------------------
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13503>
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.
