After posting about the Hakimi-Havel theorem, I received a nice email suggesting various relevant papers. One of these was by Zoltán Király called " Recognizing Graphic Degree Sequences and Generating All Realizations ". I have now implemented a sketch of the main idea of the paper, which seems to work reasonably well, so I thought I would describe it. See the paper for details, of course. One focus of Király's method is to generate graphs efficiently , by which I mean that it has polynomial delay. In turn, an algorithm with 'polynomial delay' takes a polynomial amount of time between outputs (and to produce the first output). So - roughly - it doesn't take 1s to produce the first graph, 10s for the second, 2s for the third, 300s for the fourth, and so on. Central to the method is the tree that is traversed during the search for graphs that satisfy the input degree sequence. It's a little tricky to draw, but looks something like this: At the top
Comments
2) From the ebi ftp site - I /think/ the ChEBI team meant it to be public, but I will ask them
3) Probably not, they have a good website for this purpose.
4) Maybe, but again, depending on the team.
It is a nice test for bioclipse, but there are other similar tests, in a way.
* Chebi_lite.sdf file contains only the chemical structure, ChEBI identifier and ChEBI Name.
* Chebi_complete.sdf file contains all the chemical structures and associated information.