# Havel-Hakimi Graphs

### Graph: a library for Havel Hakimi Tournaments

The `Graph` module offers data structures and methods for working with
direct graphs in Haskell. The library is then extended to working examples
of the Havel-Hakimi algorithm.

```:l ./../Helpers -- mostly for hhsort

data Vertex = V { name::String, degree::Int} deriving Eq
data Edge = E { source::Vertex, target::Vertex } deriving Eq
data Graph = G { edges::[Edge] } | BadGraph deriving (Eq, Show)
type Degrees = [Int]

vertices :: Graph -> [Vertex]
vertices (G es) = let totV = [target, source] <*> es in f totV []
where
f [] acc = acc
f ((V n d):vs) acc | any (\v -> name v == n) acc = f vs acc
| otherwise = f vs ((V n d):acc)

degreesToVerts :: Degrees -> [Vertex]
degreesToVerts ds =  [V (show ss) d | (ss, d) <- zip [1..] ds]

instance Show Vertex where
show (V a b) = a
instance Show Edge where
show (E a b) = show a ++ "->" ++ show b

instance Ord Vertex where
(<=) (V ss n) (V tt m) = n <= m
(>=) (V ss n) (V tt m) = n >= m
```

The above data types `Vertex``Edge` and `Graph` are the heart of Graph module.
Each comes with some default methods for accessing sub-types. Being defined explicitly,
`vertices :: Graph -> [Vertex]` and `degreesToVerts :: Degrees -> [Vertex]`
appear to be the odd methods out. `vertices` returns the vertices for a graph,
while `degreesToVerts` allows us to build a vertex set with expectations for the degree
of each vertex. Next, Some instances of `Show` are a included to keep things pretty.
Lastly, `Ord` is extended to Vertex so that we can sort on them.

Now the work horse functions:

```havelHakimi :: [Int] -> Bool
havelHakimi (a:[]) = a == 0
havelHakimi (a:as) = havelHakimi.hhsort \$
map (subtract 1) (take a as) ++ drop a as

vertsToGraph :: [Vertex] -> Graph
vertsToGraph verts = rebuildDegs.G \$ hh verts []
where
havel ((V ss n):as) =
hhsort \$ snd_map (+ (-1)) (take n as) ++ drop n as
toEdges ((V ss n):as) = [E (V ss n) vert | vert <- take n as]
snd_map f xs = [V a (f b) | (V a b) <- xs]

hh [] edgeAccum = edgeAccum
hh verts edgeAccum =
let sorted = hhsort verts in
hh (havel sorted) (edgeAccum ++ toEdges sorted)

rebuildDegs :: Graph -> Graph
rebuildDegs (G es) = G \$ map (buildE es) es
where
buildV (V n d) tars = V n \$ (length.filter (== n)) tars
buildE es (E v1 v2) =
let totalV = [name.target, name.source] <*> es in
E (buildV v1 totalV) (buildV v2 totalV)

degreesToGraph :: Degrees -> Graph
degreesToGraph degs | havelHakimi degs =
vertsToGraph.degreesToVerts \$ degs
```

`vertsToGraph` relies on some not so obvious methods, `hhsort` and `rebuildDegs`.
The first is a specialized `quicksort` which orders vertices from largest degree
to smallest. The algorithm deincrements on the degrees given for the vertices, and so
`rebuildDeg` is needed to rebuild the degrees of each vertex.
The method `degreesToGraph` checks that a given set of degrees is graphic in the sense of
Erdős–Gallai, via the Havel-Hakimi algorithm. `BadGraph` is returned if the given set
of degrees is not graphic, and returns a realization if the set of degrees is graphic.
For example a list of `n+1` n’s ought to represent an `n-simplex` in our scheme.

```simplex n = degreesToGraph.take (n+1) \$ repeat n
simplex 4
```
`G {edges = [1->2,1->3,1->4,1->5,2->3,2->4,2->5,3->4,3->5,4->5]}`

We then see that a `4-simplex` is in fact graphic.