Opened 10 years ago
Closed 10 years ago
#8284 closed defect (fixed)
IntervalGraph generator and a bug in is_chordal
Reported by: | ncohen | Owned by: | ncohen |
---|---|---|---|
Priority: | critical | Milestone: | sage-4.5 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-4.5.alpha1 | |
Authors: | Nathann Cohen | Reviewers: | Robert Miller |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Hello !!!
This very small patch creates an independent generator for IntervalGraph?, which is then called by the old RandomIntervalGraph? function... The function is_chordal is fixed, as it was not exploring the whole graph when it was not connected.
Nathann
Attachments (1)
Change History (17)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- Owner changed from rlm to ncohen
comment:3 Changed 10 years ago by
- Status changed from needs_review to needs_work
Can you please provide a doctest which shows a simple example of creating an IntervalGraph
from intervals?
comment:5 Changed 10 years ago by
- Reviewers set to Robert Miller
- Status changed from needs_review to needs_work
Please add the following doctests:
- An example of
is_chordal
for a non-connected graph.
- Examples of the usage of each option to
lex_BFS
.
After this is done, I'll be happy with the patch. All tests pass.
comment:6 Changed 10 years ago by
I forgot to mention, please also look over the attached patch. I believe this is a cleaner coding of the same thing.
comment:7 Changed 10 years ago by
The max
instruction fails with this modification, as the --possibly last-- vertex in the list may have been removed before, thus max is trying to find the maximum of an empty list ...
I'll bring the other modifications as soon as possible... Thank you for your help ! :-)
Nathann
comment:9 Changed 10 years ago by
- Priority changed from major to critical
comment:10 Changed 10 years ago by
Patch updated ! And based on the brand new 4.4.4.alpha0. Apply only this one !
Nathann
Changed 10 years ago by
comment:12 Changed 10 years ago by
This new graphs.IntervalGraph? and the repaired graphs.RandomInterval? work as advertised. Nicely done Nathann.
However, I think graphs.Interval should allow repeated intervals, e.g., g = graphs.IntervalGraph?( [(0,2), (0,2), (1,5), (3,7)] ) should create a graph with four vertices (not three as the method currently does).
comment:13 Changed 10 years ago by
you are right !!! I think the best way would be to create a RealInterval? class in sage.sets, this way each vertex would be an immutable (hashable) object, and the graph could have two vertices representing the same interval.. I had the same problem when writing the recognition algorithm (#7563) : twin vertices were representing the same intervals, and the final graph was not isomorphic to the first as some vertices had disappeared..
I used a small trick to make it work, but this is definitely not a good answer :-)
Nathann
comment:14 Changed 10 years ago by
You might be able to get away with just creating a class that doesn't have a defined hash function, so that the default (the memory address) is used. The problem with using a tuple is that the two hash values below are the same:
sage: a=(1,2) sage: b=(1,2) sage: hash(a) 3713081631934410656 sage: hash(b) 3713081631934410656
We can use a feature of user-defined classes, though:
"User-defined classes have cmp() and hash() methods by default; with them, all objects compare unequal (except with themselves) and x.hash() returns id(x)."
This means we can get vertices which contain objects which normally would be considered equal in a dictionary to be stored as two different things in a dictionary:
sage: class Vertex(object): ....: def __init__(self, value): ....: self.__value=value ....: sage: a=Vertex((1,2)) sage: b=Vertex((1,2)) sage: a is b False sage: hash(a) 4528980944 sage: hash(b) 4528980816 sage: Graph({a: [b]}) Graph on 2 vertices
Does that address the problem? It introduces a problem, in that now you can't do:
g[Vertex((1,2))]
to get the neighbors, since, of course, the element you are creating is not the same as any of the vertices of the graph. Also, you have to use v.value to get the interval (or better, make some accessors for the attribute (and if you want, try to disallow changing it).
comment:15 Changed 10 years ago by
Hmmmm.. Anyway creating a RealInterval? class wouldn't be a solution as we would like RealInterval?(1,2) == RealInterval?(1,2) to be True, which can not hold if we want the vertices to be different in the Graph :-/
In the end, perhaps the best idea is the one Ed mentionned in one of his emails : just labels the vertices with (id,(a.b)), and forget about unnecessary abstraction, which wouldn't add anything in this case...
But then the user creating an interval graph by giving a list of pairs (a,b) would not be able to guess the name of its vertices, as they would depend on the id given by IntervalGraph?. Of course we can make it number them according to the order given by the list, but I don't like it very much either :-/
Any idea ? :-/
Nathann
comment:16 Changed 10 years ago by
- Merged in set to sage-4.5.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
oh yes, and the lex_bfs method now admits an optional initial vertex ! :-)