Opened 9 years ago

Closed 9 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)

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

Download all attachments as: .zip

Change History (17)

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 9 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 9 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 9 years ago by ncohen

  • Status changed from needs_work to needs_review

Done ! :-)

comment:5 Changed 9 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 9 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 9 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 ! :-)

Nathann

comment:8 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

Here it is ! :-)

comment:9 Changed 9 years ago by ncohen

  • Priority changed from major to critical

comment:10 Changed 9 years ago by ncohen

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

Nathann

Changed 9 years ago by ncohen

comment:11 Changed 9 years ago by rlm

  • Status changed from needs_review to positive_review

Looks good.

comment:12 Changed 9 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 9 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 :-)

Nathann

comment:14 Changed 9 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)
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 9 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 ? :-/

Nathann

comment:16 Changed 9 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.