This module implements an interface to the ISGCI database in Sage.
This database gathers information on graph classes and their inclusions in each other. It also contains information on the complexity of several computational problems.
It is available on the GraphClasses.org website maintained by H.N. de Ridder et al.
Presently, it is possible to use this database through the variables and methods present in the graph_classes object. For instance:
sage: Trees = graph_classes.Tree
sage: Chordal = graph_classes.Chordal
It is then possible to check the inclusion of classes inside of others, if the information is available in the database:
sage: Trees <= Chordal
True
And indeed, trees are chordal graphs.
The ISGCI database is not all-knowing, and so comparing two classes can return True, False, or Unknown (see the documentation of the Unknown truth value).
An unknown answer to A <= B only means that ISGCI cannot deduce from the information in its database that A is a subclass of B nor that it is not. For instance, ISGCI does not know at the moment that some chordal graphs are not trees:
sage: graph_classes.Chordal <= graph_classes.Tree
Unknown
Given a graph class, one can obtain its associated information in the ISGCI database with the description() method:
sage: Chordal.description()
Class of graphs : Chordal
-------------------------
type : base
id : gc_32
name : chordal
Problems :
-----------
3-Colourability : Linear
Clique : Polynomial
Clique cover : Polynomial
Cliquewidth : Unbounded
Cliquewidth expression : NP-complete
Colourability : Linear
Cutwidth : NP-complete
Domination : NP-complete
Feedback vertex set : Polynomial
Hamiltonian cycle : NP-complete
Hamiltonian path : NP-complete
Independent set : Linear
Maximum bisection : Unknown
Maximum cut : NP-complete
Minimum bisection : Unknown
Recognition : Linear
Treewidth : Polynomial
Weighted clique : Polynomial
Weighted feedback vertex set : Unknown
Weighted independent set : Linear
It is possible to obtain the complete list of the classes stored in ISGCI by calling the show_all() method (beware – long output):
sage: graph_classes.show_all()
id | name | type | smallgraph
----------------------------------------------------------------------------------------------------------------------
gc_309 | $K_4$--minor--free | base |
gc_541 | $N^*$ | base |
gc_215 | $N^*$--perfect | base |
gc_5 | $P_4$--bipartite | base |
gc_3 | $P_4$--brittle | base |
gc_6 | $P_4$--comparability | base |
gc_7 | $P_4$--extendible | base |
...
Until a proper search method is implemented, this lets one find classes which do not appear in graph_classes.*.
To retrieve a class of graph from its ISGCI ID one may use the get_class() method:
sage: GC = graph_classes.get_class("gc_5")
sage: GC
$P_4$--bipartite graphs
The graph classes represented by the ISGCI database can alternatively be used to access recognition algorithms. For instance, in order to check that a given graph is a tree one has the following the options
sage: graphs.PathGraph(5) in graph_classes.Tree
True
or:
sage: graphs.PathGraph(5).is_tree()
True
Furthermore, all ISGCI graph classes which are defined by the exclusion of a finite sequence of induced subgraphs benefit from a generic recognition algorithm. For instance
sage: g = graphs.PetersenGraph()
sage: g in graph_classes.ClawFree
False
sage: g.line_graph() in graph_classes.ClawFree
True
Or directly from ISGCI
sage: gc = graph_classes.get_class("gc_441")
sage: gc
diamond--free graphs
sage: graphs.PetersenGraph() in gc
True
graph_classes currently predefines the following graph classes
Class | Related methods |
---|---|
BinaryTrees | BalancedTree(), is_tree() |
Bipartite | BalancedTree(), is_bipartite() |
Block | blocks_and_cut_vertices() |
Chordal | is_chordal() |
Claw-Free | ClawGraph() |
Comparability | |
Gallai | is_gallai_tree() |
Grid | Grid2dGraph(), GridGraph() |
Interval | RandomInterval(), IntervalGraph(), is_interval() |
Line | line_graph_forbidden_subgraphs(), is_line_graph() |
Modular | modular_decomposition() |
Outerplanar | is_circular_planar() |
Perfect | is_perfect() |
Planar | is_planar() |
Split | is_split() |
Tree | trees(), is_tree() |
UnitDisk | IntervalGraph() |
UnitInterval | is_interval() |
The database is stored by Sage in two ways.
The classes: the list of all graph classes and their properties is stored in a huge dictionary (see classes()). Below is what Sage knows of gc_249:
sage: graph_classes.classes()['gc_249'] # random
{'problem':
{'Independent set': 'Polynomial',
'Treewidth': 'Unknown',
'Weighted independent set': 'Polynomial',
'Cliquewidth expression': 'NP-complete',
'Weighted clique': 'Polynomial',
'Clique cover': 'Unknown',
'Domination': 'NP-complete',
'Clique': 'Polynomial',
'Colourability': 'NP-complete',
'Cliquewidth': 'Unbounded',
'3-Colourability': 'NP-complete',
'Recognition': 'Linear'},
'type': 'base',
'id': 'gc_249',
'name': 'line'}
The class inclusion digraph: Sage remembers the class inclusions through the inclusion digraph (see inclusion_digraph()). Its nodes are ID of ISGCI classes:
sage: d = graph_classes.inclusion_digraph()
sage: d.vertices()[-10:]
['gc_990', 'gc_991', 'gc_992', 'gc_993', 'gc_994', 'gc_995', 'gc_996', 'gc_997', 'gc_998', 'gc_999']
An arc from gc1 to gc2 means that gc1 is a superclass of gc2. This being said, not all edges are stored ! To ensure that a given class is included in another one, we have to check whether there is in the digraph a path from the first one to the other:
sage: bip_id = graph_classes.Bipartite._gc_id
sage: perfect_id = graph_classes.Perfect._gc_id
sage: d.has_edge(perfect_id, bip_id)
False
sage: d.distance(perfect_id, bip_id)
2
Hence bipartite graphs are perfect graphs. We can see how ISGCI obtains this result
sage: p = d.shortest_path(perfect_id, bip_id)
sage: len(p) - 1
2
sage: print p # random
['gc_56', 'gc_76', 'gc_69']
sage: for c in p:
... print graph_classes.get_class(c)
perfect graphs
...
bipartite graphs
What ISGCI knows is that perfect graphs contain unimodular graph which contain bipartite graphs. Therefore bipartite graphs are perfect !
Note
The inclusion digraph is NOT ACYCLIC. Indeed, several entries exist in the ISGCI database which represent the same graph class, for instance Perfect graphs and Berge graphs:
sage: graph_classes.inclusion_digraph().is_directed_acyclic()
False
sage: Berge = graph_classes.get_class("gc_274"); Berge
Berge graphs
sage: Perfect = graph_classes.get_class("gc_56"); Perfect
perfect graphs
sage: Berge <= Perfect
True
sage: Perfect <= Berge
True
sage: Perfect == Berge
True
The database is loaded not so large, but it is still preferable to only load it on demand. This is achieved through the cached methods classes() and inclusion_digraph().
Upon the first access to the database, the information is extracted from the XML file and stored in the cache of three methods:
Note that the digraph is only built if necessary (for instance if the user tries to compare two classes).
Todo
Technical things:
Long-term stuff:
Bases: sage.structure.sage_object.SageObject, sage.structure.unique_representation.CachedRepresentation
An instance of this class represents a Graph Class, matching some entry in the ISGCI database.
EXAMPLE:
Testing the inclusion of two classes:
sage: Chordal = graph_classes.Chordal
sage: Trees = graph_classes.Tree
sage: Trees <= Chordal
True
sage: Chordal <= Trees
Unknown
TEST:
sage: Trees >= Chordal
Unknown
sage: Chordal >= Trees
True
Prints the information of ISGCI about the current class.
EXAMPLE:
sage: graph_classes.Chordal.description()
Class of graphs : Chordal
-------------------------
type : base
id : gc_32
name : chordal
Problems :
-----------
3-Colourability : Linear
Clique : Polynomial
Clique cover : Polynomial
Cliquewidth : Unbounded
Cliquewidth expression : NP-complete
Colourability : Linear
Cutwidth : NP-complete
Domination : NP-complete
Feedback vertex set : Polynomial
Hamiltonian cycle : NP-complete
Hamiltonian path : NP-complete
Independent set : Linear
Maximum bisection : Unknown
Maximum cut : NP-complete
Minimum bisection : Unknown
Recognition : Linear
Treewidth : Polynomial
Weighted clique : Polynomial
Weighted feedback vertex set : Unknown
Weighted independent set : Linear
Returns the list of forbidden induced subgraphs defining the class.
If the graph class is not defined by a finite list of forbidden induced subgraphs, None is returned instead.
EXAMPLES:
sage: graph_classes.Perfect.forbidden_subgraphs()
sage: gc = graph_classes.get_class('gc_62')
sage: gc
claw--free graphs
sage: gc.forbidden_subgraphs()
[Graph on 4 vertices]
sage: gc.forbidden_subgraphs()[0].is_isomorphic(graphs.ClawGraph())
True
Bases: sage.structure.unique_representation.UniqueRepresentation
x.__init__(...) initializes x; see help(type(x)) for signature
Returns the graph classes, as a dictionary.
Upon the first call, this loads the database from the local XML file. Subsequent calls are cached.
EXAMPLES:
sage: t = graph_classes.classes()
sage: type(t)
<type 'dict'>
sage: sorted(t["gc_151"].keys())
['id', 'name', 'problem', 'type']
sage: t["gc_151"]['name']
'cograph'
sage: t["gc_151"]['problem']['Clique']
{'complexity': 'Linear'}
Returns the class corresponding to the given id in the ISGCI database.
INPUT:
EXAMPLE:
With an existing id:
sage: Cographs = graph_classes.get_class("gc_151")
sage: Cographs
cograph graphs
With a wrong id:
sage: graph_classes.get_class(-1)
Traceback (most recent call last):
...
ValueError: The given class id does not exist in the ISGCI database. Is the db too old ? You can update it with graph_classes.update_db().
Returns the class inclusion digraph
Upon the first call, this loads the database from the local XML file. Subsequent calls are cached.
EXAMPLES:
sage: g = graph_classes.inclusion_digraph(); g
Digraph on ... vertices
Returns the graph class inclusions
OUTPUT:
a list of dictionaries
Upon the first call, this loads the database from the local XML file. Subsequent calls are cached.
EXAMPLES:
sage: t = graph_classes.inclusions()
sage: type(t)
<type 'list'>
sage: t[0]
{'sub': 'gc_1', 'super': 'gc_2'}
Prints all graph classes stored in ISGCI
EXAMPLE:
sage: graph_classes.show_all()
id | name | type | smallgraph
----------------------------------------------------------------------------------------------------------------------
gc_309 | $K_4$--minor--free | base |
gc_541 | $N^*$ | base |
gc_215 | $N^*$--perfect | base |
gc_5 | $P_4$--bipartite | base |
gc_3 | $P_4$--brittle | base |
gc_6 | $P_4$--comparability | base |
gc_7 | $P_4$--extendible | base |
...
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.smallgraphs()
sage: t
{'2C_4': Graph on 8 vertices,
'2K_2': Graph on 4 vertices,
'2K_3': Graph on 6 vertices,
'2K_3 + e': Graph on 6 vertices,
'2K_4': Graph on 8 vertices,
'2P_3': Graph on 6 vertices,
...
sage: t['fish']
Graph on 6 vertices
Updates the ISGCI database by downloading the latest version from internet.
This method downloads the ISGCI database from the website GraphClasses.org. It then extracts the zip file and parses its XML content.
Depending on the credentials of the user running Sage when this command is run, one attempt is made at saving the result in Sage’s directory so that all users can benefit from it. If the credentials are not sufficient, the XML file are saved instead in the user’s directory (in the SAGE_DB folder).
EXAMPLE:
sage: graph_classes.update_db() # Not tested -- requires internet