bliss.Graph

class bliss.Graph

An undirected graph with arbitrary vertex names. The vertex names should be hashable and comparable. Vertices and edges can be both added and removed. Written almost fully in Python, only the automorphism group and canonical labeling/form search routines use bliss written in C++.

__cmp__(other)

Ordering of graphs is not defined, will raise an Error.

__eq__(other)

Check whether the graph is equal to the graph ‘other’. That is, whether the graphs have the same vertices colored with the same colors and the same edges.

__ge__(other)

Ordering of graphs is not defined, will raise an Error.

__gt__(other)

Ordering of graphs is not defined, will raise an Error.

__hash__()

Return hash(self).

__init__()

Create a new empty graph.

__le__(other)

Ordering of graphs is not defined, will raise an Error.

__lt__(other)

Ordering of graphs is not defined, will raise an Error.

__ne__(other)

Check whether the graph is not equal to the graph ‘other’.

__str__()

A string representation of the graph. Mainly for debugging.

__weakref__

list of weak references to the object (if defined)

add_edge(v1, v2)

Add an edge between two vertices in the graph. Adds the argument vertices in the graph if they do not already exist.

Parameters

• v1 – a hashable and immutable vertex name.

• v2 – a hashable and immutable vertex name.

add_vertex(v, color=0)

Add a new vertex in the graph. If the vertex already exists, do nothing.

Parameters

• v – the name of the new vertex. It should be hashable and immutable.

• color – the color of the vertex (an integer in 0..2^31-1).

Returns

False if the vertex already existed, True otherwise.

canonical_form(reporter=None)

Find the canonical form of the graph. Obtained by permuting the graph with the canonical labeling produced with canonical_labeling().

Parameters

reporter – if this function argument is given, then reporter(aut) is called for each generator automorphism “aut”.

Returns

the canonical form graph.

canonical_labeling(reporter=None)

Find a canonical labeling for the graph.

Parameters

reporter – if this function argument is given, then reporter(aut) is called for each generator automorphism “aut”.

Returns

a pair consisting of a canonical labeling, and a Stats object with search space statistics and the automorphism group size.

copy()

Returns

a deep copy of this graph.

del_edge(v1, v2)

Delete an edge between two vertices from the graph. If the edge does not exist, do nothing.

Parameters

• v1 – a vertex name.

• v2 – a vertex name.

del_vertex(v)

Delete a vertex from the graph. If the vertex does not exist, do nothing.

Parameters

v – the vertex to be deleted.

find_automorphisms(reporter=None)

Find a generating set for the automorphism group of the graph.

Parameters

reporter – if this function argument is given, then reporter(aut) is called for each generator automorphism “aut”.

Returns

A Stats object with search space statistics and the automorphism group size.

get_isomorphism(g)

Return an isomorphism from this graph to the graph ‘g’, or None is the graphs are not isomorphic. Observe that for empty graphs an empty dictionary is returned and thus one should not check isomorphism by ‘if g1.get_isomorphism(g2)’ but by ‘if g1.get_isomorphism(g2) != None’. The returned isomorphism ‘lab’ is a labeling such that self.relabel(lab).is_equal(g) == True.

get_vertices()

Returns

the (list of) vertices in the graph.

is_equal(g)

Check whether the graph is equal to the graph ‘g’. Returns True if this is the case and False otherwise.

nof_vertices()

Returns

the number of vertices in the graph.

permute(perm)

Permute the graph.

Parameters

perm – a permutation of the vertex set of the graph.

Returns

the permuted graph

write_dot(file)

Write the graph in the Graphviz DOT format.

Parameters

file – the output file object.