bliss.RawGraph

class bliss.RawGraph(n=0)

Python object interface to “raw” bliss graphs. In such a graph of n vertices, the vertices are identified by integers from 0 to n-1. The vertices can be colored with non-negative integers. Vertices and edges can only be added, not removed.

__eq__(other)

Returns

True if “this == other” in a total order on graphs.

__ge__(other)

Returns

True if “this >= other” in a total order on graphs.

__gt__(other)

Returns

True if “this > other” in a total order on graphs.

__hash__()

Returns

the hash value for the current graph.

__init__(n=0)

Create a new graph of n vertices and no edges. The vertices are numbered from 0 to n-1.

Parameters

n – the number of vertices.

Returns

an empty graph with n vertices and no edges.

__le__(other)

Returns

True if “this <= other” in a total order on graphs.

__lt__(other)

Returns

True if “this < other” in a total order on graphs.

__ne__(other)

Returns

True if “this != other” in a total order on graphs.

__weakref__

list of weak references to the object (if defined)

add_edge(v1, v2)

Add an edge between vertices.

Parameters

• v1 – a vertex.

• v2 – a vertex.

add_vertex(color=0)

Add a new vertex in the graph.

Parameters

color – the color of the new vertex.

Returns

the number of the new vertex.

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.

change_color(vertex, color)

Set the color of a vertex.

Parameters

• vertex – the vertex whose color is changed

• color – the new color of the vertex (an integer in range 0…2^32-1).

copy()

Returns

a copy of the graph.

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.

is_automorphism(perm)

Check whether a permutation is an automorphism of the graph.

Parameters

perm – a permutation of [0..n-1]

Returns

True is perm is an automorphism of the graph.

nof_vertices()

Returns

the number of the vertices in the graph.

permute(perm)

Permute the graph.

Parameters

perm – a permutation of [0..n-1]

Returns

the permuted graph

classmethod read_dimacs(filename)

Read the graph in the DIMACS format.

Parameters

filename – the input file name.

Returns

the graph described in the input file.

write_dimacs(filename)

Write the graph in the DIMACS format.

Parameters

filename – the name of the output file.

write_dot(filename)

Write the graph in the Graphviz DOT format.

Parameters

filename – the name of the output file.