comfort-graph-0.0.3: Graph structure with type parameters for nodes and edges

Safe HaskellSafe
LanguageHaskell2010

Data.Graph.Comfort

Contents

Synopsis

Types

data Graph edge node edgeLabel nodeLabel Source #

Instances

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

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) Source # 

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) Source # 

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) => Semigroup (Graph edge node edgeLabel nodeLabel) Source # 

Methods

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

sconcat :: NonEmpty (Graph edge node edgeLabel nodeLabel) -> Graph edge node edgeLabel nodeLabel #

stimes :: Integral b => b -> Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel #

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

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) Source #

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

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

Minimal complete definition

from, to

Methods

from, to :: edge node -> node Source #

Instances

Edge EitherEdge Source # 

Methods

from :: EitherEdge node -> node Source #

to :: EitherEdge node -> node Source #

Edge UndirEdge Source # 

Methods

from :: UndirEdge node -> node Source #

to :: UndirEdge node -> node Source #

Edge DirEdge Source # 

Methods

from :: DirEdge node -> node Source #

to :: DirEdge node -> node Source #

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

data DirEdge node Source #

Constructors

DirEdge node node 

Instances

Functor DirEdge Source # 

Methods

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

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

Foldable DirEdge Source # 

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

Methods

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

Ord1 DirEdge Source # 

Methods

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

Show1 DirEdge Source # 

Methods

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

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

Reverse DirEdge Source # 

Methods

reverseEdge :: DirEdge node -> DirEdge node Source #

Edge DirEdge Source # 

Methods

from :: DirEdge node -> node Source #

to :: DirEdge node -> node Source #

Eq node => Eq (DirEdge node) Source # 

Methods

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

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

Ord node => Ord (DirEdge node) Source # 

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) Source # 

Methods

showsPrec :: Int -> DirEdge node -> ShowS #

show :: DirEdge node -> String #

showList :: [DirEdge node] -> ShowS #

Arbitrary n => Arbitrary (DirEdge n) Source # 

Methods

arbitrary :: Gen (DirEdge n) #

shrink :: DirEdge n -> [DirEdge n] #

data UndirEdge node Source #

Constructors

UndirEdge node node 

Instances

Foldable UndirEdge Source # 

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

Methods

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

Ord1 UndirEdge Source # 

Methods

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

Show1 UndirEdge Source # 

Methods

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

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

Edge UndirEdge Source # 

Methods

from :: UndirEdge node -> node Source #

to :: UndirEdge node -> node Source #

Eq node => Eq (UndirEdge node) Source # 

Methods

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

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

Ord node => Ord (UndirEdge node) Source # 

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) Source # 

Methods

showsPrec :: Int -> UndirEdge node -> ShowS #

show :: UndirEdge node -> String #

showList :: [UndirEdge node] -> ShowS #

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

Methods

arbitrary :: Gen (UndirEdge n) #

shrink :: UndirEdge n -> [UndirEdge n] #

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

data EitherEdge node Source #

Constructors

EDirEdge (DirEdge node) 
EUndirEdge (UndirEdge node) 

Instances

Foldable EitherEdge Source # 

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

Methods

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

Ord1 EitherEdge Source # 

Methods

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

Show1 EitherEdge Source # 

Methods

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

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

Edge EitherEdge Source # 

Methods

from :: EitherEdge node -> node Source #

to :: EitherEdge node -> node Source #

Eq node => Eq (EitherEdge node) Source # 

Methods

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

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

Ord node => Ord (EitherEdge node) Source # 

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) Source # 

Methods

showsPrec :: Int -> EitherEdge node -> ShowS #

show :: EitherEdge node -> String #

showList :: [EitherEdge node] -> ShowS #

Construction

empty :: Graph edge node edgeLabel nodeLabel Source #

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

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

Extract large portions of the graph

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

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

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

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

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

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

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

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

Queries

isEmpty :: Graph e n el nl -> Bool Source #

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

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

predecessors :: (Edge e, Ord n) => Graph e n el nl -> n -> [n] Source #

Direct predecessors of a node, i.e. nodes with an outgoing edge to the queried node.

successors :: (Edge e, Ord n) => Graph e n el nl -> n -> [n] Source #

Direct successors of a node, i.e. nodes with an incoming edge from the queried node.

adjacentEdgeSet :: (Edge e, Ord n) => Graph e n el nl -> n -> Set (e n) Source #

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

Deprecated: Use adjacentEdgeSet instead.

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

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

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

Manipulate labels

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

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

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

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

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

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

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

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

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) Source #

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) Source #

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

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

The node sets must be disjoint.

Manipulate indices

class Edge edge => Reverse edge where Source #

Minimal complete definition

reverseEdge

Methods

reverseEdge :: edge node -> edge node Source #

Instances

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

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

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

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

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

Same restrictions as in mapMaybeEdgeKeys.

Insertion and removal

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

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

Could be implemented more efficiently.

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

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

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

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

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.