-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | library for computation automorphism group and canonical labelling of a graph
--   
--   library for computation automorphism group and canonical labelling of
--   a graph
@package hgal
@version 2.0.0.2


-- | Various functions to build graphs.
module Data.Graph.Construction
hCubeG :: Int -> Graph
cycleG :: Int -> Graph
prismG :: Int -> Graph
productG :: Graph -> Graph -> Graph
linearG :: Int -> Graph
arcG :: Graph
starG :: (Vertex, Vertex) -> Graph
unionG :: Graph -> Graph -> Graph
undirG :: Graph -> Graph
tensorG :: [Int] -> Graph
kG :: Int -> Int -> Graph
cliqueG :: (Vertex, Vertex) -> Graph
emptyG :: Int -> Graph


module Data.Graph.Partition

-- | A cell is represented by its list of vertices, with the invariant that
--   the list is sorted
type Cell = [Vertex]

-- | A partition is its list of cells
type Partition = [Cell]

-- | Refines a Partition wrt to another Partition, given a graph.
--   (explained on pages 50-52) This is equivalent to partition the graph's
--   DFA in equivalent states. <tt>refine gr p q</tt> refines <tt>p</tt>
--   wrt. <tt>q</tt> in <tt>gr</tt>.
refine :: Graph -> Partition -> Partition -> Partition
isSingleton :: [a] -> Bool

-- | The unit partition of a range.
unitPartition :: (Vertex, Vertex) -> Partition

-- | Is the partition discrete ?
isDiscrete :: Partition -> Bool
mcr :: Partition -> [Vertex]
type Indicator = Int32

-- | An indicator function. <tt>lambda</tt> must be insensitive to
--   automorphisms relabeling of the graph for the Automorphism module to
--   work.
lambda :: Graph -> Partition -> Indicator
lambda_ :: Graph -> [Partition] -> [Indicator]

-- | Returns vertices fixes in the given orbits
fixedInOrbits :: Partition -> [Vertex]


-- | This modules manages permutations between nodes of a graph.
--   Permutations are represented as arrays.
module Data.Graph.Permutation

-- | A permutations maps a range of Vertices to itself.
type Permutation = Array Vertex Vertex

-- | Fixed vertices of a given permutation
fixed :: Permutation -> [Vertex]

-- | Builds the permutation taking l1 on l2.
permBetween :: Bounds -> [Vertex] -> [Vertex] -> Permutation

-- | Relabel a graph using a permutation
applyPerm :: Permutation -> Graph -> Graph

-- | Returns the orbits of a permutation, as a partition
orbitsFromPerm :: Permutation -> Partition

-- | Merge the orbits of two permutations
mergePerms :: Permutation -> Permutation -> Permutation


-- | 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
module Data.Graph.Automorphism

-- | Return the canonic version of a graph.
canonicGraph :: Partition -> Graph -> Graph

-- | Returns a canonic labeling of the graph (slow -- but dead simple
--   implementation). This implementation serves documentation and
--   debugging purposes.
canonicGraph0 :: Partition -> Graph -> Graph

-- | Returns generators of the automorphism group
autGenerators :: Partition -> Graph -> [Permutation]

-- | Given a graph, return generators of its automorphism group, and its
--   canonic labeling
automorphisms :: Partition -> Graph -> ([Permutation], Graph)

-- | Tells whether two graphs are isomorphic
isIsomorphic :: Graph -> Graph -> Bool
debugTree :: Partition -> Graph -> IO ()
withUnitPartition :: () => (Partition -> Array Vertex e -> t) -> Array Vertex e -> t
