Opened 8 years ago

Closed 6 years ago

# Tolerance Graphs (graph generators, etc.)

Reported by: Owned by: eisermbi jason, ncohen, rlm major sage-5.13 graph theory sage-5.13.beta1 Birk Eisermann David Coudert N/A #14980

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)

• Typo in documentation of function PermutationGraph?
• Speed improvement of function IntervalGraph?
• Renaming `RandomInterval()` to `RandomIntervalGraph()`

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:

### comment:1 Changed 8 years ago by eisermbi

• Status changed from new to needs_review

### comment:2 follow-up: ↓ 4 Changed 8 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):
....:     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))
....:     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

rep = dict( zip(range(n),intervals) )
g.set_vertices(rep)

return g
```

The same should be done in the ToleranceGraph? function.

### comment:3 Changed 8 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 7 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
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
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 7 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 7 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.

### 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: ↓ 14 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

### 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.

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.