Undirected Graphs

26th September 2017By DawidData Structures

Data structures capture relationship between the component values such as succession or relative magnitude. Graphs data structure is a very general representation of binary relations recorded as edges between a collection of vertices. There are many variations and extensions of graphs such as labelled vertices, labelled edges, root verities, multi-edges etc. However, in this article we will look at the most 'basic' graphs where component values are identified as vertices.

Let is therefore construct a 'universal' type-class specification for graphs. The type-class should allow us to: construct and modify the graph by adding and deleting vertices and edges.

class GraphSpec g where
  empty    :: g a
  addVert  :: Ord a =&gt; a -&gt; g a -&gt; g a
  addEdge  :: Ord a =&gt; a -&gt; a -&gt; g a -&gt; g a
  delVert  :: Ord a =&gt; a -&gt; g a -&gt; g a
  vertices :: Ord a =&gt; g a -&gt; [a]
  adj      :: Ord a =&gt; a -&gt; g a -&gt; [a]

graph :: (GraphSpec g, Ord a) =&gt; [a] -&gt; [(a,a)] -&gt; g a
graph vs es = foldr (uncurry addEdge) es
  where gvs = foldr addVert empty vs

class GraphSpec g where

empty :: g a

addVert :: Ord a => a -> g a -> g a

addEdge :: Ord a => a -> a -> g a -> g a

delVert :: Ord a => a -> g a -> g a

vertices :: Ord a => g a -> [a]

adj :: Ord a => a -> g a -> [a]

graph :: (GraphSpec g, Ord a) => [a] -> [(a,a)] -> g a

graph vs es = foldr (uncurry addEdge) es

where gvs = foldr addVert empty vs

The class polymorphic graph function combines additions to form graphs from lists? How? That's simple. The uncurry takes a function (a -> b -> c) -> (a, b) -> c.

List Representation

Just like with other data types we have talked in this series, let's begin by seeing how graphs can be represented as list. Mathematically, a graph is a set of vertices V and a set of edges E. Edges are represented as an unordered pairs (V, V). Let us there define the data type VEListsGraph which will have a list of those same properties:

data VEListsGraph a = VE [a] [(a,a)]

1	data VEListsGraph a = VE [a] [(a,a)]

The first list is the V set and the pair represents the edges. At this point, it is worth imposing some invariants on this data structure so that when e.g. vertex is deleted, we do not have edges leading to or from it:

(v1, v2) `elem` es ==> v1 `elem` vs && v2 `elem` vs

1

(v1, v2) `elem` es ==> v1 `elem` vs && v2 `elem` vs

This reads: for all edges (v1,v2), both v1 and v2 must be members of vertex set
(v1, v2) `elem` es ==> (v2,v1) `elem` es

1

(v1, v2) `elem` es ==> (v2,v1) `elem` es

this enforces the symmetry in the graph i.e. if there is an edge coming from v1 to v2 then there must also be a vortex from v2 to v1
Both vs and es are strictly ordered.

instance GraphSpec VEListsGraph where
  empty                    = VE []  []
  addVert v (VE vs es)     = VE vs' es
    where vs' = insert v vs
  addEdge v1 v2 (VE vs es) = VE vs' es'
    where vs' = insert v1 (insert v2 vs)
          es' = insert (v1,v2) (insert (v2,v2) es)

instance GraphSpec VEListsGraph where

empty = VE [] []

addVert v (VE vs es) = VE vs' es

where vs' = insert v vs

addEdge v1 v2 (VE vs es) = VE vs' es'

where vs' = insert v1 (insert v2 vs)

es' = insert (v1,v2) (insert (v2,v2) es)

The empty function simply creates an empty graph, no magic here at all. addVert is a little more complicated. Here

insert :: Ord a =&gt; a -&gt; [a] -&gt; [a]

1	insert :: Ord a => a -> [a] -> [a]

is insertion into an ordered list. Finally we have addEdge which is highly problematic as the insert function to be called 4 times! delete can be implemented in a similar way:

delVert v (VE vs es) = VE vs' es'
  where vs' = delete v vs
        es' = [e | e@(v1,v2) &lt;- es, v1 /= v, v2 /= v]

delEdge v1 v2 (VE vs es) = VE vs es'
  where es' = delete (v1,v2) (delete (v2,v2) es)

delVert v (VE vs es) = VE vs' es'

where vs' = delete v vs

es' = [e | e@(v1,v2) <- es, v1 /= v, v2 /= v]

delEdge v1 v2 (VE vs es) = VE vs es'

where es' = delete (v1,v2) (delete (v2,v2) es)

Again, to maintain the invariant (1) deleting a vertex involves deleting all edges incident to it. This 'multiple edge' deletion could be quite costly. The list comprehension allows us to do it in linear time (with reasonably low constant).

The vertices function which returns a list of all the vertices in the graph is almost free since the vertices are stored as a list. Finally, in order to get all the elements adjecient to a particular vertex v we use adj function. This one runs in O(n) where n is the number of edges. There is a little bit of filtering going on in this function. es' contains a list of all edges which have v as their first element. To make this a little bit faster we mentioned at the beginning that the set will be strictly ordered. This means that we can firstly drop the first 'half' of elements which are strictly smaller than the value we are looking for (remember that v has Ord class type). This can be done through binary search rather than linearly. Then we take all the elements which are equal to the value v using takeWhile.

vertices (VE vs _) = vs

adj v (VE _ es) = map snd es'
  where
  es' = takeWhile((==v) . fst) $ dropWhile ((&lt; v) .fst)) $ es

vertices (VE vs _) = vs

adj v (VE _ es) = map snd es'

where

es' = takeWhile((==v) . fst) $ dropWhile ((< v) .fst)) $ es

For a persistence and dynamic graph data structure, O(1) is unrealistic, but we could bring it down to O(log m) where is is the number of vertices.

Nested Adjacency Sets

We just saw that representing graphs using lists is not a great idea because the operations such as addition, deletion and getting neighbours are quite expensive. One solution around this problem is to use nested adjacency sets. They are a vertex-index table of linked lists of neighbours. Now, we don't have the access to 'tables' as it would defite the point of a purely functional data structure. Instead, we are going to use sets (which we already covered). Those sets will be used for both inner and outer collection. Let us define the data type first: Graph is our graph. It is made of a set which contains another adjacency set.

data Graph a = G (Set (Adj a))

data Adj a = A a (Set a)

data Graph a = G (Set (Adj a))

data Adj a = A a (Set a)

Our invariant is also simpler than it was before. We want to have efficient access to edges from both ends therefore we need to retain symmetry in the representation of edges.

A v ws `member` adjs &amp;&amp; w `member` ws ==&gt; A w vs `member` adjs &amp;&amp; v `member` vs

1	A v ws `member` adjs && w `member` ws ==> A w vs `member` adjs && v `member` vs

This is when it gets slightly tricky, how can the adj function find an A v vs element in a graph's adjacency set, when all it has is v? The simplest solution is to declare custom Ord and Eq instances for Adj a that ignore the neighbours.

instance Eq a =&gt; Eq (Adj a) where
  A v _ == A w _ = v == w

instance Ord a =&gt; Ord (Adj a) where
  compare  (A v _) (A w _) = compare v w

instance Eq a => Eq (Adj a) where

A v _ == A w _ = v == w

instance Ord a => Ord (Adj a) where

compare (A v _) (A w _) = compare v w

So with that out of the way we can move into the matching and updating the array.

match :: Ord a =&gt; a -&gt; Set a -&gt; a
match a (b:x) = case compare a b of
                EQ -&gt; b
                GT -&gt; match a x

addUp :: Ord a =&gt; a -&gt; (a-&gt;a) -&gt; Set a -&gt; Set a
addUp a u [] = [a]
addUp a u bx@(b:x) = case compare a b of
                     LT -&gt; a : bx
                     EQ -&gt; u b : x
                     GT -&gt; b : addUp a u x

match :: Ord a => a -> Set a -> a

match a (b:x) = case compare a b of

EQ -> b

GT -> match a x

addUp :: Ord a => a -> (a->a) -> Set a -> Set a

addUp a u [] = [a]

addUp a u bx@(b:x) = case compare a b of

LT -> a : bx

EQ -> u b : x

GT -> b : addUp a u x

The Blog

Undirected Graphs

List Representation

Nested Adjacency Sets

Leave a Reply Cancel reply

Search

Categories