#14396: ISGCI update, small graphs and recognition
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.9
Component: graph theory | Keywords:
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies:
Stopgaps: |
----------------------------+-----------------------------------------------
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/
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14396>
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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
