Data.Graph.Types

Main Graph type class

class Graph g where

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 graph-directionality agnostic, otherwise use the more specific ones in UGraph and DGraph

Minimal complete definition

empty, order, vertices, edgeTriples, containsVertex, adjacentVertices', reachableAdjacentVertices', vertexDegree, insertVertex, containsEdgePair, incidentEdgeTriples, edgeTriple, insertEdgeTriple, removeVertex, removeEdgePair, isSimple, union, intersection, toList, 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 density of a graph is the ratio of the number of existing edges to the number of posible edges

vertices :: g v e -> [v]

Retrieve all 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 it untouched

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

Insert 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 gets 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 attribute less 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 also gets 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 multiple 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 also get removed

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

Retrieve the isolated vertices of a graph, if any

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

Union of two graphs

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

Intersection of two graphs

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

Convert a graph to an adjacency list with vertices in type v and edge attributes in e

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

Construct a graph from an adjacency list with vertices in type /v and edge attributes in e

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

Get the adjacency binary matrix representation of a graph toAdjacencyMatrix :: g v e -> [[Int]]

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

Instances

Graph UGraph

Defined in Data.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

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

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

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

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

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

Graph DGraph

Defined in Data.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

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

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

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

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

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

Edges type class

class IsEdge e where

Types that represent edges

The main IsEdge instances are Edge for undirected edges and Arc for directed edges.

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

Defined in Data.Graph.Types

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

Defined in Data.Graph.Types

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

Main IsEdge instances

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

Defined in Data.Graph.Types

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

Functor (Edge v)

Defined in Data.Graph.Types

Methods

fmap :: (a -> b) -> Edge v a -> Edge v b

(<$) :: a -> Edge v b -> Edge v a

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

Two Edges are equal if they point to the same vertices, regardless of the direction

Defined in Data.Graph.Types

Methods

(==) :: Edge v a -> Edge v a -> Bool

(/=) :: Edge v a -> Edge v a -> Bool

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

Defined in Data.Graph.Types

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 v, Read e) => Read (Edge v e)

Defined in Data.Graph.Types

Methods

readsPrec :: Int -> ReadS (Edge v e)

readList :: ReadS [Edge v e]

readPrec :: ReadPrec (Edge v e)

readListPrec :: ReadPrec [Edge v e]

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

Defined in Data.Graph.Types

Methods

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

show :: Edge v e -> String

showList :: [Edge v e] -> ShowS

Generic (Edge v e)

Defined in Data.Graph.Types

Associated Types

type Rep (Edge v e) :: Type -> Type

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)

Defined in Data.Graph.Types

Methods

arbitrary :: Gen (Edge v e)

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

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

Defined in Data.Graph.Types

Methods

rnf :: Edge v e -> ()

type Rep (Edge v e)

Defined in Data.Graph.Types

type Rep (Edge v e) = D1 (MetaData "Edge" "Data.Graph.Types" "graphite-0.10.0.1-HhXsvYnwz7AHqOTrhvfKfJ" False) (C1 (MetaCons "Edge" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 v) :*: (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 v) :*: S1 (MetaSel (Nothing :: Maybe 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

Defined in Data.Graph.Types

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

Functor (Arc v)

Defined in Data.Graph.Types

Methods

fmap :: (a -> b) -> Arc v a -> Arc v b

(<$) :: a -> Arc v b -> Arc v a

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

Two Arcs are equal if they point to the same vertices, and the directions are the same

Defined in Data.Graph.Types

Methods

(==) :: Arc v a -> Arc v a -> Bool

(/=) :: Arc v a -> Arc v a -> Bool

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

Defined in Data.Graph.Types

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 v, Read e) => Read (Arc v e)

Defined in Data.Graph.Types

Methods

readsPrec :: Int -> ReadS (Arc v e)

readList :: ReadS [Arc v e]

readPrec :: ReadPrec (Arc v e)

readListPrec :: ReadPrec [Arc v e]

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

Defined in Data.Graph.Types

Methods

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

show :: Arc v e -> String

showList :: [Arc v e] -> ShowS

Generic (Arc v e)

Defined in Data.Graph.Types

Associated Types

type Rep (Arc v e) :: Type -> Type

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)

Defined in Data.Graph.Types

Methods

arbitrary :: Gen (Arc v e)

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

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

Defined in Data.Graph.Types

Methods

rnf :: Arc v e -> ()

type Rep (Arc v e)

Defined in Data.Graph.Types

type Rep (Arc v e) = D1 (MetaData "Arc" "Data.Graph.Types" "graphite-0.10.0.1-HhXsvYnwz7AHqOTrhvfKfJ" False) (C1 (MetaCons "Arc" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 v) :*: (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 v) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 e))))

Edges and Arcs constructors

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

Construct an attribute less undirected Edge between two vertices

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

Construct an attribute less directed Arc between two vertices

Edge attributes type clases

class Weighted e where

Edge attributes that represent weights

Methods

weight :: e -> Double

Instances

Weighted Double

Defined in Data.Graph.Types

Methods

weight :: Double -> Double

Weighted Float

Defined in Data.Graph.Types

Methods

weight :: Float -> Double

Weighted Int

Defined in Data.Graph.Types

Methods

weight :: Int -> Double

Weighted (Double, String)

Defined in Data.Graph.Types

Methods

weight :: (Double, String) -> Double

class Labeled e where

Edge attributes that represent labels

Methods

label :: e -> String

Instances

Labeled String

Defined in Data.Graph.Types

Methods

label :: String -> String

Labeled (Double, String)

Defined in Data.Graph.Types

Methods

label :: (Double, String) -> String

Triple-Edges 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