Opened 6 years ago

Closed 4 years ago

#14396 closed enhancement (fixed)

ISGCI update, small graphs and recognition

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-6.4
Component: graph theory Keywords:
Cc: nthiery, dimpase, dcoudert, Konrad127123, elixyre Merged in:
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: b44dcb0 (Commits) Commit: b44dcb00da4bd94a264a81e545bf0b03ae76c64f
Dependencies: Stopgaps:

Description (last modified by vbraun)

Helloooooooooooooooo !

This patch is nice ! It adds in Sage the list of smallgraphs used in ISGCI [1], which can now be obtained like that :

sage: d = graph_classes.smallgraphs()
sage: d['P_5']                                                                                                                                                           
Graph on 5 vertices
sage: d['P_5'].is_isomorphic(graphs.PathGraph(5))
True

Now that we have this information, we can do another veeeeeeery nice thing : write a generic recognition algorithm for graph classes defined by a list of forbidden subgraphs.

    sage: g = graphs.PetersenGraph()                                                                                                                                      
    sage: g in graph_classes.ClawFree                                                                                                                                     
    False                                                                                                                                                                 
    sage: g.line_graph() in graph_classes.ClawFree                                                                                                                        
    True                                                                                                                                                                                                                                                                                                                       
    sage: gc = graph_classes.get_class("gc_441")                                                                                                                          
    sage: gc                                                                                                                                                              
    diamond--free graphs                                                                                                                                                  
    sage: graphs.PetersenGraph() in gc                                                                                                                                    
    True   

Of course there is no specific code written for these classes. The list of subgraphs is obtained from the ISGCI database, and each of them is tested.... Nice generic stuff. Of course many graph classes are not defined in such a way, so everything is not done on that front ;-)

And of course, it's an occasion to update the version of ISGCI we ship in Sage.

Howto:

After applying the branch's commits, one has to save graphs-20130920.tar.bz2 to the build/upstream/ directory and run sage -i graphs again.

Nathann

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

Updated tarball: http://trac.sagemath.org/raw-attachment/ticket/14396/graphs-20130920.tar.bz2

Attachments (1)

graphs-20130920.tar.bz2 (292.4 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (25)

comment:1 Changed 6 years ago by ncohen

  • Authors set to Nathann Cohen
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by Konrad127123

  • Cc Konrad127123 added

comment:3 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:5 Changed 6 years ago by ncohen

  • Branch set to u/ncohen/14396
  • Cc elixyre added
  • Description modified (diff)

comment:6 Changed 6 years ago by git

  • Commit set to 96aac188ea19fdf840cb5e75b649c873a49aaefe

Branch pushed to git repo; I updated commit sha1. New commits:

96aac18trac #14396: ISGCI update, small graphs and recognition

Changed 6 years ago by ncohen

comment:7 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:8 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:9 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:10 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:11 follow-up: Changed 5 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to needs_work

Hello,

I tried this patch and indeed it is cool :)

If I understand well, each time we implement a new membership test to a graph class, we should try to include it in isgci module, right? Also, is there a simple way for the user to know which recognition tests are available?

A small error:

**********************************************************************
File "src/sage/graphs/isgci.py", line 758, in sage.graphs.isgci.GraphClasses.smallgraphs
Failed example:
    t[0]
Expected:
    {'super': 'gc_2', 'sub': 'gc_1'}
Got:
    {'sub': 'gc_1', 'super': 'gc_2'}
**********************************************************************

comment:12 Changed 4 years ago by git

  • Commit changed from 96aac188ea19fdf840cb5e75b649c873a49aaefe to f287feee7a4e8ff6a52864191d655924b86448ed

Branch pushed to git repo; I updated commit sha1. New commits:

7857634trac #14396: Merged with 6.5.beta5
f287feetrac #14396: Review

comment:13 in reply to: ↑ 11 Changed 4 years ago by ncohen

  • Status changed from needs_work to needs_review

Yo !

I tried this patch and indeed it is cool :)

I had almost forgotten about it. Two years old :-P

If I understand well, each time we implement a new membership test to a graph class, we should try to include it in isgci module, right?

Yes, if we want the syntax g in graph_classes.X to use it.

Also, is there a simple way for the user to know which recognition tests are available?

Do you mean "to get the list of all classes defined by forbidden subgraphs"? If so, I don't think so. For specific recognition problems, however, they often correspond to our "Graph.is_*" functions.

A small error:

Fixed.

Nathann

comment:14 follow-up: Changed 4 years ago by dcoudert

In the description of method graph_classes.smallgraphs is weird:

sage: graph_classes.smallgraphs?
Type:            CachedMethodCallerNoArgs
String form:     Cached version of <function smallgraphs at 0x1132b62a8>
File:            /Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/misc/cachefunc.so
Definition:      graph_classes.smallgraphs(self)
Docstring:
   Returns a dictionary associating a graph to a graph description
   string.

   Upon the first call, this loads the database from the local XML
   files. Subsequent calls are cached.

   EXAMPLES:

      sage: t = graph_classes.inclusions()
      sage: type(t)
      <type 'list'>
      sage: t[0]
      {'sub': 'gc_1', 'super': 'gc_2'}

Class docstring:
   Utility class that is used by "CachedMethod" to bind a cached
   method to an instance, in the case of a method that does not accept
   any arguments except "self".

   Note: The return value "None" would not be cached. So, if you
     have a method that does not accept arguments and may return
     "None" after a lengthy computation, then "@cached_method" should
     not be used.

   EXAMPLE:

      sage: P.<a,b,c,d> = QQ[]
      sage: I = P*[a,b]
      sage: I.gens
      Cached version of <function gens at 0x...>
      sage: type(I.gens)
      <type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'>
      sage: I.gens is I.gens
      True
      sage: I.gens() is I.gens()
      True

   AUTHOR:

   * Simon King (2011-04)
Init docstring:
   EXAMPLES:

      sage: class Foo:
      ....:     def __init__(self, x):
      ....:         self._x = x
      ....:     @cached_method
      ....:     def f(self):
      ....:         return self._x^2
      sage: a = Foo(2)
      sage: print a.f.get_cache()
      None
      sage: a.f()
      4
      sage: a.f.get_cache()
      4
Call docstring:
   Call the cached method.

   EXAMPLE:

      sage: P.<a,b,c,d> = QQ[]
      sage: I = P*[a,b]
      sage: I.gens()    # indirect doctest
      [a, b]
      sage: I.gens() is I.gens()
      True

Furthermore, the example exposes graph_classes.inclusions() but not graph_classes.smallgraphs().

The rest seems ok.

David.

comment:15 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:16 in reply to: ↑ 14 Changed 4 years ago by ncohen

Yo !

In the description of method graph_classes.smallgraphs is weird:

That's because the method is a cached_method, and the documentation of cached_method is automatically appended to the function's doc. I don't think that it help either :-/

Furthermore, the example exposes graph_classes.inclusions() but not graph_classes.smallgraphs().

Fixed.

Nathann

comment:17 Changed 4 years ago by git

  • Commit changed from f287feee7a4e8ff6a52864191d655924b86448ed to b44dcb00da4bd94a264a81e545bf0b03ae76c64f

Branch pushed to git repo; I updated commit sha1. New commits:

b44dcb0trac #14396: Review

comment:18 Changed 4 years ago by dcoudert

  • Status changed from needs_review to positive_review

Perfect. For me the patch is good to go (installation, tests, doc build, etc.). Cool!

David.

comment:19 Changed 4 years ago by ncohen

Wow.

Wow.

Reviewed.

Wow.

comment:20 Changed 4 years ago by ncohen

(Thanks)

comment:21 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Missing link to the new graphs database

comment:22 Changed 4 years ago by ncohen

  • Status changed from needs_work to positive_review

It is attached to this ticket. I know we should avoid that, sorry. I did not know that two years ago apparently ^^;

Nathann

comment:23 Changed 4 years ago by vbraun

  • Description modified (diff)

comment:24 Changed 4 years ago by vbraun

  • Branch changed from u/ncohen/14396 to b44dcb00da4bd94a264a81e545bf0b03ae76c64f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.