Opened 7 years ago

Closed 6 years ago

#13283 closed enhancement (fixed)

Tolerance Graphs (graph generators, etc.)

Reported by: eisermbi Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.13
Component: graph theory Keywords:
Cc: Merged in: sage-5.13.beta1
Authors: Birk Eisermann Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14980 Stopgaps:

Description (last modified by dcoudert)

Intersection graphs are generated by a representations of geometric objects like intervals, parallelograms, etc. Unlike graphs listed under "Families of Graphs" in graph_generators.py, these graphs do not depend on just a few integer parameters. Hence, we create a new section "Intersection Graphs". Example classes of intersection graphs are interval graphs and permutation graphs (already implemented) as well as tolerance graphs or trapezoid graphs.

A tolerance graph is generated by a tolerance representation. And a tolerance representation can be described by a list ((l_0,r_0,t_0), (l_1,r_1,t_1), ..., (l_k,r_k,t_k)) where I_i = (l_i,r_i) denotes a closed interval on the real line and t_i a positive value, called tolerance. This representation generates the tolerance graph with the vertex set {0, 1, ..., k} and the edge set

{(i, j): |I_i \cap I_j| >= min{t_i, t_j} }

where |I_i \cap I_j| denotes the length of the intersection of I_i and I_j.


For easier review, our patch is divided into parts.

Part 1 (...-1_intersection_graphs.patch):

  • Creating section "Intersection Graphs"
  • Moving of functions IntervalGraph, PermutationGraph into this section

Part 2 (...-1a_corrections.patch)

Part 3 (...-2_tolerance_graphs.patch):

  • Adding method ToleranceGraph which generates the tolerance graph for a given tolerance representation
  • Adding methods to generate random (bounded) tolerance graphs

Apply:

Attachments (5)

trac_13283-3_whitespaces-nearby.patch (1.6 KB) - added by eisermbi 7 years ago.
trac_13283-1_intersection_graphs.patch (16.4 KB) - added by eisermbi 6 years ago.
trac_13283-1a_corrections.patch (8.4 KB) - added by eisermbi 6 years ago.
trac_13283-2_tolerance_graphs.patch (8.6 KB) - added by eisermbi 6 years ago.
trac_13283-rev.patch (9.3 KB) - added by dcoudert 6 years ago.

Download all attachments as: .zip

Change History (21)

Changed 7 years ago by eisermbi

comment:1 Changed 7 years ago by eisermbi

  • Status changed from new to needs_review

comment:2 follow-up: Changed 7 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to needs_work

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.

comment:3 Changed 7 years ago by dcoudert

With a fresh install of 5.2.rc0: install OK, long tests OK, docbuild OK. I think the functions are working correctly.

While implementing running time improvements proposed above, you could also implement a RandomIntervalGraph? function. That would be useful.

comment:4 in reply to: ↑ 2 Changed 6 years ago 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!

comment:5 Changed 6 years ago by eisermbi

  • Authors set to Birk Eisermann
  • Dependencies set to #14980
  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:6 Changed 6 years ago by dcoudert

I agree with proposed modifications, and the proposal to rename the RandomInterval? function RandomIntervalGraph?.

I cannot review the ticket now due to the dependency with #14980.

comment:7 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:8 Changed 6 years ago by ncohen

(#14980 has been positively reviewed)

comment:9 Changed 6 years ago by eisermbi

  • Status changed from needs_review to needs_work

comment:10 Changed 6 years ago by eisermbi

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Patch is updated (including the renaming of RandomInterval? to RandomIntervalGraph?).

Apply trac_13283-1_intersection_graphs.patch, trac_13283-1a_corrections.patch, trac_13283-2_tolerance_graphs.patch

comment:11 Changed 6 years ago by dcoudert

Hello,

can you rebase the patch on sage 5.12.beta5 so that I can review it?

Thanks.

Changed 6 years ago by eisermbi

Changed 6 years ago by eisermbi

Changed 6 years ago by eisermbi

comment:12 Changed 6 years ago by eisermbi

Sure. (Sorry for delay.) Now the files are rebased to 5.12.beta5. Thanks for reviewing!

comment:13 follow-up: Changed 6 years ago by dcoudert

  • Description modified (diff)

I have added a small review patch, mainly to correct one doctest and add a missing one.

For me the patch is good to go, so if you agree with the review patch, you can set the patch to positive review.

Best, David.

Apply trac_13283-1_intersection_graphs.patch, trac_13283-1a_corrections.patch, trac_13283-2_tolerance_graphs.patch, trac_13283-rev.patch

Changed 6 years ago by dcoudert

comment:14 in reply to: ↑ 13 Changed 6 years ago by eisermbi

  • Status changed from needs_review to positive_review

That is fine! Hence, set to positive review.

comment:15 Changed 6 years ago by dcoudert

Good job!

comment:16 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.13.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.