#13283: Tolerance Graphs (graph generators, etc.)
----------------------------+-----------------------------------------------
Reporter: eisermbi | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.3
Component: graph theory | Keywords:
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies:
Stopgaps: |
----------------------------+-----------------------------------------------
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 (...-2_tolerance_graphs.patch):
- typo in documentation of `PermutationGraph`
- Adding method `ToleranceGraph` which generates the tolerance graph for a
given tolerance representation
- Adding methods to generate random (bounded) tolerance representations
Part 3 (...-3_whitespaces_nearby.patch):
- removing some trailing white spaces above the new method
`ToleranceGraph`
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13283>
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.
