#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:
Authors: Jernej Azarija, David Coudert | Merged in:
Dependencies: | Stopgaps:
----------------------------------------------------------+-----------------
Comment (by azi):
Replying to [comment:26 dcoudert]:
>
> > * Where did you find that this "abs" was not needed ? I thought it
was `O_o`
>
> It was in the original patch from Jernej Azarija
([trac_17334_triangle_free_speedup.patch]). I don't know if its true or
not, and since the gain is very limited, we could put it back to be on the
safe side.
abs is not needed. Perhaps we can still remove it from this patch and I
add it later in a generic patch fixing various small details in graph.py.
The reason it is not needed is that Kirchhoff matrix tree theorem states
that the number of spanning trees equals
det(L')*(-1)^(i+j}+)
where L' is the matrix that is obtained from the Laplacian after removing
row i and column j.
>
> > * I'm not a big fan of having triangle_count in generic_graph, as
I don't really see it used with DiGraphs... And the code reflects that
indeed, but if you think they can, then why not ? Could you at least say
that not all algorithms are available for Digraphs, and that the method
looks for "directed C3" in this case, or something similar ? And in
particular not C3 in the underlying graph.
>
> Jernej should answer that remark.
I am not really sure what to do here.
>
>
> > * "tests if the trace of the adjacency matrix is positive" would
be counting the number of loops `:-D` Btw I guess it would be better to
have "``return (A * * 3 ).trace() == 0``" instead of "``return
(A*A*A).trace() == 0``", just in case they might implement some smart
thing for powers of binary matrices eventually... The logarithmic power
method changes nothing for `k=3` `:-)`
>
> OK.
>
> I have implemented some of the modifications.
>
> > Thanks for that patch !!
>
> I was also thinking of some nice and fast methods from Alon et al., or
from Latapy (see the code in c and the survey at [http://www-
rp.lip6.fr/~latapy/Triangles/]). We could add them (in particular the
compact-forward method) at the cost of adding an interface and a method
for converting the graph into the tricky data structure used by Latapy.
Haven't looked at the site yet, but is it hard to implement the algorithm
directly into sage?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13503#comment:27>
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.
