#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_work
Priority: minor | Milestone:
sage-5.4
Component: graph theory | Resolution:
Keywords: triangles, graphs, number of triangles | Work issues:
Report Upstream: N/A | Reviewers:
David Coudert
Authors: Jernej Azarija | Merged in:
Dependencies: | Stopgaps:
----------------------------------------------------------+-----------------
Comment (by dcoudert):
If the graph is dense, the first visited vertex will have a triangle with
high probability. So after a very small number of iterations and so
operations, the algorithm returns False. But with matrix multiplications,
you have to pay the full cost whatever the result.
Of course, if the graph is dense and triangle free (not so many such
graphs), my algorithm will take long time, and possibly more than matrix
multiplications, but in average it is faster. Do your own experiments to
convince yourself.
So for testing if G is triangle free, it is good to have a parameter to
choose the algorithm, and a default behavior like: if G has less than 15
nodes, then do matrix multiplications, else use other algo.
For counting triangles, the situation is different and we clearly have to
take into account the density to choose the best algorithm.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13503#comment:13>
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.
