Data.Graph.Comfort

types

data Graph edge node edgeLabel nodeLabel

Instances

(Eq nodeLabel, Eq edgeLabel, Eq node, Eq1 edge) => Eq (Graph edge node edgeLabel nodeLabel)

Methods

(==) :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Bool

(/=) :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Bool

(Ord nodeLabel, Ord edgeLabel, Ord node, Ord1 edge) => Ord (Graph edge node edgeLabel nodeLabel)

Methods

compare :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Ordering

(<) :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Bool

(<=) :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Bool

(>) :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Bool

(>=) :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Bool

max :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel

min :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel

(Edge e, Ord n, Show1 e, Show n, Show el, Show nl) => Show (Graph e n el nl)

Methods

showsPrec :: Int -> Graph e n el nl -> ShowS

show :: Graph e n el nl -> String

showList :: [Graph e n el nl] -> ShowS

(Edge edge, Ord node) => Monoid (Graph edge node edgeLabel nodeLabel)

Methods

mempty :: Graph edge node edgeLabel nodeLabel

mappend :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel

mconcat :: [Graph edge node edgeLabel nodeLabel] -> Graph edge node edgeLabel nodeLabel

type LabeledNode n label = (n, label)

type LabeledEdge edge node label = (edge node, label)

class (Foldable edge, Ord1 edge) => Edge edge where

Minimal complete definition

from, to

Methods

from, to :: edge node -> node

Instances

Edge EitherEdge

Methods

from :: EitherEdge node -> node

to :: EitherEdge node -> node

Edge UndirEdge

Methods

from :: UndirEdge node -> node

to :: UndirEdge node -> node

Edge DirEdge

Methods

from :: DirEdge node -> node

to :: DirEdge node -> node

defaultEdgeFoldMap :: (Edge edge, Monoid a) => edge a -> a

data DirEdge node

Constructors

DirEdge node node

Instances

Functor DirEdge

Methods

fmap :: (a -> b) -> DirEdge a -> DirEdge b

(<$) :: a -> DirEdge b -> DirEdge a

Foldable DirEdge

Methods

fold :: Monoid m => DirEdge m -> m

foldMap :: Monoid m => (a -> m) -> DirEdge a -> m

foldr :: (a -> b -> b) -> b -> DirEdge a -> b

foldr' :: (a -> b -> b) -> b -> DirEdge a -> b

foldl :: (b -> a -> b) -> b -> DirEdge a -> b

foldl' :: (b -> a -> b) -> b -> DirEdge a -> b

foldr1 :: (a -> a -> a) -> DirEdge a -> a

foldl1 :: (a -> a -> a) -> DirEdge a -> a

toList :: DirEdge a -> [a]

null :: DirEdge a -> Bool

length :: DirEdge a -> Int

elem :: Eq a => a -> DirEdge a -> Bool

maximum :: Ord a => DirEdge a -> a

minimum :: Ord a => DirEdge a -> a

sum :: Num a => DirEdge a -> a

product :: Num a => DirEdge a -> a

Eq1 DirEdge

Methods

liftEq :: (a -> b -> Bool) -> DirEdge a -> DirEdge b -> Bool

Ord1 DirEdge

Methods

liftCompare :: (a -> b -> Ordering) -> DirEdge a -> DirEdge b -> Ordering

Show1 DirEdge

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> DirEdge a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [DirEdge a] -> ShowS

Reverse DirEdge

Methods

reverseEdge :: DirEdge node -> DirEdge node

Edge DirEdge

Methods

from :: DirEdge node -> node

to :: DirEdge node -> node

Eq node => Eq (DirEdge node)

Methods

(==) :: DirEdge node -> DirEdge node -> Bool

(/=) :: DirEdge node -> DirEdge node -> Bool

Ord node => Ord (DirEdge node)

Methods

compare :: DirEdge node -> DirEdge node -> Ordering

(<) :: DirEdge node -> DirEdge node -> Bool

(<=) :: DirEdge node -> DirEdge node -> Bool

(>) :: DirEdge node -> DirEdge node -> Bool

(>=) :: DirEdge node -> DirEdge node -> Bool

max :: DirEdge node -> DirEdge node -> DirEdge node

min :: DirEdge node -> DirEdge node -> DirEdge node

Show node => Show (DirEdge node)

Methods

showsPrec :: Int -> DirEdge node -> ShowS

show :: DirEdge node -> String

showList :: [DirEdge node] -> ShowS

Arbitrary n => Arbitrary (DirEdge n)

Methods

arbitrary :: Gen (DirEdge n)

shrink :: DirEdge n -> [DirEdge n]

data UndirEdge node

Constructors

UndirEdge node node

Instances

Foldable UndirEdge

Methods

fold :: Monoid m => UndirEdge m -> m

foldMap :: Monoid m => (a -> m) -> UndirEdge a -> m

foldr :: (a -> b -> b) -> b -> UndirEdge a -> b

foldr' :: (a -> b -> b) -> b -> UndirEdge a -> b

foldl :: (b -> a -> b) -> b -> UndirEdge a -> b

foldl' :: (b -> a -> b) -> b -> UndirEdge a -> b

foldr1 :: (a -> a -> a) -> UndirEdge a -> a

foldl1 :: (a -> a -> a) -> UndirEdge a -> a

toList :: UndirEdge a -> [a]

null :: UndirEdge a -> Bool

length :: UndirEdge a -> Int

elem :: Eq a => a -> UndirEdge a -> Bool

maximum :: Ord a => UndirEdge a -> a

minimum :: Ord a => UndirEdge a -> a

sum :: Num a => UndirEdge a -> a

product :: Num a => UndirEdge a -> a

Eq1 UndirEdge

Methods

liftEq :: (a -> b -> Bool) -> UndirEdge a -> UndirEdge b -> Bool

Ord1 UndirEdge

Methods

liftCompare :: (a -> b -> Ordering) -> UndirEdge a -> UndirEdge b -> Ordering

Show1 UndirEdge

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> UndirEdge a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [UndirEdge a] -> ShowS

Edge UndirEdge

Methods

from :: UndirEdge node -> node

to :: UndirEdge node -> node

Eq node => Eq (UndirEdge node)

Methods

(==) :: UndirEdge node -> UndirEdge node -> Bool

(/=) :: UndirEdge node -> UndirEdge node -> Bool

Ord node => Ord (UndirEdge node)

Methods

compare :: UndirEdge node -> UndirEdge node -> Ordering

(<) :: UndirEdge node -> UndirEdge node -> Bool

(<=) :: UndirEdge node -> UndirEdge node -> Bool

(>) :: UndirEdge node -> UndirEdge node -> Bool

(>=) :: UndirEdge node -> UndirEdge node -> Bool

max :: UndirEdge node -> UndirEdge node -> UndirEdge node

min :: UndirEdge node -> UndirEdge node -> UndirEdge node

Show node => Show (UndirEdge node)

Methods

showsPrec :: Int -> UndirEdge node -> ShowS

show :: UndirEdge node -> String

showList :: [UndirEdge node] -> ShowS

(Arbitrary n, Ord n) => Arbitrary (UndirEdge n)

Methods

arbitrary :: Gen (UndirEdge n)

shrink :: UndirEdge n -> [UndirEdge n]

undirEdge :: Ord node => node -> node -> UndirEdge node

data EitherEdge node

Constructors

EDirEdge (DirEdge node)

EUndirEdge (UndirEdge node)

Instances

Foldable EitherEdge

Methods

fold :: Monoid m => EitherEdge m -> m

foldMap :: Monoid m => (a -> m) -> EitherEdge a -> m

foldr :: (a -> b -> b) -> b -> EitherEdge a -> b

foldr' :: (a -> b -> b) -> b -> EitherEdge a -> b

foldl :: (b -> a -> b) -> b -> EitherEdge a -> b

foldl' :: (b -> a -> b) -> b -> EitherEdge a -> b

foldr1 :: (a -> a -> a) -> EitherEdge a -> a

foldl1 :: (a -> a -> a) -> EitherEdge a -> a

toList :: EitherEdge a -> [a]

null :: EitherEdge a -> Bool

length :: EitherEdge a -> Int

elem :: Eq a => a -> EitherEdge a -> Bool

maximum :: Ord a => EitherEdge a -> a

minimum :: Ord a => EitherEdge a -> a

sum :: Num a => EitherEdge a -> a

product :: Num a => EitherEdge a -> a

Eq1 EitherEdge

Methods

liftEq :: (a -> b -> Bool) -> EitherEdge a -> EitherEdge b -> Bool

Ord1 EitherEdge

Methods

liftCompare :: (a -> b -> Ordering) -> EitherEdge a -> EitherEdge b -> Ordering

Show1 EitherEdge

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> EitherEdge a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [EitherEdge a] -> ShowS

Edge EitherEdge

Methods

from :: EitherEdge node -> node

to :: EitherEdge node -> node

Eq node => Eq (EitherEdge node)

Methods

(==) :: EitherEdge node -> EitherEdge node -> Bool

(/=) :: EitherEdge node -> EitherEdge node -> Bool

Ord node => Ord (EitherEdge node)

Methods

compare :: EitherEdge node -> EitherEdge node -> Ordering

(<) :: EitherEdge node -> EitherEdge node -> Bool

(<=) :: EitherEdge node -> EitherEdge node -> Bool

(>) :: EitherEdge node -> EitherEdge node -> Bool

(>=) :: EitherEdge node -> EitherEdge node -> Bool

max :: EitherEdge node -> EitherEdge node -> EitherEdge node

min :: EitherEdge node -> EitherEdge node -> EitherEdge node

Show node => Show (EitherEdge node)

Methods

showsPrec :: Int -> EitherEdge node -> ShowS

show :: EitherEdge node -> String

showList :: [EitherEdge node] -> ShowS

construction

empty :: Graph edge node edgeLabel nodeLabel

fromList :: (Edge e, Ord n) => [LabeledNode n nl] -> [LabeledEdge e n el] -> Graph e n el nl

fromMap :: (Edge e, Ord n) => Map n nl -> Map (e n) el -> Graph e n el nl

extract large portions of the graph

graphMap :: Graph edge node edgeLabel nodeLabel -> Map node (InOutMap edge node edgeLabel nodeLabel)

nodeLabels :: (Edge e, Ord n) => Graph e n el nl -> Map n nl

nodeSet :: Graph e n el nl -> Set n

nodes :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> [node]

nodeEdges :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> Map node (Set (edge node), nodeLabel, Set (edge node))

edgeLabels :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> Map (edge node) edgeLabel

edgeSet :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> Set (edge node)

edges :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> [edge node]

queries

isEmpty :: Graph e n el nl -> Bool

lookupNode :: Ord n => n -> Graph e n el nl -> Maybe nl

lookupEdge :: (Edge e, Ord n) => e n -> Graph e n el nl -> Maybe el

adjacentEdges :: (Edge e, Ord n) => Graph e n el nl -> n -> Set (e n)

isLoop :: (Edge edge, Eq node) => edge node -> Bool

pathExists :: (Edge edge, Ord node) => node -> node -> Graph edge node edgeLabel nodeLabel -> Bool

isConsistent :: (Ord n, Eq el) => Graph DirEdge n el nl -> Bool

manipulate labels

mapNode :: (nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1

mapNodeWithKey :: (n -> nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1

mapEdge :: (el0 -> el1) -> Graph e n el0 nl -> Graph e n el1 nl

mapEdgeWithKey :: (e n -> el0 -> el1) -> Graph e n el0 nl -> Graph e n el1 nl

mapNodeWithInOut :: (Edge e, Ord n) => (InOut e n el nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1

type InOut e n el nl = ([LabeledEdge e n el], LabeledNode n nl, [LabeledEdge e n el])

filterEdgeWithKey :: (Edge e, Ord n) => (e n -> el -> Bool) -> Graph e n el nl -> Graph e n el nl

traverseNode :: (Applicative f, Edge e, Ord n) => (nl0 -> f nl1) -> Graph e n el nl0 -> f (Graph e n el nl1)

Same restrictions as in traverse.

traverseEdge :: (Applicative f, Edge e, Ord n) => (el0 -> f el1) -> Graph e n el0 nl -> f (Graph e n el1 nl)

Same restrictions as in traverse.

traverse :: (Applicative f, Edge e, Ord n) => (nl0 -> f nl1) -> (el0 -> f el1) -> Graph e n el0 nl0 -> f (Graph e n el1 nl1)

Don't rely on a particular order of traversal!

combine graphs

checkedZipWith :: (Edge edge, Ord node) => Caller -> (nodeLabel0 -> nodeLabel1 -> nodeLabel2) -> (edgeLabel0 -> edgeLabel1 -> edgeLabel2) -> Graph edge node edgeLabel0 nodeLabel0 -> Graph edge node edgeLabel1 nodeLabel1 -> Graph edge node edgeLabel2 nodeLabel2

Node and edge sets must be equal.

union :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel

The node sets must be disjoint.

manipulate indices

class Edge edge => Reverse edge where

Minimal complete definition

reverseEdge

Methods

reverseEdge :: edge node -> edge node

Instances

Reverse DirEdge

Methods

reverseEdge :: DirEdge node -> DirEdge node

reverse :: (Reverse e, Ord n) => Graph e n el nl -> Graph e n el nl

reverseEdge :: Reverse edge => edge node -> edge node

mapKeys :: (Edge edge1, Ord node0, Ord node1) => (node0 -> node1) -> (edge0 node0 -> edge1 node1) -> Graph edge0 node0 edgeLabel nodeLabel -> Graph edge1 node1 edgeLabel nodeLabel

The index map must be an injection, that is, nodes must not collaps. Also the node and edge index maps must be consistent, i.e.

from (edgeMap e) == nodeMap (from e)
to   (edgeMap e) == nodeMap (to   e)

Strictly spoken, we would need the node map only for isolated nodes, but we use it for all nodes for simplicity.

mapMaybeEdgeKeys :: (Edge e1, Ord n) => (e0 n -> Maybe (e1 n)) -> Graph e0 n el nl -> Graph e1 n el nl

You may only use this for filtering edges and use more specialised types as a result. You must not alter source and target nodes of edges.

mapEdgeKeys :: (Edge e1, Ord n) => (e0 n -> e1 n) -> Graph e0 n el nl -> Graph e1 n el nl

Same restrictions as in mapMaybeEdgeKeys.

insertion and removal

deleteNode :: (Edge e, Ord n) => n -> Graph e n el nl -> Graph e n el nl

Node to be deleted must be contained in the graph.

deleteNodeSet :: (Edge e, Ord n) => Set n -> Graph e n el nl -> Graph e n el nl

Could be implemented more efficiently.

deleteEdge :: (Edge e, Ord n) => e n -> Graph e n el nl -> Graph e n el nl

insertNode :: Ord n => n -> nl -> Graph e n el nl -> Graph e n el nl

In the current implementation existing nodes are replaced with new labels and existing edges are maintained. However, I think we should better have an extra function for this purpose and you should not rely on this behavior.

insertEdge :: (Edge e, Ord n) => e n -> el -> Graph e n el nl -> Graph e n el nl

insertEdgeSet :: (Edge e, Ord n) => Map (e n) el -> Graph e n el nl -> Graph e n el nl

In the current implementation existing edges are replaced with new labels. However, I think we should better have an extra function for this purpose and you should not rely on this behavior. It is an unchecked error if edges between non-existing nodes are inserted.