hgal- library for computation automorphism group and canonical labelling of a graph

Safe HaskellNone



implementation of the canonic labeling of graphs + automorphism group.

The implementation is based on: Brendan D. McKay, PRACTICAL GRAPH ISOMORPHISM, in Congressus Numerantium, Vol. 30 (1981), pp. 45-87.

NOTE: Usage of implicit automorphisms, as described on page 62, is not implemented here.

TODO: - as GHC 6.6, use Sequence instead of appends at end. - skip first automorphism found; it is identity. - try not relabeling the graphs



canonicGraph :: Partition -> Graph -> GraphSource

Return the canonic version of a graph.

canonicGraph0 :: Partition -> Graph -> GraphSource

Returns a canonic labeling of the graph (slow -- but dead simple implementation). This implementation serves documentation and debugging purposes.

autGenerators :: Partition -> Graph -> [Permutation]Source

Returns generators of the automorphism group

automorphisms :: Partition -> Graph -> ([Permutation], Graph)Source

Given a graph, return generators of its automorphism group, and its canonic labeling

isIsomorphic :: Graph -> Graph -> BoolSource

Tells whether two graphs are isomorphic