Safe Haskell	Safe
Language	Haskell2010

Data.Graph.Types

Synopsis

Documentation

class Graph g where Source #

Minimal complete definition

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

Methods

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

Instances

Graph UGraph Source #
Methods empty :: Hashable v => UGraph v e Source # order :: UGraph v e -> Int Source # size :: (Hashable v, Eq v) => UGraph v e -> Int Source # vertices :: UGraph v e -> [v] Source # edgePairs :: (Hashable v, Eq v) => UGraph v e -> [(v, v)] Source # containsVertex :: (Hashable v, Eq v) => UGraph v e -> v -> Bool Source # areAdjacent :: (Hashable v, Eq v) => UGraph v e -> v -> v -> Bool Source # adjacentVertices :: (Hashable v, Eq v) => UGraph v e -> v -> [v] Source # directlyReachableVertices :: (Hashable v, Eq v) => UGraph v e -> v -> [v] Source # vertexDegree :: (Hashable v, Eq v) => UGraph v e -> v -> Int Source # degrees :: (Hashable v, Eq v) => UGraph v e -> [Int] Source # maxDegree :: (Hashable v, Eq v) => UGraph v e -> Int Source # minDegree :: (Hashable v, Eq v) => UGraph v e -> Int Source # avgDegree :: (Hashable v, Eq v) => UGraph v e -> Double Source # density :: (Hashable v, Eq v) => UGraph v e -> Double Source # insertVertex :: (Hashable v, Eq v) => v -> UGraph v e -> UGraph v e Source # insertVertices :: (Hashable v, Eq v) => [v] -> UGraph v e -> UGraph v e Source # containsEdgePair :: (Hashable v, Eq v) => UGraph v e -> (v, v) -> Bool Source # incidentEdgePairs :: (Hashable v, Eq v) => UGraph v e -> v -> [(v, v)] Source # insertEdgePair :: (Hashable v, Eq v) => (v, v) -> UGraph v () -> UGraph v () Source # insertEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> UGraph v () -> UGraph v () Source # removeVertex :: (Hashable v, Eq v) => v -> UGraph v e -> UGraph v e Source # removeVertices :: (Hashable v, Eq v) => [v] -> UGraph v e -> UGraph v e Source # removeEdgePair :: (Hashable v, Eq v) => (v, v) -> UGraph v e -> UGraph v e Source # removeEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> UGraph v e -> UGraph v e Source # removeEdgePairAndVertices :: (Hashable v, Eq v) => (v, v) -> UGraph v e -> UGraph v e Source # isSimple :: (Hashable v, Eq v) => UGraph v e -> Bool Source # fromAdjacencyMatrix :: [[Int]] -> Maybe (UGraph Int ()) Source # toAdjacencyMatrix :: UGraph v e -> [[Int]] Source #
Graph DGraph Source #
Methods empty :: Hashable v => DGraph v e Source # order :: DGraph v e -> Int Source # size :: (Hashable v, Eq v) => DGraph v e -> Int Source # vertices :: DGraph v e -> [v] Source # edgePairs :: (Hashable v, Eq v) => DGraph v e -> [(v, v)] Source # containsVertex :: (Hashable v, Eq v) => DGraph v e -> v -> Bool Source # areAdjacent :: (Hashable v, Eq v) => DGraph v e -> v -> v -> Bool Source # adjacentVertices :: (Hashable v, Eq v) => DGraph v e -> v -> [v] Source # directlyReachableVertices :: (Hashable v, Eq v) => DGraph v e -> v -> [v] Source # vertexDegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int Source # degrees :: (Hashable v, Eq v) => DGraph v e -> [Int] Source # maxDegree :: (Hashable v, Eq v) => DGraph v e -> Int Source # minDegree :: (Hashable v, Eq v) => DGraph v e -> Int Source # avgDegree :: (Hashable v, Eq v) => DGraph v e -> Double Source # density :: (Hashable v, Eq v) => DGraph v e -> Double Source # insertVertex :: (Hashable v, Eq v) => v -> DGraph v e -> DGraph v e Source # insertVertices :: (Hashable v, Eq v) => [v] -> DGraph v e -> DGraph v e Source # containsEdgePair :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> Bool Source # incidentEdgePairs :: (Hashable v, Eq v) => DGraph v e -> v -> [(v, v)] Source # insertEdgePair :: (Hashable v, Eq v) => (v, v) -> DGraph v () -> DGraph v () Source # insertEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> DGraph v () -> DGraph v () Source # removeVertex :: (Hashable v, Eq v) => v -> DGraph v e -> DGraph v e Source # removeVertices :: (Hashable v, Eq v) => [v] -> DGraph v e -> DGraph v e Source # removeEdgePair :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> DGraph v e Source # removeEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> DGraph v e -> DGraph v e Source # removeEdgePairAndVertices :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> DGraph v e Source # isSimple :: (Hashable v, Eq v) => DGraph v e -> Bool Source # fromAdjacencyMatrix :: [[Int]] -> Maybe (DGraph Int ()) Source # toAdjacencyMatrix :: DGraph v e -> [[Int]] Source #

data Edge v e Source #

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

Constructors

Edge v v e

Instances

IsEdge Edge Source #
Methods toPair :: Edge v a -> (v, v) Source # isLoop :: Eq v => Edge v a -> Bool Source #
(Eq v, Eq a) => Eq (Edge v a) Source #	To `Edge`s are equal if they point to the same vertices, regardless of the \| direction
Methods (==) :: Edge v a -> Edge v a -> Bool # (/=) :: Edge v a -> Edge v a -> Bool #
(Ord e, Ord v) => Ord (Edge v e) Source #
Methods compare :: Edge v e -> Edge v e -> Ordering # (<) :: Edge v e -> Edge v e -> Bool # (<=) :: Edge v e -> Edge v e -> Bool # (>) :: Edge v e -> Edge v e -> Bool # (>=) :: Edge v e -> Edge v e -> Bool # max :: Edge v e -> Edge v e -> Edge v e # min :: Edge v e -> Edge v e -> Edge v e #
(Read e, Read v) => Read (Edge v e) Source #
Methods readsPrec :: Int -> ReadS (Edge v e) # readList :: ReadS [Edge v e] # readPrec :: ReadPrec (Edge v e) # readListPrec :: ReadPrec [Edge v e] #
(Show e, Show v) => Show (Edge v e) Source #
Methods showsPrec :: Int -> Edge v e -> ShowS # show :: Edge v e -> String # showList :: [Edge v e] -> ShowS #
Generic (Edge v e) Source #
Associated Types type Rep (Edge v e) :: * -> * # Methods from :: Edge v e -> Rep (Edge v e) x # to :: Rep (Edge v e) x -> Edge v e #
(Arbitrary v, Arbitrary e, Num v, Ord v) => Arbitrary (Edge v e) Source #
Methods arbitrary :: Gen (Edge v e) # shrink :: Edge v e -> [Edge v e] #
(NFData v, NFData e) => NFData (Edge v e) Source #
Methods rnf :: Edge v e -> () #
type Rep (Edge v e) Source #
type Rep (Edge v e) = D1 (MetaData "Edge" "Data.Graph.Types" "graphite-0.5.0.0-5I7pH1sVUJTG7Ml6swiWg4" False) (C1 (MetaCons "Edge" PrefixI False) ((::) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 v)) ((::) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 v)) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 e)))))

data Arc v e Source #

Directed Arc with attribute of type e between to Vertices of type v

Constructors

Arc v v e

Instances

IsEdge Arc Source #
Methods toPair :: Arc v a -> (v, v) Source # isLoop :: Eq v => Arc v a -> Bool Source #
(Eq v, Eq a) => Eq (Arc v a) Source #	To `Arc`s are equal if they point to the same vertices, and the directions \| is the same
Methods (==) :: Arc v a -> Arc v a -> Bool # (/=) :: Arc v a -> Arc v a -> Bool #
(Ord e, Ord v) => Ord (Arc v e) Source #
Methods compare :: Arc v e -> Arc v e -> Ordering # (<) :: Arc v e -> Arc v e -> Bool # (<=) :: Arc v e -> Arc v e -> Bool # (>) :: Arc v e -> Arc v e -> Bool # (>=) :: Arc v e -> Arc v e -> Bool # max :: Arc v e -> Arc v e -> Arc v e # min :: Arc v e -> Arc v e -> Arc v e #
(Read e, Read v) => Read (Arc v e) Source #
Methods readsPrec :: Int -> ReadS (Arc v e) # readList :: ReadS [Arc v e] # readPrec :: ReadPrec (Arc v e) # readListPrec :: ReadPrec [Arc v e] #
(Show e, Show v) => Show (Arc v e) Source #
Methods showsPrec :: Int -> Arc v e -> ShowS # show :: Arc v e -> String # showList :: [Arc v e] -> ShowS #
Generic (Arc v e) Source #
Associated Types type Rep (Arc v e) :: * -> * # Methods from :: Arc v e -> Rep (Arc v e) x # to :: Rep (Arc v e) x -> Arc v e #
(Arbitrary v, Arbitrary e, Num v, Ord v) => Arbitrary (Arc v e) Source #
Methods arbitrary :: Gen (Arc v e) # shrink :: Arc v e -> [Arc v e] #
(NFData v, NFData e) => NFData (Arc v e) Source #
Methods rnf :: Arc v e -> () #
type Rep (Arc v e) Source #
type Rep (Arc v e) = D1 (MetaData "Arc" "Data.Graph.Types" "graphite-0.5.0.0-5I7pH1sVUJTG7Ml6swiWg4" False) (C1 (MetaCons "Arc" PrefixI False) ((::) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 v)) ((::) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 v)) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 e)))))

(<->) :: Hashable v => v -> v -> Edge v () Source #

Construct an undirected Edge between two vertices

(-->) :: Hashable v => v -> v -> Arc v () Source #

Construct a directed Arc between two vertices

class IsEdge e where Source #

Minimal complete definition

toPair, isLoop

Methods

toPair :: e v a -> (v, v) Source #

Convert an edge to a pair discargind its attribute

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

Instances

IsEdge Arc Source #
Methods toPair :: Arc v a -> (v, v) Source # isLoop :: Eq v => Arc v a -> Bool Source #
IsEdge Edge Source #
Methods toPair :: Edge v a -> (v, v) Source # isLoop :: Eq v => Edge v a -> Bool Source #

class Weighted a where Source #

Weighted Edge attributes | Useful for computing some algorithms on graphs

Minimal complete definition

weight

Methods

weight :: a -> Double Source #

Instances

Weighted Double Source #
Methods weight :: Double -> Double Source #
Weighted Float Source #
Methods weight :: Float -> Double Source #
Weighted Int Source #
Methods weight :: Int -> Double Source #
Weighted (Double, String) Source #
Methods weight :: (Double, String) -> Double Source #

class Labeled a where Source #

Labeled Edge attributes | Useful for graph plotting

Minimal complete definition

label

Methods

label :: a -> String Source #

Instances

Labeled String Source #
Methods label :: String -> String Source #
Labeled (Double, String) Source #
Methods label :: (Double, String) -> String Source #

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 Arcs from an association list of vertices and their links

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

Get Edges from an association list of vertices and their links

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

Get Edges from an association list of vertices and their links

hashMapInsert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v Source #

O(log n) Associate the specified value with the specified key in this map. | If this map previously contained a mapping for the key, leave the map | intact.