Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Functional programming with graphs
16
Functional programming with graphs
Exploring graphs and graph algorithms in functional programming
Berlin Haskell Meetup 2017-11-15
Graphs are a fundamental data structure in computer science because a lot of problems can be modelled using graphs…
Motivation
…can I use a functional programming language to solve those problems efficiently & elegantly?
Graph applications
Image taken from a slide of the Algorithms part 2 MOOC on Coursera by Bob Sedgwick and Kevin Wayne
Imperative algorithms
- literature is easy to find and there's plenty of it
- hard to understand (mostly because of…)
- lots of bookkeeping (aka state)
- not modular or composable
- hard to formally proove
Functional algorithms
(ideally)
- elegant
- no bookkeeping necessary and no state
- modular
- composable
- easy to formally proove
Reality
- literature is kind of hard to find and is mostly academic papers (books anyone?!)
- performance not always on a par with imperative-style algorithms
- use monads to mimic imperative-style strategies
- not really modular or composable
Imperative-style algorithms with monads
- state and side effect made explicit
- pattern matching
- hard to understand
- lots of bookkeeping (state)
- not modular / composable
- hard to formally proove
* Too verbose to show a code snippet in such a small available space
Towards a functional solution (1995)
Towards a functional solution
Generate and prune
(pseudo-code)
type Forest a = [RoseTree a]
type Vertex = Int
type EdgeNode = (Vertex, Weight)
type Graph = Immutable.Array Vertex [EdgeNode]
dfs :: Graph -> [Vertex] -> Forest Vertex
dfs g = prune (bounds g) . map (generate g)
where
prune bnds ts = runST $ do
array <- mkEmpty bnds
chop ts array
chop :: Forest Vertex -> Mutable.Array Vertex Bool -> Forest Vertex
This code is a simplified version of the real one and does not type-check
Gist of the algorithm
- generate step describes how to create all possible trees from a given vertex
- prune step discards the sub-trees whose root is a discovered vertex
- call-by-need assures that a given expression is evaluated on-demand: discarded trees will never be evaluated (traversed) so they will never be created in the first place.
Monadic code for efficiency
chop :: (MA.MArray (MA.STUArray s) Bool m)
=> Forest Vertex
-> MA.STUArray s Vertex Bool
-> m (Forest Vertex)
chop [] _arr = return []
chop (Node v ts:ns) arr = do
visited <- contains arr v
if visited then chop ns arr -- prune ts
else do
include arr v
-- traverse left-to-right
ts' <- chop ts arr
-- traverse top-to-bottom
ns' <- chop ns arr
return $ Node v ts' : ns'
Inductive graphs
(2001)
Inductive graphs
Conceptual definition
data Graph w l = Empty
| Context w l :&: Graph w l
type Context w l = (Adj w, Vertex, l, Adj w)
type Adj w = [(w, Vertex)]
type Vertex = Int
Graph construction
\: read "mkG [('a', 1), ('b', 2), ('c', 3)] [(1, 2, 5), (2, 1, 3), (2, 3, 1), (3, 1, 4)]"
([],3,'c',[(4,'a')]) :&: (([(5,'a')],2,'b',[(3,'a'),(1,'c')]) :&: (([],1,'a',[]) :&: Empty))
\: read "mkG [('c', 3), ('b', 2), ('a', 1)] [(1, 2, 5), (2, 1, 3), (2, 3, 1), (3, 1, 4)]"
([(4,'c'),(3,'b')],1,'a',[(5,'b')]) :&: (([],2,'b',[(1,'c')]) :&: (([],3,'c',[]) :&: Empty))
Multiple "shapes" one graph
- The order used for vertex insertion determines the "shape" of the inductive graph
- Equality of inductive graphs is based upon the set of vertices and edges, not their "shapes"
- This is important for active graph patterns (coming next…)
Active graph patterns & implementation
An extensions of patterns that allows to apply a function to the argument before the matching happens.
Active graph patterns & implementation
c (:&: ! v) g
The code above won't type-check! It's only meant to provide an intuition of active patterns
(conceptually) transform the input graph g into one in which the context for the vertex v is inserted last (if v is contained in the graph)
match
Active patterns are not essential to the implementation of inductive graphs. A function match with the following type signature will also work:
match
match :: Vertex -> Graph w l -> Maybe (Context w l, Graph w l)
Returns the context for the input vertex (if any) and a new inductive graph that doesn't contain the input vertex. the "shape" of the output graph doesn't matter!
Example
\: let g = read "mkG [('a', 1), ('b', 2), ('c', 3)] [(1, 2, 5), (2, 1, 3), (2, 3, 1), (3, 1, 4)]"
([],3,'c',[(4,'a']) :&: (([(5,'a')],2,'b',[(3,'a'),(1,'c')]) :&: (([],1,'a',[]) :&: Empty))
Example
'a'`match`g == Just (([(4, 'a'),(3,'b')], 1, 'a', [(5,'b')]),g')
Real world implementation
- inductive graphs are fully persistent data structures
- binary search tree is used to represent a graph: a pair (t, m) where t = (vertex, (inbound_edges, label, outbound_edges)) and m is the largest node in t
Functional algorithms
Caveat on time complexity of the algorithms on inductive graphs:
assume that :&: and active graph patterns implementations take constant time
in a nutshell: visit successors before siblings
dfs :: [Vertex] -> Graph w l -> [Vertex]
dfs _ Empty = []
dfs [] _ = []
dfs (v:vs) g = maybe (dfs vs g) dfs' (v `match` g)
where
-- `succs` returns all the successor edges
dfs' (ctx@(_,vtx,_,_), g') = vtx : dfs ((succs ctx) ++ vs) g'
Depth-first search
- Appending the successors at the beginning of the list makes the algorithm searching in depth
- no need for bookkeeping: DFS recursively called on a new graph that doesn't contain the context of the current vertex
in a nutshell: visit successors after siblings
bfs :: [Vertex] -> Graph w l -> [Vertex]
bfs _ Empty = []
bfs [] _ = []
bfs (v:vs) g = maybe (bfs vs g) bfs' (v `match` g)
where
-- `succs` returns all the successor edges
bfs' (ctx@(_,vtx,_,_), g') = vtx : bfs (vs ++ (succs ctx)) g'
Breadth-first search
- Appending successors at the end of the makes the algorithm searching in breadth
- BFS and DFS implementations are the same except for where successors are appended
- Efficient queue to achieve linear running time
newtype LPath l = LPath { unwrap :: [(l, Vertex)] }
instance Eq l => Eq (LPath l) where …
instance Ord l => Ord (LPath l) where …
type LRTree l = [LPath l] -- Labelled R-Tree (or Root Tree)
…
dijkstra :: (Monoid w, Ord w) => Heap.Heap (LPath w) -> Graph w l -> LRTree w
dijkstra h g | isEmpty g = []
| otherwise = maybe [] dijkstra' (Heap.viewMin h)
where
dijkstra' (LPath p@((_, v):_), h') =
maybe (dijkstra h' g) (\(ctx, g') -> LPath p : dijkstra (mergeAll p h' ctx) g')
(v `match` g)
mergeAll :: [(l, Vertex)] -> Heap.Heap (LPath l) -> Context l l -> Heap.Heap (LPath l)
shortestPathTree :: (Monoid w, Ord w) => Vertex -> Graph w l -> LRTree w
shortestPathTree src = dijkstra (Heap.singleton $ LPath [(mempty, src)])
shortestPath :: (Monoid w, Ord w) => Vertex -> Vertex -> Graph w l -> Path
shortestPath src dst = getPath dst . shortestPathTree src
Shortest path
Gist of the algorithm
- Append the path to the current vertex v
- Create a list with all paths to the siblings of v
- Get the least expensive path to an undiscovered vertex from the min-heap
- Loop until the graph is empty (paths to all reachable vertices have been found)
Keep in touch
Yours truly
- futtetennista@gmail.com
- https://futtetennismo.me
- https://github.com/futtetennista
- https://twitter.com/futtetennista
- https://stackoverflow.com/story/futtetennista
- https://keybase.io/futtetennista