#13283: Tolerance Graphs (graph generators, etc.)
----------------------------------+----------------------------------
Reporter: eisermbi | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.12
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: Birk Eisermann | Reviewers: David Coudert
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #14980 | Stopgaps:
----------------------------------+----------------------------------
Changes (by eisermbi):
* status: needs_work => needs_review
Old description:
> 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
>
> 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
New description:
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:'''
- [attachment:trac_13283-1_intersection_graphs.patch]
- [attachment:trac_13283-1a_corrections.patch]
- [attachment:trac_13283-2_tolerance_graphs.patch]
--
Comment:
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
--
Ticket URL: <http://trac.sagemath.org/ticket/13283#comment:10>
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.
