Safe Haskell | None |
---|---|
Language | Haskell2010 |
This module provides a safe and performant way to perform
operations on graphs. The types Graph
, Vertex
, Vertices
and Size
are all parameterized by a phantom type variable g
.
Much like the s
used with ST
, this type variable will
always be free. It gives us a guarentee that a vertex belongs
in a graph. See the bottom of this page for a more detailed
explanation.
- lookupVertex :: Eq v => v -> Graph g e v -> Maybe (Vertex g)
- lookupEdge :: Vertex g -> Vertex g -> Graph g e v -> Maybe e
- atVertex :: Vertex g -> Graph g e v -> v
- mapVertices :: (Vertex g -> a -> b) -> Graph g e a -> Graph g e b
- mapEdges :: (Vertex g -> Vertex g -> e -> d) -> Graph g e v -> Graph g d v
- 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 ()
- traverseNeighbors_ :: Applicative m => (Vertex g -> v -> e -> m a) -> Vertex g -> Graph g e v -> m ()
- vertices :: Graph g e v -> Vertices g v
- setVertices :: Vertices g v -> Graph g e w -> Graph g e v
- size :: Graph g e v -> Size g
- freeze :: PrimMonad m => MGraph (PrimState m) g e v -> m (Graph g e v)
- create :: PrimMonad m => (forall g. MGraph (PrimState m) g e v -> m ()) -> m (SomeGraph e v)
- with :: SomeGraph e v -> (forall g. Graph g e v -> a) -> a
- dijkstra :: (Ord s, Monoid s, Foldable t) => (v -> v -> s -> e -> s) -> s -> t (Vertex g) -> Graph g e v -> Graph g e s
- dijkstraDistance :: (Num e, Ord e) => Vertex g -> Vertex g -> Graph g e v -> Maybe e
- dijkstraFoldM :: (Ord s, Monoid s, Foldable t, PrimMonad m) => (v -> v -> s -> e -> s) -> (v -> s -> x -> m x) -> s -> x -> t (Vertex g) -> Graph g e v -> m x
- sizeInt :: Size g -> Int
- vertexInt :: Vertex g -> Int
- verticesRead :: Vertices g v -> Vertex g -> v
- verticesLength :: Vertices g v -> Int
- verticesTraverse :: Applicative m => (Vertex g -> v -> m a) -> Vertices g v -> m (Vertices g a)
- verticesTraverse_ :: Applicative m => (Vertex g -> v -> m a) -> Vertices g v -> m ()
- verticesToVertexList :: Vertices g v -> [Vertex g]
- verticesToVector :: Vertices g v -> Vector v
- verticesThaw :: PrimMonad m => Vertices g v -> m (MVertices (PrimState m) g v)
- verticesFreeze :: PrimMonad m => MVertices (PrimState m) g v -> m (Vertices g v)
Graph Operations
mapVertices :: (Vertex g -> a -> b) -> Graph g e a -> Graph g e b Source #
Not the same as fmap
because the function also takes the vertex id.
mapEdges :: (Vertex g -> Vertex g -> e -> d) -> Graph g e v -> Graph g d v Source #
Map of the edges in the graph.
traverseVertices_ :: Applicative m => (Vertex g -> v -> m a) -> Graph g e v -> m () Source #
traverseEdges_ :: Applicative m => (Vertex g -> Vertex g -> v -> v -> e -> m a) -> Graph g e v -> m () Source #
This traverses every edge in the entire graph.
traverseNeighbors_ :: Applicative m => (Vertex g -> v -> e -> m a) -> Vertex g -> Graph g e v -> m () Source #
Traverse the neighbors of a specific vertex.
freeze :: PrimMonad m => MGraph (PrimState m) g e v -> m (Graph g e v) Source #
Make an immutable copy of a mutable graph.
create :: PrimMonad m => (forall g. MGraph (PrimState m) g e v -> m ()) -> m (SomeGraph e v) Source #
Algorithms
:: (Ord s, Monoid s, Foldable t) | |
=> (v -> v -> s -> e -> s) | Weight function |
-> s | Weight to assign start vertex |
-> t (Vertex g) | Start vertices |
-> Graph g e v | Graph |
-> Graph g e s |
This is a generalization of Dijkstra's algorithm. Like the original,
it takes a start Vertex
but unlike the original, it does not take
an end. It will continue traversing the Graph
until it has touched
all vertices that are reachable from the start vertex.
Additionally, this function generalizes the notion of distance. It can be numeric (as Dijkstra has it) data, non-numeric data, or tagged numeric data. This can be used, for example, to find the shortest path from the start vertex to all other vertices in the graph.
In Dijkstra's original algorithm, tentative distances are initialized to infinity. After a node is visited, the procedure for updating its neighbors' tentative distance to a node is to compare the existing tentative distance with the new one and to keep the lesser of the two.
In this variant, tentative distances are initialized to mempty
.
The update procedure involves combining them with mappend
instead
of being choosing the smaller of the two. For this
algorithm to function correctly, the distance s
must have Ord
and
Monoid
instances satisfying:
∀ a b. mappend a b ≤ a ∀ a b. mappend a b ≤ b ∀ c. mempty ≥ c
Additionally, the Monoid
instance should have a commutative mappend
:
∀ a b. mappend a b ≅ mappend b a
The weight function is described by:
from to from edge tentative node node weight value to weight | | | | | V V V V V (v -> v -> s -> e -> s)
In many cases, some of input values can be ignored. For example, to implement
Dijkstra's original algorithm the from-node
and to-node
values are
not needed. The weight combining function will typically use the from-weight
in some way. The way this algorithm uses the weight function makes it suseptible to
the same negative-edge problem as the original. For some weight combining
function f
, it should be the case that:
∀ v1 v2 s e. f v1 v2 s e ≥ s
This function could be written without unsafely pattern matching
on Vertex
, but doing so allows us to use a faster heap implementation.
Find the shortest path between two vertices using Dijkstra's algorithm. The source code of this function provides an example of how to use the generalized variants of Dijkstra's algorithm provided by this module.
Size and Vertex
Vertices
verticesRead :: Vertices g v -> Vertex g -> v Source #
verticesLength :: Vertices g v -> Int Source #
verticesTraverse :: Applicative m => (Vertex g -> v -> m a) -> Vertices g v -> m (Vertices g a) Source #
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 () Source #
This is currently inefficient. If an itraverse
gets added
to vector
, this can be made faster.
verticesToVertexList :: Vertices g v -> [Vertex g] Source #
verticesToVector :: Vertices g v -> Vector v Source #