Data.Graph.Types

Documentation

class Graph g where

Minimal complete definition

empty, order, vertices, edgeTriples, containsVertex, areAdjacent, adjacentVertices', reachableAdjacentVertices', vertexDegree, insertVertex, containsEdgePair, incidentEdgeTriples, edgeTriple, insertEdgeTriple, removeVertex, removeEdgePair, isSimple, union, intersection, join, toList, toAdjacencyMatrix, fromAdjacencyMatrix

Methods

empty :: Hashable v => g v e

The Empty (order-zero) graph with no vertices and no edges

order :: g v e -> Int

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

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

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]

Retrieve the vertices of a graph

edgeTriples :: (Hashable v, Eq v) => g v e -> [(v, v, e)]

Retrieve the edges of a graph

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

Retrieve the edges of a graph, ignoring its attributes

containsVertex :: (Hashable v, Eq v) => g v e -> v -> Bool

Tell if a vertex exists in the graph

areAdjacent :: (Hashable v, Eq v) => g v e -> v -> v -> Bool

Tell if two vertices are adjacent

adjacentVertices :: (Hashable v, Eq v) => g v e -> v -> [v]

Retrieve the adjacent vertices of a vertex

adjacentVertices' :: (Hashable v, Eq v) => g v e -> v -> [(v, v, e)]

Same as adjacentVertices but gives back the connecting edges

reachableAdjacentVertices :: (Hashable v, Eq v) => g v e -> v -> [v]

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)]

Same as reachableAdjacentVertices but gives back the connecting edges

vertexDegree :: (Hashable v, Eq v) => g v e -> v -> Int

Total number of incident edges of a vertex

degrees :: (Hashable v, Eq v) => g v e -> [Int]

Degrees of a all the vertices in a graph

maxDegree :: (Hashable v, Eq v) => g v e -> Int

Maximum degree of a graph

minDegree :: (Hashable v, Eq v) => g v e -> Int

Minimum degree of a graph

avgDegree :: (Hashable v, Eq v) => g v e -> Double

Average degree of a graph

insertVertex :: (Hashable v, Eq v) => v -> g v e -> g v e

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

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

Tell if an edge exists in the graph

incidentEdgeTriples :: (Hashable v, Eq v) => g v e -> v -> [(v, v, e)]

Retrieve the incident edges of a vertex

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

Retrieve the incident edges of a vertex, ignoring its attributes

edgeTriple :: (Hashable v, Eq v) => g v e -> v -> v -> Maybe (v, v, e)

Get the edge between to vertices if it exists

insertEdgeTriple :: (Hashable v, Eq v) => (v, v, e) -> g v e -> g v e

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

Same as insertEdgeTriple but for multiple edges

insertEdgePair :: (Hashable v, Eq v) => (v, v) -> g v () -> g v ()

Same as insertEdgeTriple but insert edge pairs in graphs with | attributeless edges

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

Same as insertEdgePair for multiple edges

removeVertex :: (Hashable v, Eq v) => v -> g v e -> g v e

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

Same as removeVertex but for multiple vertices

removeEdgePair :: (Hashable v, Eq v) => (v, v) -> g v e -> g v e

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

Same as removeEdgePair but for multple edges

removeEdgePairAndVertices :: (Hashable v, Eq v) => (v, v) -> g v e -> g v e

Remove the edge from a graph if present | The involved vertices are also removed

isSimple :: (Hashable v, Eq v) => g v e -> Bool

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

Union of two graphs

intersection :: g v e -> g v e -> g v e

Intersection of two graphs

join :: g v e -> g v e -> g v e

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)])]

Convert a graph to an adjacency list with edge attributes in e

fromList :: (Hashable v, Eq v) => [(v, [(v, e)])] -> g v e

Construct a graph from an adjacency list with edge attributes in e

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

Get the adjacency binary matrix representation of a grah

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

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

Instances

Graph UGraph

Methods

empty :: Hashable v => UGraph v e

order :: UGraph v e -> Int

size :: (Hashable v, Eq v) => UGraph v e -> Int

density :: (Hashable v, Eq v) => UGraph v e -> Double

vertices :: UGraph v e -> [v]

edgeTriples :: (Hashable v, Eq v) => UGraph v e -> [(v, v, e)]

edgePairs :: (Hashable v, Eq v) => UGraph v e -> [(v, v)]

containsVertex :: (Hashable v, Eq v) => UGraph v e -> v -> Bool

areAdjacent :: (Hashable v, Eq v) => UGraph v e -> v -> v -> Bool

adjacentVertices :: (Hashable v, Eq v) => UGraph v e -> v -> [v]

adjacentVertices' :: (Hashable v, Eq v) => UGraph v e -> v -> [(v, v, e)]

reachableAdjacentVertices :: (Hashable v, Eq v) => UGraph v e -> v -> [v]

reachableAdjacentVertices' :: (Hashable v, Eq v) => UGraph v e -> v -> [(v, v, e)]

vertexDegree :: (Hashable v, Eq v) => UGraph v e -> v -> Int

degrees :: (Hashable v, Eq v) => UGraph v e -> [Int]

maxDegree :: (Hashable v, Eq v) => UGraph v e -> Int

minDegree :: (Hashable v, Eq v) => UGraph v e -> Int

avgDegree :: (Hashable v, Eq v) => UGraph v e -> Double

insertVertex :: (Hashable v, Eq v) => v -> UGraph v e -> UGraph v e

insertVertices :: (Hashable v, Eq v) => [v] -> UGraph v e -> UGraph v e

containsEdgePair :: (Hashable v, Eq v) => UGraph v e -> (v, v) -> Bool

incidentEdgeTriples :: (Hashable v, Eq v) => UGraph v e -> v -> [(v, v, e)]

incidentEdgePairs :: (Hashable v, Eq v) => UGraph v e -> v -> [(v, v)]

edgeTriple :: (Hashable v, Eq v) => UGraph v e -> v -> v -> Maybe (v, v, e)

insertEdgeTriple :: (Hashable v, Eq v) => (v, v, e) -> UGraph v e -> UGraph v e

insertEdgeTriples :: (Hashable v, Eq v) => [(v, v, e)] -> UGraph v e -> UGraph v e

insertEdgePair :: (Hashable v, Eq v) => (v, v) -> UGraph v () -> UGraph v ()

insertEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> UGraph v () -> UGraph v ()

removeVertex :: (Hashable v, Eq v) => v -> UGraph v e -> UGraph v e

removeVertices :: (Hashable v, Eq v) => [v] -> UGraph v e -> UGraph v e

removeEdgePair :: (Hashable v, Eq v) => (v, v) -> UGraph v e -> UGraph v e

removeEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> UGraph v e -> UGraph v e

removeEdgePairAndVertices :: (Hashable v, Eq v) => (v, v) -> UGraph v e -> UGraph v e

isSimple :: (Hashable v, Eq v) => UGraph v e -> Bool

union :: UGraph v e -> UGraph v e -> UGraph v e

intersection :: UGraph v e -> UGraph v e -> UGraph v e

join :: UGraph v e -> UGraph v e -> UGraph v e

toList :: (Hashable v, Eq v) => UGraph v e -> [(v, [(v, e)])]

fromList :: (Hashable v, Eq v) => [(v, [(v, e)])] -> UGraph v e

toAdjacencyMatrix :: UGraph v e -> [[Int]]

fromAdjacencyMatrix :: [[Int]] -> Maybe (UGraph Int ())

Graph DGraph

Methods

empty :: Hashable v => DGraph v e

order :: DGraph v e -> Int

size :: (Hashable v, Eq v) => DGraph v e -> Int

density :: (Hashable v, Eq v) => DGraph v e -> Double

vertices :: DGraph v e -> [v]

edgeTriples :: (Hashable v, Eq v) => DGraph v e -> [(v, v, e)]

edgePairs :: (Hashable v, Eq v) => DGraph v e -> [(v, v)]

containsVertex :: (Hashable v, Eq v) => DGraph v e -> v -> Bool

areAdjacent :: (Hashable v, Eq v) => DGraph v e -> v -> v -> Bool

adjacentVertices :: (Hashable v, Eq v) => DGraph v e -> v -> [v]

adjacentVertices' :: (Hashable v, Eq v) => DGraph v e -> v -> [(v, v, e)]

reachableAdjacentVertices :: (Hashable v, Eq v) => DGraph v e -> v -> [v]

reachableAdjacentVertices' :: (Hashable v, Eq v) => DGraph v e -> v -> [(v, v, e)]

vertexDegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int

degrees :: (Hashable v, Eq v) => DGraph v e -> [Int]

maxDegree :: (Hashable v, Eq v) => DGraph v e -> Int

minDegree :: (Hashable v, Eq v) => DGraph v e -> Int

avgDegree :: (Hashable v, Eq v) => DGraph v e -> Double

insertVertex :: (Hashable v, Eq v) => v -> DGraph v e -> DGraph v e

insertVertices :: (Hashable v, Eq v) => [v] -> DGraph v e -> DGraph v e

containsEdgePair :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> Bool

incidentEdgeTriples :: (Hashable v, Eq v) => DGraph v e -> v -> [(v, v, e)]

incidentEdgePairs :: (Hashable v, Eq v) => DGraph v e -> v -> [(v, v)]

edgeTriple :: (Hashable v, Eq v) => DGraph v e -> v -> v -> Maybe (v, v, e)

insertEdgeTriple :: (Hashable v, Eq v) => (v, v, e) -> DGraph v e -> DGraph v e

insertEdgeTriples :: (Hashable v, Eq v) => [(v, v, e)] -> DGraph v e -> DGraph v e

insertEdgePair :: (Hashable v, Eq v) => (v, v) -> DGraph v () -> DGraph v ()

insertEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> DGraph v () -> DGraph v ()

removeVertex :: (Hashable v, Eq v) => v -> DGraph v e -> DGraph v e

removeVertices :: (Hashable v, Eq v) => [v] -> DGraph v e -> DGraph v e

removeEdgePair :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> DGraph v e

removeEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> DGraph v e -> DGraph v e

removeEdgePairAndVertices :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> DGraph v e

isSimple :: (Hashable v, Eq v) => DGraph v e -> Bool

union :: DGraph v e -> DGraph v e -> DGraph v e

intersection :: DGraph v e -> DGraph v e -> DGraph v e

join :: DGraph v e -> DGraph v e -> DGraph v e

toList :: (Hashable v, Eq v) => DGraph v e -> [(v, [(v, e)])]

fromList :: (Hashable v, Eq v) => [(v, [(v, e)])] -> DGraph v e

toAdjacencyMatrix :: DGraph v e -> [[Int]]

fromAdjacencyMatrix :: [[Int]] -> Maybe (DGraph Int ())

data Edge v e

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

Constructors

Edge v v e

Instances

IsEdge Edge

Methods

originVertex :: Edge v a -> v

destinationVertex :: Edge v a -> v

attribute :: Edge v a -> a

toPair :: Edge v a -> (v, v)

fromPair :: (v, v) -> Edge v ()

toTriple :: Edge v a -> (v, v, a)

fromTriple :: (v, v, a) -> Edge v a

isLoop :: Eq v => Edge v a -> Bool

(Eq v, Eq a) => Eq (Edge v a)

To Edges 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)

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)

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)

Methods

showsPrec :: Int -> Edge v e -> ShowS

show :: Edge v e -> String

showList :: [Edge v e] -> ShowS

Generic (Edge v e)

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)

Methods

arbitrary :: Gen (Edge v e)

shrink :: Edge v e -> [Edge v e]

(NFData v, NFData e) => NFData (Edge v e)

Methods

rnf :: Edge v e -> ()

type Rep (Edge v e)

type Rep (Edge v e) = D1 (MetaData "Edge" "Data.Graph.Types" "graphite-0.9.0.0-JMxBWTsM0Ut3rTUv0zEQzn" 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

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

Constructors

Arc v v e

Instances

IsEdge Arc

Methods

originVertex :: Arc v a -> v

destinationVertex :: Arc v a -> v

attribute :: Arc v a -> a

toPair :: Arc v a -> (v, v)

fromPair :: (v, v) -> Arc v ()

toTriple :: Arc v a -> (v, v, a)

fromTriple :: (v, v, a) -> Arc v a

isLoop :: Eq v => Arc v a -> Bool

(Eq v, Eq a) => Eq (Arc v a)

To Arcs 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)

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)

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)

Methods

showsPrec :: Int -> Arc v e -> ShowS

show :: Arc v e -> String

showList :: [Arc v e] -> ShowS

Generic (Arc v e)

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)

Methods

arbitrary :: Gen (Arc v e)

shrink :: Arc v e -> [Arc v e]

(NFData v, NFData e) => NFData (Arc v e)

Methods

rnf :: Arc v e -> ()

type Rep (Arc v e)

type Rep (Arc v e) = D1 (MetaData "Arc" "Data.Graph.Types" "graphite-0.9.0.0-JMxBWTsM0Ut3rTUv0zEQzn" 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 ()

Construct an attributeless undirected Edge between two vertices

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

Construct an attributeless directed Arc between two vertices

class IsEdge e where

Minimal complete definition

originVertex, destinationVertex, attribute, toPair, fromPair, toTriple, fromTriple, isLoop

Methods

originVertex :: e v a -> v

Retrieve the origin vertex of the edge

destinationVertex :: e v a -> v

Retrieve the destination vertex of the edge

attribute :: e v a -> a

Retrieve the attribute of the edge

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

Convert an edge to a pair discarding its attribute

fromPair :: (v, v) -> e v ()

Convert a pair to an edge, where it's attribute is unit

toTriple :: e v a -> (v, v, a)

Convert an edge to a triple, where the 3rd element it's the edge | attribute

fromTriple :: (v, v, a) -> e v a

Convert a triple to an edge

isLoop :: Eq v => e v a -> Bool

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

Methods

originVertex :: Arc v a -> v

destinationVertex :: Arc v a -> v

attribute :: Arc v a -> a

toPair :: Arc v a -> (v, v)

fromPair :: (v, v) -> Arc v ()

toTriple :: Arc v a -> (v, v, a)

fromTriple :: (v, v, a) -> Arc v a

isLoop :: Eq v => Arc v a -> Bool

IsEdge Edge

Methods

originVertex :: Edge v a -> v

destinationVertex :: Edge v a -> v

attribute :: Edge v a -> a

toPair :: Edge v a -> (v, v)

fromPair :: (v, v) -> Edge v ()

toTriple :: Edge v a -> (v, v, a)

fromTriple :: (v, v, a) -> Edge v a

isLoop :: Eq v => Edge v a -> Bool

class Weighted a where

Weighted Edge attributes | Useful for computing some algorithms on graphs

Minimal complete definition

weight

Methods

weight :: a -> Double

Instances

Weighted Double

Methods

weight :: Double -> Double

Weighted Float

Methods

weight :: Float -> Double

Weighted Int

Methods

weight :: Int -> Double

Weighted (Double, String)

Methods

weight :: (Double, String) -> Double

class Labeled a where

Labeled Edge attributes | Useful for graph plotting

Minimal complete definition

label

Methods

label :: a -> String

Instances

Labeled String

Methods

label :: String -> String

Labeled (Double, String)

Methods

label :: (Double, String) -> String

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

Edges generator

Triples convenience functions

tripleToPair :: (a, b, c) -> (a, b)

Convert a triple to a pair by ignoring the third element

pairToTriple :: (a, b) -> (a, b, ())

Convert a pair to a triple where the 3rd element is unit

tripleOriginVertex :: (v, v, e) -> v

Get the origin vertex from an edge triple

tripleDestVertex :: (v, v, e) -> v

Get the destination vertex from an edge triple

tripleAttribute :: (v, v, e) -> e

Get the attribute from an edge triple

type Links v e = HashMap v e

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

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

Get the links for a given vertex

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

Get Arcs from an association list of vertices and their links

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

Get Edges from an association list of vertices and their links

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

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.