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

Functor (Graph k)

#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 -> Maybe (Graph k v)

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

Does nothing if the edge is already present. Returns Nothing iff either key is absent from the graph.

#deleteEdge Source

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

Remove edge from the start key to the end key.

Does nothing if the edge isn't present.

#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.

#deleteVertex Source

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

Remove the given vertex from the graph.

Does nothing if the key isn't present.

#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.

#edges Source

edges :: forall v k. Ord k => Graph k v -> Set (Tuple k k)

List all edges 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.

Returns mempty if the queried key is absent from the graph.

#isChildOf Source

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

Returns false if either key is absent from the graph.

#descendants Source

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

Returns all descendants of given key.

Returns bottom if k is in cycle. Returns mempty if the queried key is absent from the graph.

#isDescendantOf Source

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

Returns false if either key is absent from the graph.

#parents Source

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

Returns immediate ancestors of given key.

Returns mempty if the queried key is absent from the graph.

#isParentOf Source

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

Returns false if either key is absent from the graph.

#ancestors Source

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

Returns all ancestors of given key.

Returns bottom if k is in cycle. Returns mempty if the queried key is absent from the graph.

#isAncestorOf Source

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

Returns false if either key is absent from the graph.

#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.

Returns mempty if the key is absent from the graph.

#areAdjacent Source

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

Check if the keys are adjacent.

Returns false if either key is absent from the graph.

#areConnected Source

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

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

#isValidPath Source

isValidPath :: forall v k. Ord k => Graph k v -> NonEmptyList k -> Boolean

#shortestPath Source

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

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

Returns Nothing if there's no path between the keys or if the keys aren't present in the graph. Cyclic graphs may return bottom.

#allPaths Source

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

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

Cyclic graphs may return bottom. Returns mempty if either key is absent from the graph.

Modules: Data.Graph