Module

# Data.Graph

Package
purescript-digraph
Repository
nullobject/purescript-digraph

``type AdjacencyList a w = List (Tuple a (List (Tuple a w)))``

`AdjacencyList a w` represents a `List` of vertices of type `a` with a list of adjacent vertices connected with edges of type `w`.

### #GraphSource

``newtype Graph a w``

`Graph a w` represents a graph of vertices of type `a` connected by edges with a weight of type `w`. It is represented internally as a map of maps.

#### Instances

• `Newtype (Graph a w) _`
• `(Show a, Show w) => Show (Graph a w)`

### #emptySource

``empty :: forall a w. Ord a => Graph a w``

An empty graph.

### #isEmptySource

``isEmpty :: forall a w. Ord a => Graph a w -> Boolean``

Test whether a graph is empty.

``fromAdjacencyList :: forall a w. Ord a => AdjacencyList a w -> Graph a w``

Create a graph from an adjacency list.

### #verticesSource

``vertices :: forall a w. Graph a w -> List a``

Get the vertices of a graph.

### #sizeSource

``size :: forall a w. Graph a w -> Int``

Get the number of vertices in a graph.

### #elemSource

``elem :: forall a w. Ord a => a -> Graph a w -> Boolean``

Test whether a vertex is in a graph.

``adjacent :: forall a w. Ord a => a -> Graph a w -> List a``

Get the adjacent vertices of a vertex.

``adjacent' :: forall a w. Ord a => a -> Graph a w -> List (Tuple a w)``

Get the adjacent vertices and associated costs of a vertex.

``isAdjacent :: forall a w. Ord a => a -> a -> Graph a w -> Boolean``

Test whether two vertices are adjacent in a graph.

### #weightSource

``weight :: forall a w. Ord a => a -> a -> Graph a w -> Maybe w``

Get the weight of the edge between two vertices. Returns `Nothing` if no edge exists between the vertices.

### #shortestPathSource

``shortestPath :: forall a w. Ord a => Ord w => Semiring w => a -> a -> Graph a w -> Maybe (List a)``

Get the shortest path between two vertices. Returns `Nothing` if no path exists between the vertices.

### #shortestPath'Source

``shortestPath' :: forall a w. Ord a => Ord w => Semiring w => (a -> Boolean) -> a -> Graph a w -> Maybe (List a)``

Get the shortest path from a starting vertex to a vertex that satisifes a predicate function. Returns `Nothing` if no path exists between the vertices.

### #traverseSource

``traverse :: forall a w. Ord a => a -> Graph a w -> List a``

Perform a depth-frist traversal of a graph from a starting vertex. Returns a `List` of the visited vertices.

### #connectedComponentsSource

``connectedComponents :: forall a w. Ord a => Graph a w -> List (Graph a w)``

Get the strongly connected components of a graph. Returns a `List` of connected subgraphs.

### #insertVertexSource

``insertVertex :: forall a w. Ord a => a -> Graph a w -> Graph a w``

Insert a vertex into a graph.

### #insertEdgeSource

``insertEdge :: forall a w. Ord a => a -> a -> w -> Graph a w -> Graph a w``

Insert an edge into a graph.

### #deleteVertexSource

``deleteVertex :: forall a w. Ord a => a -> Graph a w -> Graph a w``

Delete a vertex from a graph.

### #deleteEdgeSource

``deleteEdge :: forall a w. Ord a => a -> a -> Graph a w -> Graph a w``

Delete an edge from a graph.

### #filterSource

``filter :: forall a w. Ord a => (a -> Boolean) -> Graph a w -> Graph a w``

Remove the matching vertices from a graph.

Modules
Data.Graph