ISGCI: Information System on Graph Classes and their Inclusions¶

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.

Predefined classes¶

graph_classes currently predefines the following graph classes

Class	Related methods
Apex	`is_apex()`, `apex_vertices()`
AT_free	`is_asteroidal_triple_free()`
Biconnected	`is_biconnected()`, `blocks_and_cut_vertices()`, `blocks_and_cuts_tree()`
BinaryTrees	`BalancedTree()`, `is_tree()`
Bipartite	`BalancedTree()`, `is_bipartite()`
Block	`is_block_graph()`, `blocks_and_cut_vertices()`, `RandomBlockGraph()`
Chordal	`is_chordal()`
Claw-Free	`ClawGraph()`
Comparability
Gallai	`is_gallai_tree()`
Grid	`Grid2dGraph()`, `GridGraph()`
Interval	`RandomIntervalGraph()`, `IntervalGraph()`, `is_interval()`
Line	`line_graph_forbidden_subgraphs()`, `is_line_graph()`
Modular	`modular_decomposition()`
Outerplanar	`is_circular_planar()`
Perfect	`is_perfect()`
Planar	`is_planar()`
Polyhedral	`is_polyhedral()`
Split	`is_split()`
Tree	`trees()`, `is_tree()`
UnitDisk	`IntervalGraph()`
UnitInterval	`is_interval()`

Information for developers¶

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:
- sage.graphs.isgci._classes (dictionary)
- sage.graphs.isgci._inclusions (list of dictionaries)
- sage.graphs.isgci._inclusion_digraph (DiGraph)
Note that the digraph is only built if necessary (for instance if the user tries to compare two classes).

Todo

Technical things:

Query the database for non-inclusion results so that comparisons can return False, and implement strict inclusions.
Implement a proper search method for the classes not listed in graph_classes

See also

sage.graphs.isgci.show_all().
Some of the graph classes appearing in graph_classes already have a recognition algorithm implemented in Sage. It would be so nice to be able to write g in Trees, g in Perfect, g in Chordal, … :-)

Long-term stuff:

Implement simple accessors for all the information in the ISGCI database (as can be done from the website)
Implement intersection of graph classes
Write generic recognition algorithms for specific classes (when a graph class is defined by the exclusion of subgraphs, one can write a generic algorithm checking the existence of each of the graphs, and this method already exists in Sage).
Improve the performance of Sage’s graph library by letting it take advantage of the properties of graph classes. For example, Graph.independent_set() could use the library to detect that a given graph is, say, a tree or a planar graph, and use a specialized algorithm for finding an independent set.

AUTHORS:¶

H.N. de Ridder et al. (ISGCI database)
Nathann Cohen (Sage implementation)

Methods¶

class sage.graphs.isgci.GraphClass(name, gc_id, recognition_function=None)[source]¶

Bases: SageObject, CachedRepresentation

An instance of this class represents a Graph Class, matching some entry in the ISGCI database.

EXAMPLES:

Testing the inclusion of two classes:

Sage

sage: Chordal = graph_classes.Chordal
sage: Trees = graph_classes.Tree
sage: Trees <= Chordal
True
sage: Chordal <= Trees
Unknown

Python

>>> from sage.all import *
>>> Chordal = graph_classes.Chordal
>>> Trees = graph_classes.Tree
>>> Trees <= Chordal
True
>>> Chordal <= Trees
Unknown

description()[source]¶

Print the information of ISGCI about the current class.

EXAMPLES:

Sage

sage: graph_classes.Chordal.description()
Class of graphs : Chordal
-------------------------
id                             :  gc_32
name                           :  chordal
...
Problems :
-----------
3-Colourability                :  Linear
Clique                         :  Polynomial
Clique cover                   :  Polynomial
...
Recognition                    :  Linear
...

Python

>>> from sage.all import *
>>> graph_classes.Chordal.description()
Class of graphs : Chordal
-------------------------
id                             :  gc_32
name                           :  chordal
...
Problems :
-----------
3-Colourability                :  Linear
Clique                         :  Polynomial
Clique cover                   :  Polynomial
...
Recognition                    :  Linear
...

forbidden_subgraphs()[source]¶

Return 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

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

Python

>>> from sage.all import *
>>> graph_classes.Perfect.forbidden_subgraphs()
>>> gc = graph_classes.get_class('gc_62')
>>> gc
claw--free graphs
>>> gc.forbidden_subgraphs()
[Graph on 4 vertices]
>>> gc.forbidden_subgraphs()[Integer(0)].is_isomorphic(graphs.ClawGraph())
True

class sage.graphs.isgci.GraphClasses[source]¶

Bases: UniqueRepresentation

classes()[source]¶

Return 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

sage: t = graph_classes.classes()
sage: type(t)
<... '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'}

Python

>>> from sage.all import *
>>> t = graph_classes.classes()
>>> type(t)
<... 'dict'>
>>> sorted(t["gc_151"].keys())
['id', 'name',... 'problem',... 'type']
>>> t["gc_151"]['name']
'cograph'
>>> t["gc_151"]['problem']['Clique']
{'complexity': 'Linear'}

get_class(id)[source]¶

Return the class corresponding to the given id in the ISGCI database.

INPUT:

id – string; the desired class’ ID

See also

show_all()

EXAMPLES:

With an existing id:

Sage

sage: Cographs = graph_classes.get_class("gc_151")
sage: Cographs
cograph graphs

Python

>>> from sage.all import *
>>> Cographs = graph_classes.get_class("gc_151")
>>> Cographs
cograph graphs

With a wrong id:

Sage

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().

Python

>>> from sage.all import *
>>> graph_classes.get_class(-Integer(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().

inclusion_digraph()[source]¶

Return the class inclusion digraph.

Upon the first call, this loads the database from the local XML file. Subsequent calls are cached.

EXAMPLES:

Sage

sage: g = graph_classes.inclusion_digraph(); g
Digraph on ... vertices

Python

>>> from sage.all import *
>>> g = graph_classes.inclusion_digraph(); g
Digraph on ... vertices

inclusions()[source]¶

Return the graph class inclusions.

OUTPUT: list of dictionaries

Upon the first call, this loads the database from the local XML file. Subsequent calls are cached.

EXAMPLES:

Sage

sage: t = graph_classes.inclusions()
sage: type(t)
<... 'list'>
sage: t[0]
{'sub': 'gc_1', 'super': 'gc_2'}

Python

>>> from sage.all import *
>>> t = graph_classes.inclusions()
>>> type(t)
<... 'list'>
>>> t[Integer(0)]
{'sub': 'gc_1', 'super': 'gc_2'}

show_all()[source]¶

Print all graph classes stored in ISGCI.

EXAMPLES:

Sage

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                 |
...

Python

>>> from sage.all import *
>>> 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                 |
...

smallgraphs()[source]¶

Return 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

sage: t = graph_classes.smallgraphs()
sage: t['2C_4']
Graph on 8 vertices
sage: t['2K_3 + e']
Graph on 6 vertices
sage: t['fish']
Graph on 6 vertices
sage: t['bull']
Graph on 5 vertices

Python

>>> from sage.all import *
>>> t = graph_classes.smallgraphs()
>>> t['2C_4']
Graph on 8 vertices
>>> t['2K_3 + e']
Graph on 6 vertices
>>> t['fish']
Graph on 6 vertices
>>> t['bull']
Graph on 5 vertices

update_db()[source]¶

Update 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).

EXAMPLES:

Sage

sage: graph_classes.update_db()  # optional - internet
Database downloaded

Python

>>> from sage.all import *
>>> graph_classes.update_db()  # optional - internet
Database downloaded

ISGCI: Information System on Graph Classes and their Inclusions¶

How to use it?¶

Inclusions¶

Descriptions¶

Recognition of graphs¶

Predefined classes¶

Sage’s view of ISGCI¶

Information for developers¶

AUTHORS:¶

Methods¶