Opened 8 years ago

Last modified 7 years ago

#11880 closed enhancement

ISGCI in Sage (a Graph Classes database http://www.graphclasses.org/ ) — at Version 19

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.1
Component: graph theory Keywords:
Cc: nthiery, jason, ekirkman Merged in:
Authors: Nathann Cohen Reviewers: Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

This ticket creates a file

sage/graphs/isgci.py

That is a first implementation of an interface between Sage and the Graph Classes database ISGCI ![1]. With this interface, the XML content of the database can be read using dictionaries and lists (much easier to work with), and some operations are implemented like the comparison (relatively to inclusion) of graph classes.

There will be more work needed on this new feature, for instance the implementation of an easy way to query the database.

Along with the patch, two .sobj files should be added to the directory $SAGE_ROOT/data/graphs/. These files are an .sobj version of the database that I created on my own computer.

When this patch will be merged into Sage, it is likely that users that do not update their version of Sage will progressively then be working with an outdated version of the database, as the version will be the one used the day they downloaded their copy of Sage. To avoid that, this patch implements a function sage.graphs.isgci.update_db() that downloads a new version of the database from ISGCI's website and updates the current .sobj files.

Hence, instead of using my two files attached to this ticket, one can also call this method which will create them automatically.

I tried to make the documentation clear enough about all that is currently possible with ISGCI.

One of the discussions on sage-devel related to this database: http://groups.google.com/forum/#!searchin/sage-devel/This$20is$20the$20copy$20of$20several$20mails$20concerning$20ISGCI$20and$20what$20we$20could$20do$20with/sage-devel/N05a9w_UrIA/XGlVD7NT7p4J

Nathann

![1] http://www.graphclasses.org/


Apply :

Add to SAGE_ROOT/data/graphs/:

Change History (27)

comment:1 Changed 8 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 8 years ago by leif

  • Description modified (diff)

Changed 8 years ago by ncohen

Changed 8 years ago by ncohen

Changed 8 years ago by ncohen

comment:4 follow-up: Changed 8 years ago by nthiery

  • Reviewers set to Nicolas M. Thiéry

Hi Nathann!

I have just been trough the patch, and am overall happy with it! I noticed a couple typos, which I'll fix in a little patch.

Just one thing. Instead of:

    global classes, class_digraph 
    _load_ISGCI_if_not_loaded() 

what about using some idiom like:

    classes = igsci.classes()
    class_diagraph = igsci.class_digraph()

where classes would be a cached method (or cached function depending on whether igsci is a module or an object) whose first step would be to load the database; similarly class_digraph would be a cached method calling igsci.classes(), and then building the digraph, and so on.

Two other little suggestions:

  • class_digraph -> inclusion_digraph?
  • classs -> cls (it seems to be the standard shorthand to workaround the reserved keyword)

comment:5 in reply to: ↑ 4 ; follow-up: Changed 8 years ago by ncohen

where classes would be a cached method (or cached function depending on whether igsci is a module or an object) whose first step would be to load the database; similarly class_digraph would be a cached method calling igsci.classes(), and then building the digraph, and so on.

Ahahaah ! Of course, let us do it "the sage-combinat way". It would be nice to have isgci inherit from UniqueRepresentant?, and add some decorations inside of it :-)

I am waiting for your typo patch and I will change that if you did not do it already :-)

I also need to see how cachedmethod is written, just to breathe easier :-)

Two other little suggestions:

  • class_digraph -> inclusion_digraph?
  • classs -> cls (it seems to be the standard shorthand to workaround the reserved keyword)

+1 !

Nathann

comment:6 in reply to: ↑ 5 Changed 8 years ago by nthiery

Replying to ncohen:

I am waiting for your typo patch and I will change that if you did not do it already :-)

Please go ahead if you feel like it; I won't have my reviewer's patch before tonight.

I also need to see how cachedmethod is written, just to breathe easier :-)

It's super optimized and in Cython since #11115, thanks to Simon.

Nicolas

comment:7 Changed 8 years ago by nthiery

  • Status changed from needs_review to needs_work

comment:8 Changed 8 years ago by nthiery

Hi Nathann!

I hope this won't conflict too much, since I did quite a few documentation changes after all. Feel free to take or drop all my suggestions in the attached reviewer's patch. I left also a couple TODO's; again mostly suggestions.

Cheers,

Nicolas

comment:9 follow-up: Changed 8 years ago by nthiery

I forgot: the patch is also on the Sage-Combinat queue if you want.

comment:10 in reply to: ↑ 9 ; follow-up: Changed 8 years ago by hivert

Replying to nthiery:

I forgot: the patch is also on the Sage-Combinat queue if you want.

Just for the record: There are problems with the added TODO in the doc:

/home/data/Sage-Install/sage-5.0.beta2/local/lib/python2.7/site-packages/sage/graphs/isgci.py:docstring of sage.graphs.isgci:109: ERROR: Error parsing content block for the "list-table" directive: two-level bullet list expected, but row 2 does not contain a second-level bullet list.

.. list-table::
   :widths: 20 30
   :header-rows: 1

   * - Class
     - Related methods

   * - BinaryTrees

     TODO: use .. seealso:: in all entries of this list?

     - :meth:`BalancedTree <sage.graphs.graph_generators.GraphGenerators.BalancedTree>`,
       :meth:`is_tree <sage.graphs.generic_graph.GenericGraph.is_tree>`
[...]

Changed 8 years ago by nthiery

comment:11 in reply to: ↑ 10 Changed 8 years ago by nthiery

Just for the record: There are problems with the added TODO in the doc:

Fixed.

comment:12 Changed 8 years ago by ncohen

Helloooooo Nicolas !

Well, I updated the GraphClasses? class so that it now has classes() and inclusion_digraph() methods, and finally noticed that all the other functions (_load_ISGCI_[...]) or update_ISGCI) and all that stuff would be much better as methods of GraphClasses? as it is now unique. Now, moving functions around would make the patch impossible to read, as it would "remove all lines" and "add the same lines later in the file, with an increased indentation". Hence I will upload many patches to this ticket :

  • the first one will contain the modifications I mentionned
  • The second will *ONLY* move the methods in the file
  • The third one will modify them so that they will work (because they will demand a self argument for instances, and other things).

I hope the review will not be too hard :-)

Nathann

comment:13 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:14 Changed 8 years ago by ncohen

  • Description modified (diff)

Changed 8 years ago by ncohen

comment:15 Changed 8 years ago by ncohen

  • Description modified (diff)

Changed 8 years ago by ncohen

comment:16 Changed 8 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Hellooooooo !!

With this new patch the class works again. It is not totally "object-oriented", and way nicer. Nicolas : I believe I addressed all of your remarks except one :

# TODO: or systematically use the user's version if it exists,
# throwing a warning if it is not the most recent?

This TODO appears in the part of the code that loads "the most recent" version of the database. Why would you want to only load the user's version instead of the most recent one ? I thought that this way all users may benefit from a global update...

About returning to the user the exception raised by a wrong access to a file I did not know what to do exactly. There is nothing wrong going on if the user cannot write to the system-wide database, so this exception is still caught. On the other hand he should be able to write to his own DOT_SAGE folder, so in this second case the code does not catch the exception anymore.

Well... I think that's all I had to say :-)

Nathann

Changed 8 years ago by ncohen

Changed 8 years ago by nthiery

comment:17 follow-up: Changed 8 years ago by nthiery

Hi Nathann,

I just went back through the patches (I folded them on the Sage-Combinat queue: trac_11880-isgci-all_in_one-nc.patch). I added a reviewer patch adding a bit of doc, and using the shorter syntax for links, and using further cached methods.

It's basically good enough to go, up to little details:

  • doc coverage:
      zephyr-~s>sage -coverage graphs/isgci.py 
      ----------------------------------------------------------------------
      graphs/isgci.py
      SCORE graphs/isgci.py: 64% (11 of 17)
    
      Missing documentation:
      	 * __init__(self, name, gc_id):
     	 * __le__(self, other):
    	 * __ge__(self, other):
    	 * __eq__(self, other):
    	 * __lt__(self, other):
    
      Missing doctests:
    	 * __hash__(self):
    
  • I am not sure about the name of the method show since for other Sage objects, this opens a plot.
  • I have not retested _download_db and friends

comment:18 Changed 8 years ago by nthiery

  • Status changed from needs_review to needs_work

comment:19 in reply to: ↑ 17 Changed 8 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Hi Nathann,

Wow !! This patch's almost good ! GREAAAAAAAAT ! :-)

I just went back through the patches (I folded them on the Sage-Combinat queue: trac_11880-isgci-all_in_one-nc.patch). I added a reviewer patch adding a bit of doc, and using the shorter syntax for links, and using further cached methods.

I saw that... Thank you very much !

  • doc coverage:

Argggg... Ok, it's now fixed :-)

  • I am not sure about the name of the method show since for other Sage objects, this opens a plot.

Then I made the mistake twice, as the MixedIntegerLinearProgram? object also have a .show() method that does not plot anything. Though you are right, perhaps the name "show" is not descriptive enough... What would you think of graph_classes.Chordal.description() to obtain the same information ? :-)

  • I have not retested _download_db and friends

I have not modified them. Actually, since I reinstalled Sage since the last time I worked on this patch I obtained an error the first time I ran isgci, and I fixed it by running graph_classes.update_db() :-)

Nathann

Note: See TracTickets for help on using tickets.