| Copyright | (c) Jean-Philippe Bernardy 2003 2008 |
|---|---|
| License | GPL |
| Maintainer | JeanPhilippe.Bernardy@gmail.com |
| Stability | proposal |
| Portability | GHC |
| Safe Haskell | Safe |
| Language | Haskell98 |
Data.Graph.Automorphism
Description
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 -> Graph
- canonicGraph0 :: Partition -> Graph -> Graph
- autGenerators :: Partition -> Graph -> [Permutation]
- automorphisms :: Partition -> Graph -> ([Permutation], Graph)
- isIsomorphic :: Graph -> Graph -> Bool
- debugTree :: Partition -> Graph -> IO ()
- withUnitPartition :: (Partition -> Array Vertex e -> t) -> Array Vertex e -> t
Documentation
canonicGraph :: Partition -> Graph -> Graph #
Return the canonic version of a graph.
canonicGraph0 :: Partition -> Graph -> Graph #
Returns a canonic labeling of the graph (slow -- but dead simple implementation). This implementation serves documentation and debugging purposes.
autGenerators :: Partition -> Graph -> [Permutation] #
Returns generators of the automorphism group
automorphisms :: Partition -> Graph -> ([Permutation], Graph) #
Given a graph, return generators of its automorphism group, and its canonic labeling
isIsomorphic :: Graph -> Graph -> Bool #
Tells whether two graphs are isomorphic