Module

Data.Graph

Package: purescript-digraph
Repository: nullobject/purescript-digraph

#AdjacencyList Source

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.

#Graph Source

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)

#empty Source

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

An empty graph.

#isEmpty Source

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

Test whether a graph is empty.

#fromAdjacencyList Source

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

Create a graph from an adjacency list.

#vertices Source

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

Get the vertices of a graph.

#size Source

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

Get the number of vertices in a graph.

#elem Source

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

Test whether a vertex is in a graph.

#adjacent Source

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

Get the adjacent vertices of a vertex.

#adjacent' Source

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

Get the adjacent vertices and associated costs of a vertex.

#isAdjacent Source

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

Test whether two vertices are adjacent in a graph.

#weight Source

weight :: forall w a. 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.

#shortestPath Source

shortestPath :: forall w a. 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 w a. 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.

#traverse Source

traverse :: forall w a. 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.

#connectedComponents Source

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

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

#insertVertex Source

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

Insert a vertex into a graph.

#insertEdge Source

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

Insert an edge into a graph.

#deleteVertex Source

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

Delete a vertex from a graph.

#deleteEdge Source

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

Delete an edge from a graph.

#filter Source

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

Remove the matching vertices from a graph.

Modules: Data.Graph