Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

- class Graph g 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 IsEdge e where
- class Weighted a where
- class Labeled a where
- arbitraryEdge :: (Arbitrary v, Arbitrary e, Ord v, Num v) => (v -> v -> e -> edge) -> Gen edge
- type Links v e = HashMap v e
- insertLink :: (Hashable v, Eq v) => v -> a -> Links v a -> Links v a
- getLinks :: (Hashable v, Eq v) => v -> HashMap v (Links v e) -> Links v e
- linksToArcs :: [(v, Links v a)] -> [Arc v a]
- linksToEdges :: [(v, Links v a)] -> [Edge v a]
- linksToEdges' :: Eq v => (v, Links v a) -> [Edge v a]
- hashMapInsert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v

# Documentation

empty, order, vertices, edgePairs, containsVertex, areAdjacent, adjacentVertices, directlyReachableVertices, vertexDegree, insertVertex, containsEdgePair, incidentEdgePairs, insertEdgePair, removeVertex, removeEdgePair, isSimple, fromAdjacencyMatrix, toAdjacencyMatrix

empty :: Hashable v => g v e Source #

The Empty (order-zero) 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

vertices :: g v e -> [v] Source #

Retrieve the vertices of a graph

edgePairs :: (Hashable v, Eq v) => g v e -> [(v, v)] Source #

Retrieve the edges of a graph

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

directlyReachableVertices :: (Hashable v, Eq v) => g v e -> v -> [v] Source #

Retrieve the vertices that are directly reachable from a particular
| vertex.
| A vertex is `directly reachable`

to other if there is an edge that
| connects `from`

one vertex `to`

the other
| Every vertex is directly reachable from itself

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

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

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

incidentEdgePairs :: (Hashable v, Eq v) => g v e -> v -> [(v, v)] Source #

Retrieve the incident edges of a vertex

insertEdgePair :: (Hashable v, Eq v) => (v, v) -> g v () -> g v () 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

insertEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> g v () -> g v () Source #

Same as `insertEdgePair`

but 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

fromAdjacencyMatrix :: [[Int]] -> Maybe (g Int ()) Source #

Generate a graph of Int vertices from an adjacency | square matrix

toAdjacencyMatrix :: g v e -> [[Int]] Source #

Get the adjacency matrix representation of a grah

Undirected Edge with attribute of type *e* between to Vertices of type *v*

Edge v v e |

IsEdge Edge Source # | |

(Eq v, Eq a) => Eq (Edge v a) Source # | To |

(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 # | |

(Eq v, Eq a) => Eq (Arc v a) Source # | To |

(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 undirected `Edge`

between two vertices

class Weighted a where Source #

Weighted Edge attributes | Useful for computing some algorithms on graphs

arbitraryEdge :: (Arbitrary v, Arbitrary e, Ord v, Num v) => (v -> v -> e -> edge) -> Gen edge Source #

Edges generator

type Links v e = HashMap v e Source #

Each vertex maps to a `Links`

value so it can poit to other vertices

insertLink :: (Hashable v, Eq v) => v -> a -> Links v a -> Links v a Source #

Insert a link directed to *v* with attribute *a* | If the connnection already exists, the attribute is replaced

getLinks :: (Hashable v, Eq v) => v -> HashMap v (Links v e) -> Links v e Source #

Get the links for a given vertex

linksToArcs :: [(v, Links v a)] -> [Arc v a] Source #

Get `Arc`

s from an association list of vertices and their links

linksToEdges :: [(v, Links v a)] -> [Edge v a] Source #

Get `Edge`

s from an association list of vertices and their links