#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_review
Priority: minor | Milestone:
sage-5.6
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):
Oh, didn't know I can do that too. Here we go...
I have tested the code briefly and it looks good to me as far as
correction goes. I have two additional remarks though.
1. Can we avoid using graphx? Why exactly are we using it? I know its
because of performance but what exactly is making the algorithm tick that
faster? It doesn’t seem the right thing (to me) to call a graphx object
for this purpose but rather see where the problem in Sage is. Its weird
that its that faster even when you take the wrapping overhead into
account.
2. The code in is_triangle_free currently looks as follows
{{{
BB = {}
for u in self.vertex_iterator():
BB[u] = Bitset(capacity=N)
for v in self.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 self.vertex_iterator())
}}}
Am I missing something or this should be equivalent (to the slightly more
optimal):
{{{
BB = {}
for u in self.vertex_iterator():
BB[u] = Bitset(capacity=N)
for v in self.vertex_iterator():
if B[u]&B[v]:
BB[u].add(map[v])
if B[u] & BB[u] == 1:
return False
return True
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13503#comment:32>
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.
