#14396: ISGCI update, small graphs and recognition
---------------------------------+----------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.12
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: Nathann Cohen | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+----------------------------------
Description changed by ncohen:
Old description:
> 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.
>
> Nathann
>
> [1] http://www.graphclasses.org/
>
> Apply:
>
> * [attachment:trac_14396.patch]
>
> And the new graphs SPKG :
> http://steinertriples.fr/graphs-20130402.p5.spkg
New description:
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.
Nathann
[1] http://www.graphclasses.org/
Apply:
* [attachment:trac_14396.patch]
And the new graphs SPKG : http://steinertriples.fr/graphs-20130920.p5.spkg
--
--
Ticket URL: <http://trac.sagemath.org/ticket/14396#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
