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.
Jonathan Zingale 