Safe Haskell  Safe 

Language  Haskell2010 
 class Graph g where
 class IsEdge e where
 data Edge v e = Edge v v e
 data Arc v e = Arc v v e
 (<>) :: Hashable v => v > v > Edge v ()
 (>) :: Hashable v => v > v > Arc v ()
 class Weighted e where
 class Labeled e where
 arbitraryEdge :: (Arbitrary v, Arbitrary e, Ord v, Num v) => (v > v > e > edge) > Gen edge
 tripleToPair :: (a, b, c) > (a, b)
 pairToTriple :: (a, b) > (a, b, ())
 tripleOriginVertex :: (v, v, e) > v
 tripleDestVertex :: (v, v, e) > v
 tripleAttribute :: (v, v, e) > e
Documentation
Types that behave like graphs

 The main Graph
instances are UGraph
and DGraph
. The functions in this
class should be used for algorithms that are graphdirectionality agnostic,
otherwise use the more specific ones in UGraph
and DGraph
empty, order, vertices, edgeTriples, containsVertex, areAdjacent, adjacentVertices', reachableAdjacentVertices', vertexDegree, insertVertex, containsEdgePair, incidentEdgeTriples, edgeTriple, insertEdgeTriple, removeVertex, removeEdgePair, isSimple, union, intersection, join, toList, toAdjacencyMatrix, fromAdjacencyMatrix
empty :: Hashable v => g v e Source #
The Empty (orderzero) graph with no vertices and no edges
order :: g v e > Int Source #
Retrieve the order of a graph
 The order
of a graph is its number of vertices
size :: (Hashable v, Eq v) => g v e > Int Source #
Retrieve the size of a graph
 The size
of a graph is its number of edges
density :: (Hashable v, Eq v) => g v e > Double Source #
Density of a graph  The ratio of the number of existing edges in the graph to the number of  posible edges
vertices :: g v e > [v] Source #
Retrieve the vertices of a graph
edgeTriples :: (Hashable v, Eq v) => g v e > [(v, v, e)] Source #
Retrieve the edges of a graph
edgePairs :: (Hashable v, Eq v) => g v e > [(v, v)] Source #
Retrieve the edges of a graph, ignoring its attributes
containsVertex :: (Hashable v, Eq v) => g v e > v > Bool Source #
Tell if a vertex exists in the graph
areAdjacent :: (Hashable v, Eq v) => g v e > v > v > Bool Source #
Tell if two vertices are adjacent
adjacentVertices :: (Hashable v, Eq v) => g v e > v > [v] Source #
Retrieve the adjacent vertices of a vertex
adjacentVertices' :: (Hashable v, Eq v) => g v e > v > [(v, v, e)] Source #
Same as adjacentVertices
but gives back the connecting edges
reachableAdjacentVertices :: (Hashable v, Eq v) => g v e > v > [v] Source #
Same as adjacentVertices
but gives back only those vertices for which
 the connecting edge allows the vertex to be reached.

 For an undirected graph this is equivalent to adjacentVertices
, but
 for the case of a directed graph, the directed arcs will constrain the
 reachability of the adjacent vertices.
reachableAdjacentVertices' :: (Hashable v, Eq v) => g v e > v > [(v, v, e)] Source #
Same as reachableAdjacentVertices
but gives back the connecting edges
vertexDegree :: (Hashable v, Eq v) => g v e > v > Int Source #
Total number of incident edges of a vertex
degrees :: (Hashable v, Eq v) => g v e > [Int] Source #
Degrees of a all the vertices in a graph
maxDegree :: (Hashable v, Eq v) => g v e > Int Source #
Maximum degree of a graph
minDegree :: (Hashable v, Eq v) => g v e > Int Source #
Minimum degree of a graph
avgDegree :: (Hashable v, Eq v) => g v e > Double Source #
Average degree of a graph
insertVertex :: (Hashable v, Eq v) => v > g v e > g v e Source #
Insert a vertex into a graph  If the graph already contains the vertex leave the graph untouched
insertVertices :: (Hashable v, Eq v) => [v] > g v e > g v e Source #
Insert a many vertices into a graph  New vertices are inserted and already contained vertices are left  untouched
containsEdgePair :: (Hashable v, Eq v) => g v e > (v, v) > Bool Source #
Tell if an edge exists in the graph
incidentEdgeTriples :: (Hashable v, Eq v) => g v e > v > [(v, v, e)] Source #
Retrieve the incident edges of a vertex
incidentEdgePairs :: (Hashable v, Eq v) => g v e > v > [(v, v)] Source #
Retrieve the incident edges of a vertex, ignoring its attributes
edgeTriple :: (Hashable v, Eq v) => g v e > v > v > Maybe (v, v, e) Source #
Get the edge between to vertices if it exists
insertEdgeTriple :: (Hashable v, Eq v) => (v, v, e) > g v e > g v e Source #
Insert an edge into a graph  The involved vertices are inserted if don't exist. If the graph already  contains the edge, its attribute is updated
insertEdgeTriples :: (Hashable v, Eq v) => [(v, v, e)] > g v e > g v e Source #
Same as insertEdgeTriple
but for multiple edges
insertEdgePair :: (Hashable v, Eq v) => (v, v) > g v () > g v () Source #
Same as insertEdgeTriple
but insert edge pairs in graphs with
 attributeless edges
insertEdgePairs :: (Hashable v, Eq v) => [(v, v)] > g v () > g v () Source #
Same as insertEdgePair
for multiple edges
removeVertex :: (Hashable v, Eq v) => v > g v e > g v e Source #
Remove a vertex from a graph if present  Every edge incident to this vertex is also removed
removeVertices :: (Hashable v, Eq v) => [v] > g v e > g v e Source #
Same as removeVertex
but for multiple vertices
removeEdgePair :: (Hashable v, Eq v) => (v, v) > g v e > g v e Source #
Remove an edge from a graph if present  The involved vertices are left untouched
removeEdgePairs :: (Hashable v, Eq v) => [(v, v)] > g v e > g v e Source #
Same as removeEdgePair
but for multple edges
removeEdgePairAndVertices :: (Hashable v, Eq v) => (v, v) > g v e > g v e Source #
Remove the edge from a graph if present  The involved vertices are also removed
isSimple :: (Hashable v, Eq v) => g v e > Bool Source #
Tell if a graph is simple
 A graph is simple
if it has no loops
union :: g v e > g v e > g v e Source #
Union of two graphs
intersection :: g v e > g v e > g v e Source #
Intersection of two graphs
join :: g v e > g v e > g v e Source #
Join two graphs

 The join
of two graphs G1 and G2 is a new graph where each vertex of
 G1 has an edge to all the vertices of G2
toList :: (Hashable v, Eq v) => g v e > [(v, [(v, e)])] Source #
Convert a graph to an adjacency list with edge attributes in e
fromList :: (Hashable v, Eq v) => [(v, [(v, e)])] > g v e Source #
Construct a graph from an adjacency list with edge attributes in e
toAdjacencyMatrix :: g v e > [[Int]] Source #
Get the adjacency binary matrix representation of a grah
fromAdjacencyMatrix :: [[Int]] > Maybe (g Int ()) Source #
Generate a graph of Int vertices from an adjacency  square binary matrix
Types that represent edges

 The main IsEdge
instances are Edge
for undirected edges and Arc
for
directed edges.
originVertex :: e v a > v Source #
Retrieve the origin vertex of the edge
destinationVertex :: e v a > v Source #
Retrieve the destination vertex of the edge
attribute :: e v a > a Source #
Retrieve the attribute of the edge
toPair :: e v a > (v, v) Source #
Convert an edge to a pair discarding its attribute
fromPair :: (v, v) > e v () Source #
Convert a pair to an edge, where it's attribute is unit
toTriple :: e v a > (v, v, a) Source #
Convert an edge to a triple, where the 3rd element it's the edge  attribute
fromTriple :: (v, v, a) > e v a Source #
Convert a triple to an edge
isLoop :: Eq v => e v a > Bool Source #
Tell if an edge is a loop
 An edge forms a loop
if both of its ends point to the same vertex
Undirected Edge with attribute of type e between to Vertices of type v
Edge v v e 
IsEdge Edge Source #  
Functor (Edge v) Source #  
(Eq v, Eq a) => Eq (Edge v a) Source #  Two 
(Ord e, Ord v) => Ord (Edge v e) Source #  
(Read e, Read v) => Read (Edge v e) Source #  
(Show e, Show v) => Show (Edge v e) Source #  
Generic (Edge v e) Source #  
(Arbitrary v, Arbitrary e, Num v, Ord v) => Arbitrary (Edge v e) Source #  
(NFData v, NFData e) => NFData (Edge v e) Source #  
type Rep (Edge v e) Source #  
Directed Arc with attribute of type e between to Vertices of type v
Arc v v e 
IsEdge Arc Source #  
Functor (Arc v) Source #  
(Eq v, Eq a) => Eq (Arc v a) Source #  Two 
(Ord e, Ord v) => Ord (Arc v e) Source #  
(Read e, Read v) => Read (Arc v e) Source #  
(Show e, Show v) => Show (Arc v e) Source #  
Generic (Arc v e) Source #  
(Arbitrary v, Arbitrary e, Num v, Ord v) => Arbitrary (Arc v e) Source #  
(NFData v, NFData e) => NFData (Arc v e) Source #  
type Rep (Arc v e) Source #  
(<>) :: Hashable v => v > v > Edge v () Source #
Construct an attributeless undirected Edge
between two vertices
(>) :: Hashable v => v > v > Arc v () Source #
Construct an attributeless directed Arc
between two vertices
arbitraryEdge :: (Arbitrary v, Arbitrary e, Ord v, Num v) => (v > v > e > edge) > Gen edge Source #
Edges generator
Triples convenience functions
tripleToPair :: (a, b, c) > (a, b) Source #
Convert a triple to a pair by ignoring the third element
pairToTriple :: (a, b) > (a, b, ()) Source #
Convert a pair to a triple where the 3rd element is unit
tripleOriginVertex :: (v, v, e) > v Source #
Get the origin vertex from an edge triple
tripleDestVertex :: (v, v, e) > v Source #
Get the destination vertex from an edge triple
tripleAttribute :: (v, v, e) > e Source #
Get the attribute from an edge triple