bliss
A colored graph is a triple G=(V,E,c) where V={1,2,...,N} is a finite set of vertices, E is a set of 2-element subsets of V called edges, and c:V→N is a function that associates to each vertex a nonnegative integer (a color). For example, identifying blue with 0 and green with 1, the graphs in Figure 1 are
G_{1} = ({1,2,3,4}, {{1,2},{1,3},{1,4},{2,3},{2,4}}, ⟨1→1,2→0,3→0,4→0⟩)
andG_{2} = ({1,2,3,4}, {{1,2},{1,4},{2,3},{2,4},{3,4}}, ⟨1→0,2→1,3→0,4→0⟩).
Let γ:V→V be a permutation of V. Denote by v^{γ} the image of v∈V under γ. For a colored graph G=(V,E,c), define the colored graphG^{γ} = (V, {{v^{γ},w^{γ}} | {v,w}∈E}, c^{γ}),
where c^{γ}:V→N is defined for all v∈V by c^{γ}(v^{γ})=c(v).Two colored graphs, G_{1}=(V,E_{1},c_{1}) and G_{2}=(V,E_{2},c_{2}), are isomorphic if there exists a permutation γ:V→V such that G_{1}^{γ}=G_{2}. Such a permutation γ is called an isomorphism of G_{1} onto G_{2}. For example, there are two possible isomorphisms of G_{1} onto G_{2} in Figure 1, namely ⟨1→2,2→4,3→1,4→3⟩ and ⟨1→2,2→4,3→3,4→1⟩. We write G_{1}≅G_{2} to indicate that G_{1} and G_{2} are isomorphic.
An automorphism of a colored graph is an isomorphism of the colored graph onto itself. The set of all automorphisms of a colored graph G forms a permutation group where the group operation is the functional composition of permutations. This permutation group is called the automorphism group of G and is denoted by Aut(G). A set of generators for Aut(G) is a set S⊆Aut(G) such that every non-identity permutation in Aut(G) can be obtained by composing elements of S. For example, {⟨1→1,2→2,3→4,4→3⟩} is a set of generators for
Aut(G_{1})={⟨1→1,2→2,3→3,4→4⟩,⟨1→1,2→2,3→4,4→3⟩}
in Figure 1.A function ρ from colored graphs to colored graphs is a canonical representative map if the following two conditions hold:
({1,2,3,4}, {(1,2),(1,3),(1,4),(2,3),(2,4)}, ⟨1→1,2→0,3→0,4→0⟩)
Given a permutation γ:V→V of V and a directed colored graph G=(V,E,c), define the directed colored graphG^{γ}=(V, {(v^{γ},w^{γ}) | (v,w)∈E}, c^{γ}),
where c^{γ}:V→N is defined for all v∈V by c^{γ}(v^{γ})=c(v). The definitions of automorhism, isomorphism, generator sets, and canonical labelings for directed colored graphs are the same as for undirected colored graphs.The source code documentation of bliss 0.73, produced by running doxygen in the source code directory, is perhaps the best place to browse the bliss C++ and C APIs.
The algorithms and data structures used in bliss are described in
Please refer to this paper when documenting work that uses bliss; you can use this bibtex entry.
The older version of bliss as well as the graphs used in the experiments of this paper are available here.
jbliss is a Java language wrapper for bliss. It allows fast prototyping of, for instance, search algorithms applying isomorph rejection. It is much more convenient to use than the C++ interface but it not well-suited for extremely performance critical software.
PyBliss is a Python language wrapper for bliss. It allows fast prototyping of, for instance, search algorithms applying isomorph rejection. It is much more convenient to use than the C++ interface but it not well-suited for performance critical software.
Some small utilities, including translators between graph formats.