Graph classes, ISGCI, and interesting improvements ...

[Nathann Cohen]

Hello everybody !!!

This is the copy of several mails concerning ISGCI and what we could do with it in Sage. ISGCI (Information System on Graph Class Inclusions) can be seen ass a Java software, a Website, or an amazing database of graph classes. It contains a huge list of them, plus information on their inclusions, plus information on the complexity of several algorithms (Dominating set, coloring, etc ) on the corresponding classes. This would make a great Poset in Sage, as handy as Sloane's encyclopedia for graph theoreticians, and perhaps much more. Anyway, everything is explained in the following mails :-)

Nathann

[Nathann Cohen]

from Nathann Cohen <nathan...@gmail.com>
to gu...@informatik.uni-rostock.de
date 4 March 2010 00:10
subject isgci and Sagemath
mailed-by gmail.com

Hello !!!

I am a user and a developper of the Graph Library in the software Sage
Math ( http://sagemath.org/ ), an attempt to build a free alternative
to Maple... I would be very interested in using your database inside
this software, first as a handy way to question it, but also in order
to find, given, for example, a graph class, which kind of algorithm
would be best to solve on it a problem of maximal clique or vertex
coloring.

Could you tell me in which way it would be for us possible to use your
database ? Is it licensed under some GPL-compatible license ? Would we
need to directly send requests to you website ?

With many thanks for your help,

Nathann Cohen

[Nathann Cohen]

from Ernst de Ridder <hnri...@t-online.de>
reply-to Ernst de Ridder <hnri...@t-online.de>
to nathan...@gmail.com
cc Van Bang Le <l...@informatik.uni-rostock.de>
date 4 March 2010 19:51
subject ISGCI <-> Sagemath interfacing

> I am a user and a developper of the Graph Library in the software Sage
> Math ( http://sagemath.org/ ), an attempt to build a free alternative to
> Maple... I would be very interested in using your database inside this
> software, first as a handy way to question it, but also in order to
> find, given, for example, a graph class, which kind of algorithm would
> be best to solve on it a problem of maximal clique or vertex coloring.
>
> Could you tell me in which way it would be for us possible to use your
database ? Is it licensed under some GPL-compatible license ? Would we
need to directly send requests to you website ?

Hi Nathann,

thank you for your interest in ISGCI. In order to make the discussion on
how to interface a bit easier, first a bit of background on how ISGCI is
implemented.

ISGCI started life as an applet that could draw relations between graph
classes. Accordingly, most of the system is still written in java,
although there are some auxiliary tools that are written in Perl and in
Python. Originally, all there was, was the applet. Once we began to add
information to the system, we started to store information in
(generated) web pages. Currently, all the information on the classes is
visible in the web pages and the applet can be use to generate coloured
drawings of the relations between graph classes. The process goes
roughly like this:

input xml files -[java apps]-> derived xml files -[xslt scripts]-> web
pages
input xml files -[java apps]-> derived xml files -[java applet]->
drawing

As you will probably have noticed, the applet doesn't work so very well
anymore in modern java versions and the graph class pages look a bit
dated as well. Currently, we're testing ISGCI v3, which will work in
java 1.6 and have nicer looking web pages as well.

Now, if you want to access data from ISGCI, I see three ways:

1. We can give you copies of the derived xml database files.
Advantage: You're totally independent of ISGCI.
Disadvantage: You're missing out any updates to ISGCI, you have to do
your own parsing of these files. Below I attached snippets from these
files.

2. You write some clever script to extract the data you want from the
ISGCI web pages.
Advantage: No work for us:-)
Disadvantage: You have to rework your scripts whenever the format of the
web pages change.

3. You extract the data you want from ISGCI using a cgi interface.
Advantage: Flexible, always up-to-date data.
Disadvantage: not independent of ISGCI.

I'd say 2 is not a good idea, leaving 1 and 3. What I like about 3 is
that we have been thinking about a convenient way for the user of
querying the system rather than browsing it. With such an interface we
could swat 2 flies at once: Better querying inside ISGCI and querying
from outside ISGCI. However, this depends on
- what information you want to extract from ISGCI. Classes? Relations?
- in what format do you want to get it. Drawing? Text? Some xml
structure? A link to the graph class page in ISGCI?

So could you give examples of the queries you'd like to do and the type
of answer you'd expect? And would for your purpose on-line or off-line
access be better?

Ernst

P.S. Quite an impressive package, sage.

[Nathann Cohen]

from Nathann Cohen <nathan...@gmail.com>
to Ernst de Ridder <hnri...@t-online.de>
cc Van Bang Le <l...@informatik.uni-rostock.de>,
Alexandre Blondin Massé <alexandre.b...@gmail.com>
date  4 March 2010 21:40
subject  Re: ISGCI <-> Sagemath interfacing

Hello !!!!

> thank you for your interest in ISGCI.

It would have been hard not to have any... Your database is just amazing !

> I'd say 2 is not a good idea, leaving 1 and 3. What I like about 3 is
> that we have been thinking about a convenient way for the user of
> querying the system rather than browsing it. With such an interface we
> could swat 2 flies at once: Better querying inside ISGCI and querying
> from outside ISGCI. However, this depends on
> - what information you want to extract from ISGCI. Classes? Relations?
> - in what format do you want to get it. Drawing? Text? Some xml
> structure? A link to the graph class page in ISGCI?
>
> So could you give examples of the queries you'd like to do and the type
> of answer you'd expect? And would for your purpose on-line or off-line
> access be better?

Well. So now it seems to be my turn of explaining a bit what I am doing. I have sent several similar emails to people who were "hosting/developping/working on" very interesting projects, only to notice that I got no answer most of the time, or that because of license incompatibilities I should forget about it, or that they did not "really" want to share their work. I have to admit your answer is a relief :-)

Ok, so... I am a Phd Student in Graph Theory. I tried to find a good graph library for a while, even begun to write mine, then found something called Sage. Sage is much bigger than just graphs, as they want to obtain a good equivalent to Maple. Well, I quite like the fact that I do not have to care about coding parts of algorithms in which I am not interested because they depend on different areas of mathematics I never took the time to study, but Graph Theory is what I am mainly concerned about :-)

Sage is not a C library nor a Java library. It is python, and can be used interactively. So with Sage I have some way to work on graphs as I would use a calculator. I can use many algorithms on them, display them, save them, send them, tests conjecture just by generating random graphs, which takes only one line. Recently, I have been linking Sage with Linear Program solvers (GLPK, Coin, Cplex), and defining at almost no development cost many methods which are now available. The graph library now has something like 210+ methods, several more currently under review, and I am now trying to put some minor theory/treewidth in it. My last patch is a LP formulation of the H-Minor problem, and I think there is virtually no graph library around which can do this for the moment (even though, clearly, it is a veeeeeeeeeery slow function).

I wrote two short tutorials about the use of Graphs and Linear Programming in Sage :

Graph Theory in Sage : http://www-sop.inria.fr/members/Nathann.Cohen/tut/Graphs/
LP in Sage : http://www-sop.inria.fr/members/Nathann.Cohen/tut/LP/

Well, as expected  I went very far from my original point... ;-)

The thing is that I have recently been working on chordal graphs, interval graphs, etc.. There is in Sage a function for proper vertex coloring, and 3 algorithms available. I would like Sage to be able to deal with the general graphs as well as it can, but I do not want it to try a deep algorithm when I know my graph is chordal, and can be colored in linear time ! So I began to think about how this should be implemented. I do not want either to check at the beginning of each algorithm if my graph is chordal, if it is bipartite, if it is .... Many things are quick enough, for example both chordality and bipartiteness can be tested in linear time, but this is not my point. I would like to have a general way to deal with this. I can not create a class for each kind of Graph, as graphs are constantly modified and can not be expected to change their type at any moment. Anyway, a graph can be both Bipartite and 3-regular, so the properties need to be cumulated.


I can not either store the properties in our Graph object, as I can not update them each time the graph is modified. Actually, I am still thinking about what the best solution is. I ended up thinking a not so bad solution could be to have arguments in our functions (pretty easy in python) through which the user could give information on the structure of its graph, or ask Sage to test it.

For example, I would like the user to be able to type :

g = graphs.RandomIntervalGraph(50)
g.coloring(chordal = True)

Or even :

g = graphs.RandomIntervalGraph(50)
g.coloring(chordal = "Try")

In the first situation, Sage would assume the graph is chordal and color it accordingly, in the second it would check it before, and choose the best algorithm to use depending on the answer.

The thing is that there are many graph classes. What could I do with such an line :

g.coloring(interval_graph = True)

I first have to know that interval graphs are chordal ! Then my algorithm, as it would know how to deal with chordal graphs, would use the corresponding code.... This is where I thought about your great database. It would, first, be a great help for my problem, and would also make available into Sage a wealth of knowledge !

This way, we would be able, for any method, to write algorithms optimized for special classes of graphs, and the user, giving the best of knowledge he has on what he is dealing with, would be able to tell Sage what it should look for.

Now, Sage knows a lot of things about Posets. The first thing I thought about was to reencode all of your database (only the inclusion parts) as a Poset in Sage. The Poset of graph classes. It would be wonderfully easy to use it, and could even be interesting for research : if we know some classes are included in each other, and also that some are not, are there some undecided links ? Do we still wonder if some class A is or is not included in some other class B ? Well, this would take something like 3 lines of code once the Poset is built. I know I can sound a bit optimistic, but it would really be great to have such a database around in Sage, and not only for my purpose. If you were willing to share it, it would be great for us to also store information about complexity, etc, along with the Poset !

The best for us would be to have an off-line copy of your database. As it seems well formated, updating it once in a while should not be too painful. I even hope Sage users could tell us to update this or that part, which we would gladly forward to you :-)

I would be glad to hear your advice on all this. I am also forwarding this email to Alexandre Blondin Massé, a friend which whom I talked about all this already. Besides, would you agree if I were to forward our discussion to Sage-devel ? It is the google group of Sage developpers, and I expect some of them to be interested in all this :-)

Regards,

Nathann Cohen

[Nathann Cohen]

from Ernst de Ridder <hnri...@t-online.de>
reply-to      Ernst de Ridder <hnri...@t-online.de>

to      Nathann Cohen <nathan...@gmail.com>

cc      Van Bang Le <l...@informatik.uni-rostock.de>,
Alexandre Blondin Massé <alexandre.b...@gmail.com>

date  6 March 2010 19:20

subject  Re: ISGCI <-> Sagemath interfacing

Hi Nathann

> only to notice that I got no answer most of the time, or that
> because of license incompatibilities I should forget about it,
> or that they did not "really" want to share their work. I have
> to admit your answer is a relief :-)

Well, since we started ISGCI as a service to the scientific
community, it would be silly to tell people who want to use it
that they can't. The more, the merrier:-)

> The thing is that I have recently been working on chordal
> graphs, interval graphs, etc.. There is in Sage a function for
> proper vertex coloring, and 3 algorithms available. I would
> like Sage to be able to deal with the general graphs as well as
> it can, but I do not want it to try a deep algorithm when I
> know my graph is chordal, and can be colored in linear time !
> So I began to think about how this should be implemented. I do
> not want either to check at the beginning of each algorithm if
> my graph is chordal, if it is bipartite, if it is .... Many
> things are quick enough, for example both chordality and
> bipartiteness can be tested in linear time, but this is not my
> point. I would like to have a general way to deal with this.

Sounds like you'd like to implement so-called "robust" algorithms
in sage: Sloppily formulated, a robust algorithm is an algorithm
that either answers your question, or tells you that the input
graph is not in the class X. In your example of the vertex
colouring, a robust algorithm for colouring chordal graphs works
as follows:

Input: A graph G (not necessarily chordal!)
Output: Either a minimum colouring of G, or the statement "G is
not chordal".

So you do not need to test in advance whether G is chordal. Note
that when the algorithm does return a colouring, this does not
imply that G is chordal. It is possible that the algorithm can
calculate minimum colourings for some graphs that aren't chordal,
just not for all graphs. You do know that any colouring returned
by the algorithm is a minimum colouring, and that when the
algorithm cannot determine a minimum colouring, then the input
graphs is definitely not chordal.

> I can not create a class for each kind of Graph, as graphs are
> constantly modified and can not be expected to change their
> type at any moment.

Could be solved by a special method that makes an immutable copy
of a Graph. Once you know a Graph cannot change anymore, it's
worthwhile to spend time to analyze it's structure, like
determining to what graph class it belongs and annotating it
with e.g. its tree or clique decomposition.

> Anyway, a graph can be both Bipartite and 3-regular, so the
> properties need to be cumulated.

Unless you have the property 'bipartite and 3-regular', then one
stored property would suffice.

> I can not either store the properties in our Graph object, as I
> can not update them each time the graph is modified. Actually,
> I am still thinking about what the best solution is. I ended up
> thinking a not so bad solution could be to have arguments in
> our functions (pretty easy in python) through which the user
> could give information on the structure of its graph, or ask
> Sage to test it.

> For example, I would like the user to be able to type :
>   g = graphs.RandomIntervalGraph(50)
>   g.coloring(chordal = True)
> Or even :
>   g = graphs.RandomIntervalGraph(50)
>   g.coloring(chordal = "Try")

Would it also be possible to pass in a set of properties, e.g.
 g.coloring(chordal = True, ATFree = True)?

> The thing is that there are many graph classes. What could I do
> with such an line :
>   g.coloring(interval_graph = True)

The idea is clear. But if you only have algorithms for e.g.
chordal, bipartite, and general graphs, is it then convenient for
the user to specify one of 1000 other classes as the type of the
graph? Wouldn't it be easier for him to specify the desired
algorithm directly? Which are the 3 implemented algorithms for
colouring you mentioned?

> I first have to know that interval graphs are chordal ! Then my
> algorithm, as it would know how to deal with chordal graphs,
> would use the corresponding code.... This is where I thought
> about your great database. It would, first, be a great help for
> my problem, and would also make available into Sage a wealth of
> knowledge !

> Now, Sage knows a lot of things about Posets. The first thing I
> thought about was to reencode all of your database (only the
> inclusion parts) as a Poset in Sage. The Poset of graph
> classes. It would be wonderfully easy to use it, and could even

That would be straightforward. Simply write an XSLT script that
converts the XML to the proper python code and you're there.

> be interesting for research : if we know some classes are
> included in each other, and also that some are not, are there
> some undecided links ? Do we still wonder if some class A is or
> is not included in some other class B ? Well, this would take
> something like 3 lines of code once the Poset is built. I know

One problem here: ISGCI has no information that some class is NOT
contained in another class. It only has \subseteq relations. In
fact non-inclusions is the single most discussed topic on our
list of Things-That-We-Really-Should-Implement. Unfortunately,
we're also really short of time:-( On the good side, you've given
us yet another incentive to really start implementing this:)

> The best for us would be to have an off-line copy of your
> database. As it seems well formated, updating it once in a
> while should not be too painful.

I've attached two files: An xml file containing the data used for
generating the web pages and its dtd. When parsing the xml file,
take special care with the note element: Its contents can be
arbitrary text, including non-well formed xml. This makes it
possible to specify html code in the original input file without
all sorts of difficult quoting. We use a recursive invocation of a
specially adapted parser for this.

If all you're interested in right now are the inclusions, I would
recommended the following:

1. Read in graphclasses
< GraphClass id="xxid" type="xxtype">
< name>...</name>
...stuff to be ignored...
< /GraphClass>
2. Read in inclusions
< incl super="xxid" sub="yyid">
...stuff to be ignored...
< /incl>
3. Calculate transitive closure
4. Throw away graph classes
- that have id starting with AUTO_
- that have type="forbidden" (i.e. X-free graphs, e.g.
 C_{n+4}-free = chordal)
5. Calculate transitive reduction

If you need an explanation on what some element in the file
means, just ask.

> I even hope Sage users could tell us to update this or that
> part, which we would gladly forward to you :-)

Any additions to the data or suggestions for improvements are
welcome. Should you use data from isgci in sage, then we'd also
appreciate a link. In fact, we'd appreciate a link even if you don't use
any data from isgci ;-P

> I would be glad to hear your advice on all this. I am also
> forwarding this email to Alexandre Blondin Massé, a friend
> which whom I talked about all this already. Besides, would you
> agree if I were to forward our discussion to Sage-devel ? It is
> the google group of Sage developpers, and I expect some of them
> to be interested in all this :-)

All fine with me. Since I don't have time to monitor the
discussion on sage-devel, I'd appreciate it if you would forward
relevant discussions there to me.

Ernst

[Jason Grout]

This looks *very* interesting. Thanks for pursuing this!

Jason

[Nathann Cohen]

Hello everybody !!

After a looooong time, I finally wrote this patch, and it is now available as ticket 11880. 

http://trac.sagemath.org/sage_trac/ticket/11880

Anf if anybody is interested by the review.... There is much more documentation than actual code :-)

Nathann