### 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
| otherwise = BadGraph
```

`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
```

We then see that a `4-simplex`

is in fact graphic.