#9727: RepresentationGraph method that generalizes IntervalGraph
----------------------------------+-----------------------------------------
Reporter: edward.scheinerman | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_info
Priority: major | Milestone:
Component: graph theory | Keywords:
Author: Ed Scheinerman | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------------+-----------------------------------------
Comment(by edward.scheinerman):
Interesting, but the Graph constructor works differently and does not
provide all the functionality that GraphRepresentation does. For example,
it will not solve the problem of repeated intervals being recognized as
separate vertices (but with the same closed neighborhoods). It will also
not accept a dictionary instead of a list as we have set up in
RepresentationGraph.
One solution might be to rework the Graph() constructor to accept a
[dictionary,function] pair. In that case, the vertices would be the keys
of the dictionary. Two vertices would be adjacent if the function, applied
to the values associated with two keys, returns True. How difficult would
that be? If easy, then that may be a preferable route. If difficult, then
I prefer this route.
It is true that if one sorts the intervals before iterating over pairs,
some speed up can be realized (especially for a sparse interval graph);
but this efficiency comes at a cost of some generality. Also, for a random
interval graph, the speedup will not be so dramatic as these random graphs
are dense.
Ed
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9727#comment:6>
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.
