#13283: Tolerance Graphs (graph generators, etc.)
--------------------------------+-------------------------------------------
Reporter: eisermbi | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.3
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers: David Coudert
Authors: | Merged in:
Dependencies: | Stopgaps:
--------------------------------+-------------------------------------------
Changes (by dcoudert):
* status: needs_review => needs_work
* reviewer: => David Coudert
Comment:
Hello,
so far I'm unable to install the patch since my installation of 5.2.rc0 is
not finished.
However, I have small remarks:
- use xrange instead of range
- it is usually faster to add edges directly (see example bellow)
- is the instruction graph.Graph(n) correct?
{{{
sage: def toto(n):
....: G = Graph()
....: for i in xrange(n):
....: for j in xrange(i+1,n):
....: G.add_edge(i,j)
....: return G
....:
sage: def titi(n):
....: G = Graph()
....: E = []
....: for i in xrange(n):
....: for j in xrange(i+1,n):
....: E.append((i,j))
....: G.add_edges(E)
....: return G
....:
sage: %timeit toto(10)
625 loops, best of 3: 406 µs per loop
sage: %timeit titi(10)
625 loops, best of 3: 674 µs per loop
sage: %timeit toto(20)
625 loops, best of 3: 1.45 ms per loop
sage: %timeit titi(20)
125 loops, best of 3: 2.58 ms per loop
}}}
So for the ''IntervalGraph'' function, I would prefer:
{{{
n = len(intervals)
g = Graph(n)
for i in xrange(n-1):
minI, maxI = sorted(intervals[i])
for j in xrange(i+1,n):
minJ, maxJ = sorted(intervals[j])
if maxI < minJ or maxJ < minI: continue
g.add_edge(i,j)
rep = dict( zip(range(n),intervals) )
g.set_vertices(rep)
return g
}}}
The same should be done in the ToleranceGraph function.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13283#comment:2>
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.
