Opened 8 years ago
Closed 6 years ago
#14396 closed enhancement (fixed)
ISGCI update, small graphs and recognition
Reported by:  ncohen  Owned by:  jason, ncohen, rlm 

Priority:  major  Milestone:  sage6.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 )
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 diamondfree 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 graphs20130920.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/rawattachment/ticket/14396/graphs20130920.tar.bz2
Attachments (1)
Change History (25)
comment:1 Changed 8 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 8 years ago by
 Cc Konrad127123 added
comment:3 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:4 Changed 7 years ago by
 Description modified (diff)
comment:5 Changed 7 years ago by
 Branch set to u/ncohen/14396
 Cc elixyre added
 Description modified (diff)
comment:6 Changed 7 years ago by
 Commit set to 96aac188ea19fdf840cb5e75b649c873a49aaefe
Changed 7 years ago by
comment:7 Changed 7 years ago by
 Description modified (diff)
comment:8 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:9 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:10 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:11 followup: ↓ 13 Changed 6 years ago by
 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 6 years ago by
 Commit changed from 96aac188ea19fdf840cb5e75b649c873a49aaefe to f287feee7a4e8ff6a52864191d655924b86448ed
comment:13 in reply to: ↑ 11 Changed 6 years ago by
 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 followup: ↓ 16 Changed 6 years ago by
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/sitepackages/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 (201104) 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 6 years ago by
 Description modified (diff)
comment:16 in reply to: ↑ 14 Changed 6 years ago by
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 notgraph_classes.smallgraphs()
.
Fixed.
Nathann
comment:17 Changed 6 years ago by
 Commit changed from f287feee7a4e8ff6a52864191d655924b86448ed to b44dcb00da4bd94a264a81e545bf0b03ae76c64f
Branch pushed to git repo; I updated commit sha1. New commits:
b44dcb0  trac #14396: Review

comment:18 Changed 6 years ago by
 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 6 years ago by
Wow.
Wow.
Reviewed.
Wow.
comment:20 Changed 6 years ago by
(Thanks)
comment:21 Changed 6 years ago by
 Status changed from positive_review to needs_work
Missing link to the new graphs database
comment:22 Changed 6 years ago by
 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 6 years ago by
 Description modified (diff)
comment:24 Changed 6 years ago by
 Branch changed from u/ncohen/14396 to b44dcb00da4bd94a264a81e545bf0b03ae76c64f
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #14396: ISGCI update, small graphs and recognition