A directed graph library for PureScript.
The directed graph pictured above can be represented with an
An adjacency list is a list of tuples that contain a vertex and a list of edges
to its adjacent vertices. A
Graph can be constructed from an
let edges = fromFoldable $ [ Tuple 'A' (fromFoldable [Tuple 'B' 1, Tuple 'C' 2]) , Tuple 'B' (fromFoldable [Tuple 'A' 1, Tuple 'D' 3]) , Tuple 'C' (fromFoldable [Tuple 'A' 2, Tuple 'D' 4]) , Tuple 'D' (fromFoldable [Tuple 'B' 3, Tuple 'C' 4]) , Tuple 'E' (fromFoldable [Tuple 'F' 1]) , Tuple 'F' (fromFoldable [Tuple 'E' 1]) , Tuple 'G' (fromFoldable ) ] let graph = fromAdjacencyList edges
size function returns the number of vertices in a graph.
size graph -- 7
vertices function returns a list of the vertices in a graph.
vertices graph -- ['A', 'B', 'C', 'D', 'E', 'F', 'G']
isAdjacent function returns true if two vertices are connected by an edge.
isAdjacent 'A' 'B' graph -- true
weight function returns the weight of the edge between two vertices.
weight 'A' 'B' graph -- Just 1
adjacent function returns all vertices connected to a vertex by an edge.
adjacent' function will also include the weight of the edges.
adjacent 'A' graph -- ['B', 'C'] adjacent' 'A' graph -- [Tuple 'B' 1, Tuple 'C' 2]
shortestPath function calculates the shortest path between two vertices
shortestPath 'A' 'D' graph -- ['A', 'B', 'D']
connectedComponents function calculates a list of connected components in a graph.
A connected component is a maximal subgraph in which any two vertices are connected to each other by a path.
connectedComponents graph -- [Graph, Graph, Graph]
An empty graph can be constructed and updated.
(insertEdge 'A' 'B' 1 <<< insertVertex 'A' <<< insertVertex 'B') empty -- Graph