bliss.ColoredGraph

class bliss.ColoredGraph

An undirected graph with arbitrary vertex names and colors. The vertex names and colors 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++.

__eq__(other)

Test whether the graphs have the same vertices colored with the same colors and the same edges.

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

Create a new empty graph.

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

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

Parameters

• v1 – a vertex name.

• v2 – a vertex name.

add_vertex(v, color)

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 comprable with the other keys.

• color – the color of the vertex.

Returns

False if the vertex already existed, True otherwise.

canonical_form(reporter=None)

Find the canonical form of the graph. Obtained by relabeling 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(v, color)

Change the color of a vertex.

Parameters

• v – the name of the vertex.

• color – the new color for the vertex.

cmp(that)

Compare this graph to that graph in a total order between graphs.

Parameters

that – the graph to be conmpared against.

Returns

-1 if this is “smaller” than “that”, 0 if the graphs are equal, and 1 if this is “greater” than “that”.

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 ‘isom’ is a labeling such that self.relabel(isom) == g.

Returns

An isomorphism or None.

get_vertices()

Returns

the (list of) vertices in the graph.

Return type

list

nof_vertices()

Returns

the number of vertices in the graph.

relabel(lab)

Relabel the graph (that is, rename the vertices).

Parameters

lab – a bijective mapping (dictionary) from the vertex names to the set of new names.

Returns

the relabeled graph

write_dot(file)

Write the graph in the Graphviz DOT format.

Parameters

file – the output file object.