Module

Data.Graph

Package
purescript-colehaus-graphs
Repository
colehaus/purescript-graphs

A data structure and functions for graphs

#Graph Source

newtype Graph k v

A graph with vertices of type v.

Edges refer to vertices using keys of type k.

Instances

#unfoldGraph Source

unfoldGraph :: forall out v k f. Ord k => Functor f => Foldable f => Foldable out => f k -> (k -> v) -> (k -> out k) -> Graph k v

Unfold a Graph from a collection of keys and functions which label keys and specify out-edges.

#fromMap Source

fromMap :: forall v k. Map k (Tuple v (Set k)) -> Graph k v

Create a Graph from a Map which maps vertices to their labels and outgoing edges.

#toMap Source

toMap :: forall v k. Graph k v -> Map k (Tuple v (Set k))

Turn a Graph into a Map which maps vertices to their labels and outgoing edges.

#empty Source

empty :: forall v k. Graph k v

An empty graph.

#insertEdge Source

insertEdge :: forall v k. Ord k => k -> k -> Graph k v -> Graph k v

Insert an edge from the start key to the end key.

#insertVertex Source

insertVertex :: forall v k. Ord k => k -> v -> Graph k v -> Graph k v

Insert a vertex into the graph.

If the key already exists, replaces the existing value and preserves existing edges.

#insertEdgeWithVertices Source

insertEdgeWithVertices :: forall v k. Ord k => Tuple k v -> Tuple k v -> Graph k v -> Graph k v

Insert two vertices and connect them.

#vertices Source

vertices :: forall v k. Graph k v -> List v

List all vertices in a graph.

#lookup Source

lookup :: forall v k. Ord k => k -> Graph k v -> Maybe v

Lookup a vertex by its key.

#outEdges Source

outEdges :: forall v k. Ord k => k -> Graph k v -> Maybe (Set k)

Get the keys which are directly accessible from the given key.

#children Source

children :: forall v k. Ord k => k -> Graph k v -> Set k

Returns immediate descendants of given key.

#descendants Source

descendants :: forall v k. Ord k => k -> Graph k v -> Set k

Returns all descendants of given key.

Will return bottom if k is in cycle.

#parents Source

parents :: forall v k. Ord k => k -> Graph k v -> Set k

Returns immediate ancestors of given key.

#ancestors Source

ancestors :: forall v k. Ord k => k -> Graph k v -> Set k

Returns all ancestors of given key.

Will return bottom if k is in cycle.

#topologicalSort Source

topologicalSort :: forall v k. Ord k => Graph k v -> List k

Topologically sort the vertices of a graph.

If the graph contains cycles, then the behavior is undefined.

#isInCycle Source

isInCycle :: forall v k. Ord k => k -> Graph k v -> Boolean

Checks if given key is part of a cycle.

#isCyclic Source

isCyclic :: forall v k. Ord k => Graph k v -> Boolean

Checks if there any cycles in graph.

#isAcyclic Source

isAcyclic :: forall v k. Ord k => Graph k v -> Boolean

Checks if there are not any cycles in the graph.

#alterVertex Source

alterVertex :: forall k v. Ord k => (Maybe v -> Maybe v) -> k -> Graph k v -> Graph k v

#alterEdges Source

alterEdges :: forall k v. Ord k => (Maybe (Set k) -> Maybe (Set k)) -> k -> Graph k v -> Graph k v

#adjacent Source

adjacent :: forall v k. Ord k => k -> Graph k v -> Set k

Find all keys adjacent to given key.

#isAdjacent Source

isAdjacent :: forall v k. Ord k => k -> k -> Graph k v -> Boolean

Check if the first key is adjacent to the second.

#areConnected Source

areConnected :: forall v k. Ord k => k -> k -> Graph k v -> Boolean

Checks if there's a directed path between the start and end key.

#shortestPath Source

shortestPath :: forall v k. Ord k => k -> k -> Graph k v -> Maybe (List k)

Returns shortest path between start and end key if it exists.

Cyclic graphs may return bottom.

#allPaths Source

allPaths :: forall v k. Ord k => k -> k -> Graph k v -> Set (List k)

Returns shortest path between start and end key if it exists.

Cyclic graphs may return bottom.

Modules
Data.Graph