#13283: Tolerance Graphs (graph generators, etc.)
--------------------------------+-----------------------------------
Reporter: eisermbi | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.11
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers: David Coudert
Report Upstream: N/A | Work issues:
Branch: | Dependencies:
Stopgaps: |
--------------------------------+-----------------------------------
Comment (by eisermbi):
> - use xrange instead of range
Done.
> - it is usually faster to add edges directly (see example bellow)
Done.
> - is the instruction graph.Graph(n) correct?
I think it is. But because of the inclusion {{{from sage.graphs.graph
import Graph}}}
at the beginning of the file it is easier to write {{{Graph(n)}}}.
>
> So for the ''IntervalGraph'' function, I would prefer: [...]
Originally, {{{max(I)}}} and {{{min(J)}}} were calculated, but
{{{max(J)}}} and {{{min(I)}}} only in some case. Your solution will
calculate all four values (maybe faster) but probably create a new tuple.
The following test shows that regarding the endpoint ordering the original
version
is slightly faster. So I left this as it was...
{{{
def newconstr(intervals):
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)
return g
def oldconstr(intervals):
n = len(intervals)
g = Graph(n)
for i in xrange(n-1):
I = intervals[i]
for j in xrange(i+1,n):
J = intervals[j]
if max(I) < min(J) or max(J) < min(I): continue
g.add_edge(i,j)
return g
II = [ (1,2), (3,4), (5,6), (7,8), (9,10), (11,12) ]
IJ = [ (1,12), (3,12), (5,12), (7,12), (9,12), (11,12) ]
I1 = [tuple(sorted((random(), random()))) for i in range(14)]
I2 = [tuple(sorted((random(), random()))) for i in range(18)]
I3 = [tuple(sorted((random(), random()))) for i in range(22)]
timeit('oldconstr(II)')
timeit('newconstr(II)')
timeit('oldconstr(IJ)')
timeit('newconstr(IJ)')
timeit('oldconstr(I1)')
timeit('newconstr(I1)')
timeit('oldconstr(I2)')
timeit('newconstr(I2)')
timeit('oldconstr(I3)')
timeit('newconstr(I3)')
}}}
{{{
625 loops, best of 3: 46 µs per loop
625 loops, best of 3: 55.4 µs per loop
625 loops, best of 3: 119 µs per loop
625 loops, best of 3: 123 µs per loop
625 loops, best of 3: 306 µs per loop
625 loops, best of 3: 327 µs per loop
625 loops, best of 3: 716 µs per loop
625 loops, best of 3: 747 µs per loop
625 loops, best of 3: 897 µs per loop
625 loops, best of 3: 934 µs per loop
}}}
Furthermore, I have added a parameter that can switch off the sorting of
the
interval endpoints. This speeds up the creation of an interval graph by
25% in average.
>
> The same should be done in the ToleranceGraph function.
Done.
> While implementing running time improvements proposed above, you could
also implement a RandomIntervalGraph? function. That would be useful.
This functionality already exists. It is not really obvious that the
function "RandomInterval" produces a graph and not an interval. Hence,
should I rename "RandomInterval" to "RandomIntervalGraph" and desprecate
"RandomInterval"? One might object that the name becomes too long but at
least two persons find it better to read... ;-)
Thanks!
--
Ticket URL: <http://trac.sagemath.org/ticket/13283#comment:4>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
