Opened 12 years ago

Closed 12 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:

Status badges


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.


Attachments (1)

trac_8284.patch (5.3 KB) - added by ncohen 12 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 12 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 12 years ago by ncohen

  • Owner changed from rlm to ncohen

oh yes, and the lex_bfs method now admits an optional initial vertex ! :-)

comment:3 Changed 12 years ago by rlm

  • 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:4 Changed 12 years ago by ncohen

  • Status changed from needs_work to needs_review

Done ! :-)

comment:5 Changed 12 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to needs_work

Please add the following doctests:

  1. An example of is_chordal for a non-connected graph.
  1. 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 12 years ago by rlm

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 12 years ago by ncohen

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 ! :-)


comment:8 Changed 12 years ago by ncohen

  • Status changed from needs_work to needs_review

Here it is ! :-)

comment:9 Changed 12 years ago by ncohen

  • Priority changed from major to critical

comment:10 Changed 12 years ago by ncohen

Patch updated ! And based on the brand new 4.4.4.alpha0. Apply only this one !


Changed 12 years ago by ncohen

comment:11 Changed 12 years ago by rlm

  • Status changed from needs_review to positive_review

Looks good.

comment:12 Changed 12 years ago by edward.scheinerman

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 12 years ago by ncohen

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 :-)


comment:14 Changed 12 years ago by jason

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)
sage: hash(b)

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
sage: hash(a)
sage: hash(b)
sage: Graph({a: [b]})
Graph on 2 vertices

Does that address the problem? It introduces a problem, in that now you can't do:


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 12 years ago by ncohen

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 ? :-/


comment:16 Changed 12 years ago by rlm

  • Merged in set to sage-4.5.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.