#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 dcoudert):
Replying to [comment:27 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.
yes, it is better to remove the abs in a patch dedicated to small details
;-)
> > 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?
It's difficult in python. The method is fast because it uses optimized
data structure. It can be done in cython, but then it is certainly better
to only implement the interfaces with the original c code of Latapy. We
can easily obtained agreement from him for integrating is code in sage.
This should be done in a dedicated patch to ease reviewing process.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13503#comment:28>
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.
