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


-- | Compute the homology of a chain complex
--   
--   This package currently computes the homology of a chain complex over
--   Z/2Z.
@package Homology
@version 0.1

module HomologyZ2

-- | A list of representatives of homology classes.
type Homology = [Int]

-- | A complex is a vector of triples. Each index represents a generator,
--   $x$, and the triple refers $(dx, d^{-1}x, alive?)$, where $dx$ is the
--   list of generators that $x$ maps to, $d^{-1}x$ is the list of
--   generators $y$ such that $x in dy$, and alive? indicates whether x is
--   still an element of the complex (alive? = true by default).
--   
--   <pre>
--   &gt;&gt;&gt; example1
--   IV.fromList [([], [3], True), ([], [3], True), ([], [], True), ([0, 1, 2], [], True), ([], [3], True)]
--   </pre>
type Complex = Vector ([Int], [Int], Bool)

-- | Compute the homology of a complex by the following method: Represent
--   the complex by a directed graph, where the vertex set is the set of
--   generators, and there is an edge from x to y if $y in dx$. For each
--   $x$ such that $dx neq emptyset$, pick $y in dx$. For each $z in
--   d^{-1}y$, and $w in dx$, if there is an edge from $z$ to $w$, delete
--   it, otherwise create an edge from $z$ to $w$. Finally, delete $x$,
--   $y$, and all edges into and out of $x$ and $y$. Continue iterating
--   this process until there are no edges left, then read off the homology
--   (the list of elements that are still alive in the complex).
--   
--   <pre>
--   &gt;&gt;&gt; homology example1
--   [1,2,4]
--   
--   &gt;&gt;&gt; homology example2
--   [2,3,4,5]
--   </pre>
homology :: Complex -> Homology

-- | An example complex.
--   
--   <pre>
--   &gt;&gt;&gt; example1
--   IV.fromList [([], [3], True), ([], [3], True), ([], [], True), ([0, 1, 2], [], True), ([], [3], True)]
--   </pre>
example1 :: Complex

-- | An example complex.
--   
--   <pre>
--   &gt;&gt;&gt; example2
--   IV.fromList [([1,4],[],True), ([],[5,2,0],True), ([4,1],[],True), ([],[],True), ([],[5,2,0],True), ([1,4],[],True)]
--   </pre>
example2 :: Complex