Data.Graph.Immutable

Documentation

dijkstra

Arguments

:: (Ord s, Monoid s)

=> (v -> v -> s -> e -> s)

-> s

Weight to assign start vertex

-> Vertex g

start

-> Vertex g

end

-> Graph g e v

-> s

dijkstraTraversal

Arguments

:: (Ord s, Monoid s)

=> (v -> v -> s -> e -> s)

Weight combining function

-> s

Weight to assign start vertex

-> Vertex g

Start vertex

-> Graph g e v

-> Vertices g s

This is a generalization of Dijkstra's algorithm. This function could be written without unsafely pattern matching on Vertex, but doing so allows us to use a faster heap implementation.

lookupVertex :: Eq v => v -> Graph g e v -> Maybe (Vertex g)

mapVertices :: (Vertex g -> a -> b) -> Graph g e a -> Graph g e b

Not the same as fmap because the function also takes the vertex id.

traverseVertices_ :: Applicative m => (Vertex g -> v -> m a) -> Graph g e v -> m ()

traverseEdges_ :: Applicative m => (Vertex g -> Vertex g -> v -> v -> e -> m a) -> Graph g e v -> m ()

This traverses every edge in the entire graph.

traverseNeighbors_ :: Applicative m => (Vertex g -> v -> e -> m a) -> Vertex g -> Graph g e v -> m ()

Change this to use unsafeRead some time soon.

lookupEdge :: Vertex g -> Vertex g -> Graph g e v -> Maybe e

mutableIForM_ :: PrimMonad m => MVector (PrimState m) a -> (Int -> a -> m b) -> m ()

mutableIFoldM' :: PrimMonad m => (a -> Int -> b -> m a) -> a -> MVector (PrimState m) b -> m a

vertices :: Graph g e v -> Vertices g v

size :: Graph g e v -> Size g

unSize :: Size g -> Int

vertexInt :: Vertex g -> Int

verticesToVertexList :: Vertices g v -> [Vertex g]

verticesTraverse :: Applicative m => (Vertex g -> v -> m a) -> Vertices g v -> m (Vertices g a)

This is currently inefficient. If an itraverse gets added to vector, this can be made faster.

verticesTraverse_ :: Applicative m => (Vertex g -> v -> m a) -> Vertices g v -> m ()

This is currently inefficient. If an itraverse gets added to vector, this can be made faster.

verticesToVector :: Vertices g v -> Vector v

verticesRead :: Vertices g v -> Vertex g -> v

verticesLength :: Vertices g v -> Int

verticesFreeze :: PrimMonad m => MVertices g (PrimState m) v -> m (Vertices g v)

verticesThaw :: PrimMonad m => Vertices g v -> m (MVertices g (PrimState m) v)

freeze :: PrimMonad m => MGraph g (PrimState m) e v -> m (Graph g e v)

create :: PrimMonad m => (forall g. MGraph g (PrimState m) e v -> m ()) -> m (SomeGraph e v)

Takes a function that builds on an empty MGraph. After the function mutates the MGraph, it is frozen and becomes an immutable SomeGraph.

with :: SomeGraph e v -> (forall g. Graph g e v -> a) -> a