ISGCI update, small graphs and recognition #14396

nathanncohen · 2013-04-02T09:08:28Z

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: https://github.com/sagemath/sage-prod/files/10657524/graphs-20130920.tar.bz2.gz

CC: @nthiery @dimpase @dcoudert @Konrad127123 @sagetrac-elixyre

Component: graph theory

Author: Nathann Cohen

Branch/Commit: b44dcb0

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/14396

The text was updated successfully, but these errors were encountered:

nathanncohen · 2013-04-02T09:27:54Z

Author: Nathann Cohen

nathanncohen · 2013-12-31T15:53:32Z

Branch: u/ncohen/14396

sagetrac-git · 2013-12-31T15:54:05Z

Commit: 96aac18

sagetrac-git · 2013-12-31T15:54:05Z

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

`96aac18`	`trac #14396: ISGCI update, small graphs and recognition`

nathanncohen · 2013-12-31T15:55:02Z

Attachment: graphs-20130920.tar.bz2.gz

dcoudert · 2015-01-19T15:27:17Z

Reviewer: David Coudert

dcoudert · 2015-01-19T15:27:17Z

comment:11

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'}
**********************************************************************

sagetrac-git · 2015-01-20T15:00:17Z

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

`7857634`	`trac #14396: Merged with 6.5.beta5`
`f287fee`	`trac #14396: Review`

sagetrac-git · 2015-01-20T15:00:17Z

Changed commit from 96aac18 to f287fee

nathanncohen · 2015-01-20T15:02:35Z

comment:13

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

dcoudert · 2015-01-20T15:35:00Z

comment:14

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.

nathanncohen · 2015-01-20T15:53:45Z

comment:16

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

sagetrac-git · 2015-01-20T15:54:06Z

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

`b44dcb0`	`trac #14396: Review`

sagetrac-git · 2015-01-20T15:54:06Z

Changed commit from f287fee to b44dcb0

dcoudert · 2015-01-20T16:47:22Z

comment:18

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

David.

nathanncohen · 2015-01-20T17:10:04Z

comment:19

Wow.

Reviewed.

Wow.

nathanncohen · 2015-01-20T17:10:10Z

comment:20

(Thanks)

vbraun · 2015-01-23T15:19:15Z

comment:21

Missing link to the new graphs database

nathanncohen · 2015-01-23T15:33:30Z

comment:22

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

Nathann

vbraun · 2015-01-24T13:19:17Z

Changed branch from u/ncohen/14396 to b44dcb0

nathanncohen mannequin added this to the sage-5.11 milestone Apr 2, 2013

nathanncohen mannequin added c: graph theory labels Apr 2, 2013

nathanncohen mannequin assigned jasongrout, nathanncohen and rlmill Apr 2, 2013

This comment has been minimized.

Sign in to view

nathanncohen mannequin added the s: needs review label Apr 2, 2013

jdemeyer modified the milestones: sage-5.11, sage-5.12 Aug 13, 2013

This comment has been minimized.

Sign in to view

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.2, sage-6.3 May 6, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.3, sage-6.4 Aug 10, 2014

dcoudert added s: needs work and removed s: needs review labels Jan 19, 2015

nathanncohen mannequin added s: needs review and removed s: needs work labels Jan 20, 2015

This comment has been minimized.

Sign in to view

dcoudert added s: positive review and removed s: needs review labels Jan 20, 2015

vbraun added s: needs work and removed s: positive review labels Jan 23, 2015

nathanncohen mannequin added s: positive review and removed s: needs work labels Jan 23, 2015

This comment has been minimized.

Sign in to view

vbraun removed the s: positive review label Jan 24, 2015

vbraun closed this as completed in 6b5e76f Jan 24, 2015

jm58660 mannequin mentioned this issue Feb 18, 2015

Convert database_odlyzko_zeta to new-style package #17064

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ISGCI update, small graphs and recognition #14396

ISGCI update, small graphs and recognition #14396

nathanncohen mannequin commented Apr 2, 2013

This comment has been minimized.

nathanncohen mannequin commented Apr 2, 2013

This comment has been minimized.

This comment has been minimized.

nathanncohen mannequin commented Dec 31, 2013

sagetrac-git mannequin commented Dec 31, 2013

sagetrac-git mannequin commented Dec 31, 2013

nathanncohen mannequin commented Dec 31, 2013

This comment has been minimized.

dcoudert commented Jan 19, 2015

dcoudert commented Jan 19, 2015

sagetrac-git mannequin commented Jan 20, 2015

sagetrac-git mannequin commented Jan 20, 2015

nathanncohen mannequin commented Jan 20, 2015

dcoudert commented Jan 20, 2015

This comment has been minimized.

nathanncohen mannequin commented Jan 20, 2015

sagetrac-git mannequin commented Jan 20, 2015

sagetrac-git mannequin commented Jan 20, 2015

dcoudert commented Jan 20, 2015

nathanncohen mannequin commented Jan 20, 2015

nathanncohen mannequin commented Jan 20, 2015

vbraun commented Jan 23, 2015

nathanncohen mannequin commented Jan 23, 2015

This comment has been minimized.

vbraun commented Jan 24, 2015

ISGCI update, small graphs and recognition #14396

ISGCI update, small graphs and recognition #14396

Comments

nathanncohen mannequin commented Apr 2, 2013

This comment has been minimized.

nathanncohen mannequin commented Apr 2, 2013

This comment has been minimized.

This comment has been minimized.

nathanncohen mannequin commented Dec 31, 2013

sagetrac-git mannequin commented Dec 31, 2013

sagetrac-git mannequin commented Dec 31, 2013

nathanncohen mannequin commented Dec 31, 2013

This comment has been minimized.

dcoudert commented Jan 19, 2015

dcoudert commented Jan 19, 2015

sagetrac-git mannequin commented Jan 20, 2015

sagetrac-git mannequin commented Jan 20, 2015

nathanncohen mannequin commented Jan 20, 2015

dcoudert commented Jan 20, 2015

This comment has been minimized.

nathanncohen mannequin commented Jan 20, 2015

sagetrac-git mannequin commented Jan 20, 2015

sagetrac-git mannequin commented Jan 20, 2015

dcoudert commented Jan 20, 2015

nathanncohen mannequin commented Jan 20, 2015

nathanncohen mannequin commented Jan 20, 2015

vbraun commented Jan 23, 2015

nathanncohen mannequin commented Jan 23, 2015

This comment has been minimized.

vbraun commented Jan 24, 2015