#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:
----------------------------------------------------------+-----------------
Changes (by dcoudert):
* cc: ncohen (added)
* reviewer: => David Coudert
Comment:
Hello,
I added Nathann in Cc because we had a discussion about counting triangles
last week ;)
The proposed method for testing if the graph is triangle free is not a
good one. Indeed, the time complexity for testing if the graph is triangle
free is at most N^w, where 2 <= w < 3 is the best possible exponent for
computing the square of a matrix of side N. You compute the square of the
adjacency matrix to get all paths of length 2, and then you test for every
edge (u,v) if there is a path of length 2 from u to v. Furthermore, the
basic algorithm of testing if some neighbors of a vertex are incident is
fast.
Let us compare the following method with your proposition for testing if
the graph is triangle free.
{{{
def my_is_triangle_free(G):
for u in G.vertex_iterator():
if any(G.has_edge(v,w) for v,w in
combinations_iterator(G.neighbors(u),2)):
return False
#
return True
}}}
We get the following running times:
{{{
sage: G = graphs.GridGraph([5,2]); M = G.adjacency_matrix() # 10 nodes
sage: %timeit G.is_triangle_free()
625 loops, best of 3: 603 µs per loop
sage: %timeit (M^3).trace() > 0
625 loops, best of 3: 101 µs per loop
sage: %timeit my_is_triangle_free(G)
625 loops, best of 3: 376 µs per loop
sage:
sage: G = graphs.GridGraph([10,5]); M = G.adjacency_matrix() # 50 nodes
sage: %timeit G.is_triangle_free()
25 loops, best of 3: 9.49 ms per loop
sage: %timeit (M^3).trace() > 0
125 loops, best of 3: 3.92 ms per loop
sage: %timeit my_is_triangle_free(G)
125 loops, best of 3: 2.67 ms per loop
sage:
sage: G = graphs.GridGraph([10,10]); M = G.adjacency_matrix() # 100 nodes
sage: %timeit G.is_triangle_free()
25 loops, best of 3: 31.5 ms per loop
sage: %timeit (M^3).trace() > 0
25 loops, best of 3: 12.3 ms per loop
sage: %timeit my_is_triangle_free(G)
125 loops, best of 3: 5.71 ms per loop
sage:
sage: G = graphs.GridGraph([50,20]); M = G.adjacency_matrix() # 1000 nodes
sage: %timeit G.is_triangle_free()
5 loops, best of 3: 1.1 s per loop
sage: %timeit (M^3).trace() > 0
5 loops, best of 3: 1.04 s per loop
sage: %timeit my_is_triangle_free(G)
5 loops, best of 3: 63.8 ms per loop
sage:
sage: G = graphs.RandomGNP(10,.1); M = G.adjacency_matrix() # 10 nodes
sage: %timeit G.is_triangle_free()
625 loops, best of 3: 492 µs per loop
sage: %timeit (M^3).trace() > 0
625 loops, best of 3: 90.5 µs per loop
sage: %timeit my_is_triangle_free(G)
625 loops, best of 3: 160 µs per loop
sage:
sage: G = graphs.RandomGNP(50,.1); M = G.adjacency_matrix() # 50 nodes
sage: %timeit G.is_triangle_free()
25 loops, best of 3: 9.92 ms per loop
sage: %timeit (M^3).trace() > 0
125 loops, best of 3: 3.93 ms per loop
sage: %timeit my_is_triangle_free(G)
625 loops, best of 3: 110 µs per loop
sage:
sage: G = graphs.RandomGNP(100,.2); M = G.adjacency_matrix() # 100 nodes,
dense
sage: %timeit G.is_triangle_free()
5 loops, best of 3: 40 ms per loop
sage: %timeit (M^3).trace() > 0
25 loops, best of 3: 12.9 ms per loop
sage: %timeit my_is_triangle_free(G)
625 loops, best of 3: 125 µs per loop
sage:
sage: G = graphs.RandomGNP(100,.01); M = G.adjacency_matrix() # 100
nodes, sparse
sage: %timeit G.is_triangle_free()
25 loops, best of 3: 29.7 ms per loop
sage: %timeit (M^3).trace() > 0
25 loops, best of 3: 12.2 ms per loop
sage: %timeit my_is_triangle_free(G)
125 loops, best of 3: 2.05 ms per loop
sage:
sage: G = graphs.RandomGNP(1000,.01); M = G.adjacency_matrix() # 1000
nodes
sage: %timeit G.is_triangle_free()
5 loops, best of 3: 33.9 s per loop
sage: %timeit (M^3).trace() > 0
5 loops, best of 3: 33.8 s per loop
sage: %timeit my_is_triangle_free(G)
625 loops, best of 3: 1.24 ms per loop
}}}
For very small graphs it is apparently faster to do {{{(M^3).trace() >
0}}}, but for large graphs, basic iterations are way faster because we
stop computations as soon as a triangle is found (if any). Therefore, a
better solution could be an hybrid method using matrix multiplication if
the graph is very small, and basic iterations otherwise.
----
For counting triangles, the situation is rather different and the density
of the graph matters. Furthermore, it is interesting to use networkx
graphs:
{{{
def my_triangles_count(G):
tr = 0
for u in G.vertex_iterator():
tr += sum(G.has_edge(v,w) for v,w in
combinations_iterator(G.neighbors(u),2))
return tr/3
def my_triangles_countnx(G):
tr = 0
ggnx = G.networkx_graph()
for u in ggnx.nodes_iter():
tr += sum(ggnx.has_edge(v,w) for v,w in
combinations_iterator(ggnx.neighbors(u),2))
return tr/3
}}}
We get the following running time:
{{{
sage: G = graphs.GridGraph([5,2])
sage: %timeit G.triangles_count()
625 loops, best of 3: 608 µs per loop
sage: %timeit my_triangles_count(G)
625 loops, best of 3: 444 µs per loop
sage: %timeit my_triangles_countnx(G)
625 loops, best of 3: 353 µs per loop
sage:
sage: G = graphs.GridGraph([10,5])
sage: %timeit G.triangles_count()
25 loops, best of 3: 9.44 ms per loop
sage: %timeit my_triangles_count(G)
125 loops, best of 3: 2.98 ms per loop
sage: %timeit my_triangles_countnx(G)
125 loops, best of 3: 1.99 ms per loop
sage:
sage: G = graphs.RandomGNP(10,.1)
sage: %timeit G.triangles_count()
625 loops, best of 3: 493 µs per loop
sage: %timeit my_triangles_count(G)
625 loops, best of 3: 217 µs per loop
sage: %timeit my_triangles_countnx(G)
625 loops, best of 3: 218 µs per loop
sage:
sage: G = graphs.RandomGNP(50,.1)
sage: %timeit G.triangles_count()
25 loops, best of 3: 9.79 ms per loop
sage: %timeit my_triangles_count(G)
125 loops, best of 3: 5.49 ms per loop
sage: %timeit my_triangles_countnx(G)
125 loops, best of 3: 2.78 ms per loop
sage:
sage: G = graphs.RandomGNP(50,.5)
sage: %timeit G.triangles_count()
25 loops, best of 3: 15 ms per loop
sage: %timeit my_triangles_count(G)
5 loops, best of 3: 82.4 ms per loop
sage: %timeit my_triangles_countnx(G)
25 loops, best of 3: 23.4 ms per loop
sage:
sage: G = graphs.RandomGNP(100,.5)
sage: %timeit G.triangles_count()
5 loops, best of 3: 58.4 ms per loop
sage: %timeit my_triangles_count(G)
5 loops, best of 3: 716 ms per loop
sage: %timeit my_triangles_countnx(G)
5 loops, best of 3: 181 ms per loop
sage:
sage: G = graphs.RandomGNP(100,.1)
sage: %timeit G.triangles_count()
25 loops, best of 3: 35.4 ms per loop
sage: %timeit my_triangles_count(G)
25 loops, best of 3: 33.6 ms per loop
sage: %timeit my_triangles_countnx(G)
25 loops, best of 3: 12.8 ms per loop
sage:
sage: G = graphs.RandomGNP(100,.05)
sage: %timeit G.triangles_count()
25 loops, best of 3: 32.3 ms per loop
sage: %timeit my_triangles_count(G)
25 loops, best of 3: 10.8 ms per loop
sage: %timeit my_triangles_countnx(G)
125 loops, best of 3: 5.53 ms per loop
}}}
As you can see, when the graph is dense, the matrix multiplication method
is the fastest, but for spare graphs it is better to use iterations and to
convert the graph into a networkx graph. However, I don't know how to
choose the threshold and I don't have better proposals in mind yet.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13503#comment:5>
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.
