Sage: Ticket #8284: IntervalGraph generator and a bug in is_chordal
https://trac.sagemath.org/ticket/8284
<p>
Hello !!!
</p>
<p>
This very small patch creates an independent generator for <a class="missing wiki">IntervalGraph?</a>, which is then called by the old <a class="missing wiki">RandomIntervalGraph?</a> function... The function is_chordal is fixed, as it was not exploring the whole graph when it was not connected.
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/8284
Trac 1.1.6ncohenTue, 16 Feb 2010 18:12:29 GMTstatus changed
https://trac.sagemath.org/ticket/8284#comment:1
https://trac.sagemath.org/ticket/8284#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketncohenTue, 16 Feb 2010 18:15:18 GMTowner changed
https://trac.sagemath.org/ticket/8284#comment:2
https://trac.sagemath.org/ticket/8284#comment:2
<ul>
<li><strong>owner</strong>
changed from <em>rlm</em> to <em>ncohen</em>
</li>
</ul>
<p>
oh yes, and the lex_bfs method now admits an optional initial vertex ! :-)
</p>
TicketrlmTue, 02 Mar 2010 04:00:16 GMTstatus changed
https://trac.sagemath.org/ticket/8284#comment:3
https://trac.sagemath.org/ticket/8284#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Can you please provide a doctest which shows a simple example of creating an <code>IntervalGraph</code> from intervals?
</p>
TicketncohenTue, 02 Mar 2010 09:13:59 GMTstatus changed
https://trac.sagemath.org/ticket/8284#comment:4
https://trac.sagemath.org/ticket/8284#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Done ! :-)
</p>
TicketrlmSat, 06 Mar 2010 21:56:58 GMTstatus changed; reviewer, author set
https://trac.sagemath.org/ticket/8284#comment:5
https://trac.sagemath.org/ticket/8284#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>Robert Miller</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
Please add the following doctests:
</p>
<ol><li>An example of <code>is_chordal</code> for a non-connected graph.
</li></ol><ol start="2"><li>Examples of the usage of each option to <code>lex_BFS</code>.
</li></ol><p>
After this is done, I'll be happy with the patch. All tests pass.
</p>
TicketrlmSat, 06 Mar 2010 21:58:10 GMT
https://trac.sagemath.org/ticket/8284#comment:6
https://trac.sagemath.org/ticket/8284#comment:6
<p>
I forgot to mention, please also look over the attached patch. I believe this is a cleaner coding of the same thing.
</p>
TicketncohenSun, 07 Mar 2010 13:02:26 GMT
https://trac.sagemath.org/ticket/8284#comment:7
https://trac.sagemath.org/ticket/8284#comment:7
<p>
The <code></code>max<code></code> 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 ...
</p>
<p>
I'll bring the other modifications as soon as possible... Thank you for your help ! :-)
</p>
<p>
Nathann
</p>
TicketncohenMon, 08 Mar 2010 12:01:40 GMTstatus changed
https://trac.sagemath.org/ticket/8284#comment:8
https://trac.sagemath.org/ticket/8284#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Here it is ! :-)
</p>
TicketncohenThu, 20 May 2010 20:07:33 GMTpriority changed
https://trac.sagemath.org/ticket/8284#comment:9
https://trac.sagemath.org/ticket/8284#comment:9
<ul>
<li><strong>priority</strong>
changed from <em>major</em> to <em>critical</em>
</li>
</ul>
TicketncohenTue, 08 Jun 2010 12:19:08 GMT
https://trac.sagemath.org/ticket/8284#comment:10
https://trac.sagemath.org/ticket/8284#comment:10
<p>
Patch updated ! And based on the brand new 4.4.4.alpha0. Apply only this one !
</p>
<p>
Nathann
</p>
TicketncohenTue, 08 Jun 2010 12:19:58 GMTattachment set
https://trac.sagemath.org/ticket/8284
https://trac.sagemath.org/ticket/8284
<ul>
<li><strong>attachment</strong>
set to <em>trac_8284.patch</em>
</li>
</ul>
TicketrlmTue, 08 Jun 2010 17:31:42 GMTstatus changed
https://trac.sagemath.org/ticket/8284#comment:11
https://trac.sagemath.org/ticket/8284#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Looks good.
</p>
Ticketedward.scheinermanSun, 13 Jun 2010 22:53:07 GMT
https://trac.sagemath.org/ticket/8284#comment:12
https://trac.sagemath.org/ticket/8284#comment:12
<p>
This new graphs.<a class="missing wiki">IntervalGraph?</a> and the repaired graphs.<a class="missing wiki">RandomInterval?</a> work as advertised. Nicely done Nathann.
</p>
<p>
However, I think graphs.Interval should allow repeated intervals, e.g.,
g = graphs.<a class="missing wiki">IntervalGraph?</a>( [(0,2), (0,2), (1,5), (3,7)] )
should create a graph with four vertices (not three as the method currently does).
</p>
TicketncohenMon, 14 Jun 2010 06:42:33 GMT
https://trac.sagemath.org/ticket/8284#comment:13
https://trac.sagemath.org/ticket/8284#comment:13
<p>
you are right !!! I think the best way would be to create a <a class="missing wiki">RealInterval?</a> 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 (<a class="closed ticket" href="https://trac.sagemath.org/ticket/7563" title="enhancement: Interval Graphs : recognition (closed: fixed)">#7563</a>) : twin vertices were representing the same intervals, and the final graph was not isomorphic to the first as some vertices had disappeared..
</p>
<p>
I used a small trick to make it work, but this is definitely not a good answer :-)
</p>
<p>
Nathann
</p>
TicketjasonMon, 14 Jun 2010 15:30:07 GMT
https://trac.sagemath.org/ticket/8284#comment:14
https://trac.sagemath.org/ticket/8284#comment:14
<p>
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:
</p>
<pre class="wiki">sage: a=(1,2)
sage: b=(1,2)
sage: hash(a)
3713081631934410656
sage: hash(b)
3713081631934410656
</pre><p>
We can use a feature of user-defined classes, though:
</p>
<p>
"User-defined classes have <span class="underline">cmp</span>() and <span class="underline">hash</span>() methods by default; with them, all objects compare unequal (except with themselves) and x.<span class="underline">hash</span>() returns id(x)."
</p>
<p>
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:
</p>
<pre class="wiki">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
</pre><p>
Does that address the problem? It introduces a problem, in that now you can't do:
</p>
<p>
<code>g[Vertex((1,2))]</code>
</p>
<p>
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.<span class="underline">value to get the interval (or better, make some accessors for the attribute (and if you want, try to disallow changing it).
</span></p>
TicketncohenMon, 14 Jun 2010 15:37:40 GMT
https://trac.sagemath.org/ticket/8284#comment:15
https://trac.sagemath.org/ticket/8284#comment:15
<p>
Hmmmm.. Anyway creating a <a class="missing wiki">RealInterval?</a> class wouldn't be a solution as we would like <a class="missing wiki">RealInterval?</a>(1,2) == <a class="missing wiki">RealInterval?</a>(1,2) to be True, which can not hold if we want the vertices to be different in the Graph :-/
</p>
<p>
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...
</p>
<p>
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 <a class="missing wiki">IntervalGraph?</a>. 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 :-/
</p>
<p>
Any idea ? :-/
</p>
<p>
Nathann
</p>
TicketrlmTue, 29 Jun 2010 16:42:09 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/8284#comment:16
https://trac.sagemath.org/ticket/8284#comment:16
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.5.alpha1</em>
</li>
</ul>
Ticket