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 VertexEdge 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
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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s