#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):
Well, the difficulty with graph algorithms is that the efficiency depends
on the data structure, and we have as many possibilities as algorithms.
bit-by-bit operations are suitable for some kind of operations, but other
representations are also helpful. Sometimes it is faster to turn the graph
into a networkx graph (e.g. when adding/removing edges to test some
property), but sometimes the extra cost of changing the graph structure is
non negligible. I don't have magic solution but it's true that we could
gather some sets of operations into dedicated graph structures as for
instance the FastGraph class Nathann has used for pathwidth.
This version is a bit faster
{{{
def my_is_triangle_free_bitset(G):
N = G.num_verts()
map = {}
i = 0
B = {}
for u in G.vertex_iterator():
map[u] = i
i += 1
B[u] = Bitset(capacity=N)
# map adjacency to bitsets
for u,v in G.edge_iterator(labels=None):
B[u].add(map[v])
B[v].add(map[u])
# map lengths 2 paths to bitsets
BB = {}
for u in G.vertex_iterator():
BB[u] = Bitset(capacity=N)
for v in G.vertex_iterator():
if B[u]&B[v]:
BB[u].add(map[v])
# search for triangles
return not any(B[u]&BB[u] for u in G.vertex_iterator())
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13503#comment:23>
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.
