API Reference#

Graph#

class pybliss.Graph(*args, **kwargs)#

Vertex-colored graph. The vertices are labeled using unsigned integers in the set \(\{0, 1, \ldots, N-1\}\), where \(N\) is the number of the vertices in the graph.

__init__(self) → None#
__init__(self, arg: int, /) → None
set_verbose_level(self, level: int) → None#

Set the verbose output level for the algorithms :arg level: The level of verbose output, 0 means no verbose output.

set_verbose_file(self, fp: object) → None#

Set the file stream for verbose output.

Parameters:

file_obj – The file object to write the output to. If None, writing to the file is disabled.

add_vertex(self, color: int = 0) → int#

Add a new vertex with color color and return its new index.

add_edge(self, v1: int, v2: int) → None#

Add an edge between v1 and v2.

get_color(self, v: int) → int#

Returns the color of the vertex v

change_color(self, v: int, c: int) → None#

Change the color of vertex v to c.

set_failure_recording(self, active: bool) → None#

Activate / deactivate failure recording

:arg active:If true, activate failure recording, deactivate otherwise.

set_component_recursion(self, active: bool) → None#

Activate/deactivate component recursion. The choice affects the computed canonical labelings; therefore, if you want to compare whether two graphs are isomorphic by computing and comparing (for equality) their canonical versions, be sure to use the same choice for both graphs. May not be called during the search, i.e. from an automorphism reporting hook function.

Parameters:

active – If true, activate component recursion, deactivate otherwise.

nvertices#

Return the number of vertices in the graph.

permute(self, perm: ndarray[dtype=uint32, shape=(*)]) → pybliss.pybliss_ext.Graph#

Return a new graph that is the result of applying the permutation perm to this graph. This graph is not modified. perm must contain N=this.get_nof_vertices() elements and be a bijection on {0,1,…,N-1}, otherwise the result is undefined.

is_automorphism(self, perm: ndarray[dtype=uint32, shape=(*)]) → bool#

Return true only if perm is an automorphism of this graph. perm must contain N=this.get_nof_vertices() elements and be a bijection on {0,1,…,N-1}, otherwise the result is undefined.

find_automorphisms(self, stats: pybliss.pybliss_ext.Stats, report: collections.abc.Callable[[int, numpy.ndarray[dtype=uint32, shape=(*), order='C', writable=False]], None] | None = None, terminate: collections.abc.Callable[[], bool] | None = None) → None#

Find a set of generators for the automorphism group of the graph. The function report (if not None) is called each time a new generator for the automorphism group is found. The first argument n for the function is the length of the automorphism (equal to get_nof_vertices()), and the second argument aut is the automorphism (a bijection on {0,…,nvertices-1}). aut is a read-only numpy.ndarray. Additionally aut’s entries are invalidated across calls to terminate. Caller must copy aut if long-term usage is intended. Do not call any member functions from the report function.

The search statistics are copied in stats.

If the terminate function argument is given, it is called in each search tree node: if the function returns true, then the search is terminated and thus not all the automorphisms may have been generated. The terminate function may be used to limit the time spent in bliss in case the graph is too difficult under the available time constraints. If used, keep the function simple to evaluate so that it does not consume too much time.

get_permutation_to_canonical_form(self, stats: pybliss.pybliss_ext.Stats, report: collections.abc.Callable[[int, numpy.ndarray[dtype=uint32, shape=(*), order='C', writable=False]], None] | None = None, terminate: collections.abc.Callable[[], bool] | None = None) → object#

Returns P, a numpy.ndarray on {0, …, nvertices-1}. Applying the ‘permutation P to this graph results in this graph’s canonical graph. The function report (if not None) is called each time a new generator for the automorphism group is found. The first argument n for the function is the length of the automorphism (equal to get_nof_vertices()), and the second argument aut is the automorphism (a bijection on {0,…,nvertices-1}). aut is a read-only numpy.ndarray. Additionally aut’s entries are invalidated across calls to terminate. Caller must copy aut if long-term usage is intended. Do not call any member functions from the report function.

The search statistics are copied in stats.

If the terminate function argument is given, it is called in each search tree node: if the function returns true, then the search is terminated and thus not all the automorphisms may have been generated. The terminate function may be used to limit the time spent in bliss in case the graph is too difficult under the available time constraints. If used, keep the function simple to evaluate so that it does not consume too much time.

This wraps the method canonical_form from the C++-API.

write_dimacs(self, fp: object) → None#

Write the graph to fp in a variant of the DIMACS format. See the bliss website <https://users.aalto.fi/tjunttil/bliss> for the definition of the file format. Note that in the DIMACS file the vertices are numbered from 1 to N while in this API they are from 0 to N-1. Thus the vertex n in the file corresponds to the vertex n-1 in the API.

Parameters:

fp – The file stream where the graph is to be written.

to_dimacs(self) → str#

Returns a str corresponding to DIMACS format of the graph.

write_dot(self, fp: object) → None#

Write the graph to fp in the graphviz format.

Parameters:

fp – The file stream where the graph is to be written.

to_dot(self) → str#

Returns a str corresponding to graphviz format of the graph.

show_dot(self, output_to: object | None = None) → None#

Visualize the graph.

Parameters:

output_to – Passed on to pytools.graphviz.show_dot() unmodified.

from_dimacs(fp: object) → pybliss.pybliss_ext.Graph#

Return a graph corresponding to DIMACS-formatted graph present in fp. See the bliss website <https://users.aalto.fi/tjunttil/bliss> for the definition of the file format. Note that in the DIMACS file the vertices are numbered from 1 to N while in this API they are from 0 to N-1. Thus the vertex n in the file corresponds to the vertex n-1 in the API.

Parameters:

fp – The file stream from where the graph is to be read.

copy(self) → pybliss.pybliss_ext.Graph#

Returns a copy of this graph.

cmp(self, other: pybliss.pybliss_ext.Graph) → int#

Compare this graph to other in a total order on graphs. Returns 0 if graphs are equal, -1 if this graph is “smaller than” the other, and 1 if this graph is “greater than” other.

__eq__(self, other: pybliss.pybliss_ext.Graph) → bool#

Returns True iff this graph is identical to other. The check is perform in \(O(E)\), where \(E\) is the number of edges in this graph.

set_long_prune_activity(self, active: bool) → None#

Disable/enable the long prune method. The choice affects the computed canonical labelings. Therefore, if you want to compare whether two graphs are isomorphic by computing and comparing (for equality) their canonical versions, be sure to use the same choice for both graphs. May not be called during the search, i.e. from an automorphism reporting hook function. active if true, activate long prune, deactivate otherwise

set_splitting_heuristic(self, shs: pybliss.pybliss_ext.Graph.SplittingHeuristic) → None#

Set the splitting heuristic used by the automorphism and canonical labeling algorithm. The selected splitting heuristics affects the computed canonical labelings. Therefore, if you want to compare whether two graphs are isomorphic by computing and comparing (for equality) their canonical versions, be sure to use the same splitting heuristics for both graphs.

Note

  • Graph represents an undirected graph, while,

  • Digraph represents a directed graph.

class pybliss.Graph.SplittingHeuristic(*values)#

Enum defining the splitting heuristics for graph canonicalization.

shs_f#

First non-unit cell. Very fast but may result in large search spaces on difficult graphs. Use for large but easy graphs.

shs_fs#

First smallest non-unit cell. Fast, should usually produce smaller search spaces than shs_f.

shs_fl#

First largest non-unit cell. Fast, should usually produce smaller search spaces than shs_f.

shs_fm#

First maximally non-trivially connected non-unit cell. Not so fast, should usually produce smaller search spaces than shs_f, shs_fs, and shs_fl.

shs_fsm#

First smallest maximally non-trivially connected non-unit cell. Not so fast, should usually produce smaller search spaces than shs_f, shs_fs, and shs_fl.

shs_flm#

First largest maximally non-trivially connected non-unit cell. Not so fast, should usually produce smaller search spaces than shs_f, shs_fs, and shs_fl.

Digraph#

class pybliss.Digraph(*args, **kwargs)#

Vertex-colored graph. The vertices are labeled using unsigned integers in the set \(\{0, 1, \ldots, N-1\}\), where \(N\) is the number of the vertices in the graph.

__init__(self) → None#
__init__(self, arg: int, /) → None
set_verbose_level(self, level: int) → None#

Set the verbose output level for the algorithms :arg level: The level of verbose output, 0 means no verbose output.

set_verbose_file(self, fp: object) → None#

Set the file stream for verbose output.

Parameters:

file_obj – The file object to write the output to. If None, writing to the file is disabled.

add_vertex(self, color: int = 0) → int#

Add a new vertex with color color and return its new index.

add_edge(self, source: int, target: int) → None#

Add an edge from source to target.

get_color(self, v: int) → int#

Returns the color of the vertex v

change_color(self, v: int, c: int) → None#

Change the color of vertex v to c.

set_failure_recording(self, active: bool) → None#

Activate / deactivate failure recording

:arg active:If true, activate failure recording, deactivate otherwise.

set_component_recursion(self, active: bool) → None#

Activate/deactivate component recursion. The choice affects the computed canonical labelings; therefore, if you want to compare whether two graphs are isomorphic by computing and comparing (for equality) their canonical versions, be sure to use the same choice for both graphs. May not be called during the search, i.e. from an automorphism reporting hook function.

Parameters:

active – If true, activate component recursion, deactivate otherwise.

nvertices#

Return the number of vertices in the graph.

permute(self, perm: ndarray[dtype=uint32, shape=(*)]) → pybliss.pybliss_ext.Digraph#

Return a new graph that is the result of applying the permutation perm to this graph. This graph is not modified. perm must contain N=this.get_nof_vertices() elements and be a bijection on {0,1,…,N-1}, otherwise the result is undefined.

is_automorphism(self, perm: ndarray[dtype=uint32, shape=(*)]) → bool#

Return true only if perm is an automorphism of this graph. perm must contain N=this.get_nof_vertices() elements and be a bijection on {0,1,…,N-1}, otherwise the result is undefined.

find_automorphisms(self, stats: pybliss.pybliss_ext.Stats, report: collections.abc.Callable[[int, numpy.ndarray[dtype=uint32, shape=(*), order='C', writable=False]], None] | None = None, terminate: collections.abc.Callable[[], bool] | None = None) → None#

Find a set of generators for the automorphism group of the graph. The function report (if not None) is called each time a new generator for the automorphism group is found. The first argument n for the function is the length of the automorphism (equal to get_nof_vertices()), and the second argument aut is the automorphism (a bijection on {0,…,nvertices-1}). aut is a read-only numpy.ndarray. Additionally aut’s entries are invalidated across calls to terminate. Caller must copy aut if long-term usage is intended. Do not call any member functions from the report function.

The search statistics are copied in stats.

If the terminate function argument is given, it is called in each search tree node: if the function returns true, then the search is terminated and thus not all the automorphisms may have been generated. The terminate function may be used to limit the time spent in bliss in case the graph is too difficult under the available time constraints. If used, keep the function simple to evaluate so that it does not consume too much time.

get_permutation_to_canonical_form(self, stats: pybliss.pybliss_ext.Stats, report: collections.abc.Callable[[int, numpy.ndarray[dtype=uint32, shape=(*), order='C', writable=False]], None] | None = None, terminate: collections.abc.Callable[[], bool] | None = None) → object#

Returns P, a numpy.ndarray on {0, …, nvertices-1}. Applying the ‘permutation P to this graph results in this graph’s canonical graph. The function report (if not None) is called each time a new generator for the automorphism group is found. The first argument n for the function is the length of the automorphism (equal to get_nof_vertices()), and the second argument aut is the automorphism (a bijection on {0,…,nvertices-1}). aut is a read-only numpy.ndarray. Additionally aut’s entries are invalidated across calls to terminate. Caller must copy aut if long-term usage is intended. Do not call any member functions from the report function.

The search statistics are copied in stats.

If the terminate function argument is given, it is called in each search tree node: if the function returns true, then the search is terminated and thus not all the automorphisms may have been generated. The terminate function may be used to limit the time spent in bliss in case the graph is too difficult under the available time constraints. If used, keep the function simple to evaluate so that it does not consume too much time.

This wraps the method canonical_form from the C++-API.

write_dimacs(self, fp: object) → None#

Write the graph to fp in a variant of the DIMACS format. See the bliss website <https://users.aalto.fi/tjunttil/bliss> for the definition of the file format. Note that in the DIMACS file the vertices are numbered from 1 to N while in this API they are from 0 to N-1. Thus the vertex n in the file corresponds to the vertex n-1 in the API.

Parameters:

fp – The file stream where the graph is to be written.

to_dimacs(self) → str#

Returns a str corresponding to DIMACS format of the graph.

write_dot(self, fp: object) → None#

Write the graph to fp in the graphviz format.

Parameters:

fp – The file stream where the graph is to be written.

to_dot(self) → str#

Returns a str corresponding to graphviz format of the graph.

show_dot(self, output_to: object | None = None) → None#

Visualize the graph.

Parameters:

output_to – Passed on to pytools.graphviz.show_dot() unmodified.

from_dimacs(fp: object) → pybliss.pybliss_ext.Digraph#

Return a graph corresponding to DIMACS-formatted graph present in fp. See the bliss website <https://users.aalto.fi/tjunttil/bliss> for the definition of the file format. Note that in the DIMACS file the vertices are numbered from 1 to N while in this API they are from 0 to N-1. Thus the vertex n in the file corresponds to the vertex n-1 in the API.

Parameters:

fp – The file stream from where the graph is to be read.

copy(self) → pybliss.pybliss_ext.Digraph#

Returns a copy of this graph.

cmp(self, other: pybliss.pybliss_ext.Digraph) → int#

Compare this graph to other in a total order on graphs. Returns 0 if graphs are equal, -1 if this graph is “smaller than” the other, and 1 if this graph is “greater than” other.

__eq__(self, other: pybliss.pybliss_ext.Digraph) → bool#

Returns True iff this graph is identical to other. The check is perform in \(O(E)\), where \(E\) is the number of edges in this graph.

set_long_prune_activity(self, active: bool) → None#

Disable/enable the long prune method. The choice affects the computed canonical labelings. Therefore, if you want to compare whether two graphs are isomorphic by computing and comparing (for equality) their canonical versions, be sure to use the same choice for both graphs. May not be called during the search, i.e. from an automorphism reporting hook function. active if true, activate long prune, deactivate otherwise

set_splitting_heuristic(self, shs: pybliss.pybliss_ext.Digraph.SplittingHeuristic) → None#

Set the splitting heuristic used by the automorphism and canonical labeling algorithm. The selected splitting heuristics affects the computed canonical labelings. Therefore, if you want to compare whether two graphs are isomorphic by computing and comparing (for equality) their canonical versions, be sure to use the same splitting heuristics for both graphs.

Note

  • Graph represents an undirected graph, while,

  • Digraph represents a directed graph.

class pybliss.Digraph.SplittingHeuristic(*values)#

Enum defining the splitting heuristics for graph canonicalization.

shs_f#

First non-unit cell. Very fast but may result in large search spaces on difficult graphs. Use for large but easy graphs.

shs_fs#

First smallest non-unit cell. Fast, should usually produce smaller search spaces than shs_f.

shs_fl#

First largest non-unit cell. Fast, should usually produce smaller search spaces than shs_f.

shs_fm#

First maximally non-trivially connected non-unit cell. Not so fast, should usually produce smaller search spaces than shs_f, shs_fs, and shs_fl.

shs_fsm#

First smallest maximally non-trivially connected non-unit cell. Not so fast, should usually produce smaller search spaces than shs_f, shs_fs, and shs_fl.

shs_flm#

First largest maximally non-trivially connected non-unit cell. Not so fast, should usually produce smaller search spaces than shs_f, shs_fs, and shs_fl.

Stats#

class pybliss.Stats(*args, **kwargs)#

Records statistics returned by the search algorithms.

__init__(self) → None#
print_to_file(self, arg: object, /) → None#
group_size#

The size of the automorphism group as int.

group_size_as_bignum#

The size of the automorphism group as BigNum.

group_size_approx#

An approximation (due to possible overflows/rounding errors) of the size of the automorphism group

n_nodes#

Number of nodes in the search tree.

n_leaf_nodes#

Number of leaf nodes in the search tree.

n_bad_nodes#

Number of bad nodes in the search tree.

n_canupdates#

Number of canonical representative nodes.

n_generators#

Number of generator permutations.

max_level#

The maximal depth of the search tree.

__str__(self) → str#

BigNum#

class pybliss.BigNum(*args, **kwargs)#

A wrapper class for non-negative big integers.

__init__(self) → None#
assign(self, arg: int, /) → None#
multiply(self, arg: int, /) → None#
print_to_file(self, arg: object, /) → None#
__str__(self) → str#

Utilities#

pybliss.utils.graph_from_numpy(N: int, E: ndarray[tuple[int, int], dtype[integer]], c: ndarray[tuple[int], dtype[integer]]) → Graph[source]#

Returns a pybliss.Graph, G, with N-vertices, E-edges and colored vector c.

Parameters:

  • N – The number of vertices in the graph, G.

  • E – A 2D numpy.ndarray of shape \(N_{\mathrm{edges}} \times 2\), where \(N_{\mathrm{edges}}\) is the number of edges in G. Each row in E is the of the form [i, j] to denote that there is an edge between i and j in G. Note that \(i, j \in \{0, 1, \ldots, N - 1\}\).

  • c – An N-long column vector such that c[i] corresponds to the color of i-th vertex in G.

pybliss.utils.digraph_from_numpy(N: int, E: ndarray[tuple[int, int], dtype[integer]], c: ndarray[tuple[int], dtype[integer]]) → Digraph[source]#

Returns a pybliss.Digraph, G, with N-vertices, E-edges and colored vector c.

Parameters:

  • N – The number of vertices in the graph, G.

  • E – A 2D numpy.ndarray of shape \(N_{\mathrm{edges}} \times 2\), where \(N_{\mathrm{edges}}\) is the number of edges in G. Each row in E is the of the form [i, j] to denote that there is an edge from i to j in G. Note that \(i, j \in \{0, 1, \ldots, N - 1\}\).

  • c – An N-long column vector such that c[i] corresponds to the color of i-th vertex in G.

pybliss.utils.graph_to_numpy(G: Graph) → tuple[ndarray[tuple[int, int], dtype[integer]], ndarray[tuple[int], dtype[integer]]][source]#

Returns a tuple (E, c) for an undirected graph G, where:

  • E is a 2D numpy.ndarray of shape \(N_{\mathrm{edges}} \times 2\), where \(N_{\mathrm{edges}}\) is the number of edges in G. Each row of E has the form [i, j], indicating that there is an edge between vertex i and vertex j in G. Note that \(i, j \in \{0, 1, \ldots, N - 1\}\).

  • c is a 1D numpy.ndarray of length \(N\) such that c[i] corresponds to the color of the i-th vertex in G.

pybliss.utils.digraph_to_numpy(G: Digraph) → tuple[ndarray[tuple[int, int], dtype[integer]], ndarray[tuple[int], dtype[integer]]][source]#

Returns a tuple (E, c) for an undirected graph G, where:

  • E is a 2D numpy.ndarray of shape \(N_{\mathrm{edges}} \times 2\), where \(N_{\mathrm{edges}}\) is the number of edges in G. Each row of E has the form [i, j], indicating that there is an edge from vertex i to vertex j in G. Note that \(i, j \in \{0, 1, \ldots, N - 1\}\).

  • c is a 1D numpy.ndarray of length \(N\) such that c[i] corresponds to the color of the i-th vertex in G.

Indices and tables#