Opened 8 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 )
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()
toRandomIntervalGraph()
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)
Change History (21)
Changed 8 years ago by
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 follow-up: ↓ 4 Changed 8 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to needs_work
comment:3 Changed 8 years ago by
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
- 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 7 years ago by
- Dependencies set to #14980
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:6 Changed 7 years ago by
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
- Milestone changed from sage-5.11 to sage-5.12
comment:8 Changed 6 years ago by
(#14980 has been positively reviewed)
comment:9 Changed 6 years ago by
- Status changed from needs_review to needs_work
comment:10 Changed 6 years ago by
- 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
Hello,
can you rebase the patch on sage 5.12.beta5 so that I can review it?
Thanks.
Changed 6 years ago by
Changed 6 years ago by
Changed 6 years ago by
comment:12 Changed 6 years ago by
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
- 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
comment:14 in reply to: ↑ 13 Changed 6 years ago by
- Status changed from needs_review to positive_review
That is fine! Hence, set to positive review.
comment:15 Changed 6 years ago by
Good job!
comment:16 Changed 6 years ago by
- Merged in set to sage-5.13.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
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:
So for the IntervalGraph? function, I would prefer:
The same should be done in the ToleranceGraph? function.