Crem.Graph

A simple data structure to describe a directed graph

Graph

newtype Graph a

A graph is just a list of edges between vertices of type a

Constructors

Graph [(a, a)]

Instances

Show a => Show (Graph a)

Defined in Crem.Graph

Methods

showsPrec :: Int -> Graph a -> ShowS

show :: Graph a -> String

showList :: [Graph a] -> ShowS

Eq a => Eq (Graph a)

Defined in Crem.Graph

Methods

(==) :: Graph a -> Graph a -> Bool

(/=) :: Graph a -> Graph a -> Bool

productGraph :: Graph a -> Graph b -> Graph (a, b)

The product graph. It has as vertices the product of the set of vertices of the initial graph. It has as edge from (a1, b1) to (a2, b2) if and only if there is an edge from a1 to a2 and an edge from b1 to b2

>>> productGraph (Graph [('a', 'b')]) (Graph [('c', 'd')])
Graph [(('a','c'),('b','d'))]

transitiveClosureGraph :: Eq a => Graph a -> Graph a

Computes all the possible paths in the input graph and considers them as edges. Notice that the current implementation is removing duplicates

addIdentityEdges :: RenderableVertices a => Graph a -> Graph a

Add all the identity edges to a graph

removeIdentityEdges :: Eq a => Graph a -> Graph a

Remove all the edges which start and end at the same vertex

UntypedGraph

data UntypedGraph

A data type to represent a graph which is not tracking the vertex type

Constructors

forall a.(RenderableVertices a, Eq a, Show a) => UntypedGraph (Graph a)

Instances

Show UntypedGraph

Defined in Crem.Graph

Methods

showsPrec :: Int -> UntypedGraph -> ShowS

show :: UntypedGraph -> String

showList :: [UntypedGraph] -> ShowS

untypedProductGraph :: UntypedGraph -> UntypedGraph -> UntypedGraph

Same as productGraph but for UntypedGraph

untypedTransitiveClosureGraph :: UntypedGraph -> UntypedGraph

Same as transitiveClosureGraph but for UntypedGraph

untypedAddIdentityEdges :: UntypedGraph -> UntypedGraph

Add all identity edges to an UntypedGraph

untypedRemoveIdentityEdges :: UntypedGraph -> UntypedGraph

Remove all the edges which start and end at the same vertex from an UntypedGraph