Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Graph.Comfort

Contents

Types
Construction
Extract large portions of the graph
Queries
Manipulate labels
Combine graphs
Manipulate indices
Insertion and removal

Synopsis

data 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
- from, to :: edge node -> node
defaultEdgeFoldMap :: (Edge edge, Monoid a) => edge a -> a
data DirEdge node = DirEdge node node
data UndirEdge node = UndirEdge node node
undirEdge :: Ord node => node -> node -> UndirEdge node
data EitherEdge node
- = EDirEdge (DirEdge node)
- | EUndirEdge (UndirEdge node)
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
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]
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
predecessors :: (Edge e, Ord n) => Graph e n el nl -> n -> [n]
successors :: (Edge e, Ord n) => Graph e n el nl -> n -> [n]
adjacentEdgeSet :: (Edge e, Ord n) => Graph e n el nl -> n -> Set (e n)
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
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)
traverseEdge :: (Applicative f, Edge e, Ord n) => (el0 -> f el1) -> Graph e n el0 nl -> f (Graph e n el1 nl)
traverse :: (Applicative f, Edge e, Ord n) => (nl0 -> f nl1) -> (el0 -> f el1) -> Graph e n el0 nl0 -> f (Graph e n el1 nl1)
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
union :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel
class Edge edge => Reverse edge
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
mapMaybeEdgeKeys :: (Edge e1, Ord n) => (e0 n -> Maybe (e1 n)) -> Graph e0 n el nl -> Graph e1 n el nl
mapEdgeKeys :: (Edge e1, Ord n) => (e0 n -> e1 n) -> Graph e0 n el nl -> Graph e1 n el nl
deleteNode :: (Edge e, Ord n) => n -> Graph e n el nl -> Graph e n el nl
deleteNodeSet :: (Edge e, Ord n) => Set n -> Graph e n el nl -> Graph e n el nl
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
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

Types

data Graph edge node edgeLabel nodeLabel Source #

Instances

Instances details

(Eq1 edge, Eq node, Eq edgeLabel, Eq nodeLabel) => Eq (Graph edge node edgeLabel nodeLabel) Source #
Instance details Defined in Data.Graph.Comfort Methods (==) :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Bool # (/=) :: Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Bool #
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) => Ord (Graph edge node edgeLabel nodeLabel) Source #
Instance details Defined in Data.Graph.Comfort 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 #
Instance details Defined in Data.Graph.Comfort 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 #
Instance details Defined in Data.Graph.Comfort 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 #
Instance details Defined in Data.Graph.Comfort 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 #

Methods

from :: edge node -> node Source #

to :: edge node -> node Source #

Instances

Instances details

Edge EitherEdge Source #
Instance details Defined in Data.Graph.Comfort Methods from :: EitherEdge node -> node Source # to :: EitherEdge node -> node Source #
Edge UndirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods from :: UndirEdge node -> node Source # to :: UndirEdge node -> node Source #
Edge DirEdge Source #
Instance details Defined in Data.Graph.Comfort 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

Instances details

Functor DirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods fmap :: (a -> b) -> DirEdge a -> DirEdge b # (<$) :: a -> DirEdge b -> DirEdge a #
Foldable DirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods fold :: Monoid m => DirEdge m -> m # foldMap :: Monoid m => (a -> m) -> DirEdge a -> 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 #
Instance details Defined in Data.Graph.Comfort Methods liftEq :: (a -> b -> Bool) -> DirEdge a -> DirEdge b -> Bool #
Ord1 DirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods liftCompare :: (a -> b -> Ordering) -> DirEdge a -> DirEdge b -> Ordering #
Show1 DirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> DirEdge a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [DirEdge a] -> ShowS #
Reverse DirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods reverseEdge :: DirEdge node -> DirEdge node Source #
Edge DirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods from :: DirEdge node -> node Source # to :: DirEdge node -> node Source #
Eq node => Eq (DirEdge node) Source #
Instance details Defined in Data.Graph.Comfort Methods (==) :: DirEdge node -> DirEdge node -> Bool # (/=) :: DirEdge node -> DirEdge node -> Bool #
Ord node => Ord (DirEdge node) Source #
Instance details Defined in Data.Graph.Comfort 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 #
Instance details Defined in Data.Graph.Comfort Methods showsPrec :: Int -> DirEdge node -> ShowS # show :: DirEdge node -> String # showList :: [DirEdge node] -> ShowS #
Arbitrary n => Arbitrary (DirEdge n) Source #
Instance details Defined in Data.Graph.Comfort Methods arbitrary :: Gen (DirEdge n) # shrink :: DirEdge n -> [DirEdge n] #

data UndirEdge node Source #

Constructors

UndirEdge node node

Instances

Instances details

Foldable UndirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods fold :: Monoid m => UndirEdge m -> m # foldMap :: Monoid m => (a -> m) -> UndirEdge a -> 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 #
Instance details Defined in Data.Graph.Comfort Methods liftEq :: (a -> b -> Bool) -> UndirEdge a -> UndirEdge b -> Bool #
Ord1 UndirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods liftCompare :: (a -> b -> Ordering) -> UndirEdge a -> UndirEdge b -> Ordering #
Show1 UndirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> UndirEdge a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [UndirEdge a] -> ShowS #
Edge UndirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods from :: UndirEdge node -> node Source # to :: UndirEdge node -> node Source #
Eq node => Eq (UndirEdge node) Source #
Instance details Defined in Data.Graph.Comfort Methods (==) :: UndirEdge node -> UndirEdge node -> Bool # (/=) :: UndirEdge node -> UndirEdge node -> Bool #
Ord node => Ord (UndirEdge node) Source #
Instance details Defined in Data.Graph.Comfort 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 #
Instance details Defined in Data.Graph.Comfort Methods showsPrec :: Int -> UndirEdge node -> ShowS # show :: UndirEdge node -> String # showList :: [UndirEdge node] -> ShowS #
(Arbitrary n, Ord n) => Arbitrary (UndirEdge n) Source #
Instance details Defined in Data.Graph.Comfort 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

Instances details

Foldable EitherEdge Source #
Instance details Defined in Data.Graph.Comfort Methods fold :: Monoid m => EitherEdge m -> m # foldMap :: Monoid m => (a -> m) -> EitherEdge a -> 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 #
Instance details Defined in Data.Graph.Comfort Methods liftEq :: (a -> b -> Bool) -> EitherEdge a -> EitherEdge b -> Bool #
Ord1 EitherEdge Source #
Instance details Defined in Data.Graph.Comfort Methods liftCompare :: (a -> b -> Ordering) -> EitherEdge a -> EitherEdge b -> Ordering #
Show1 EitherEdge Source #
Instance details Defined in Data.Graph.Comfort Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> EitherEdge a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [EitherEdge a] -> ShowS #
Edge EitherEdge Source #
Instance details Defined in Data.Graph.Comfort Methods from :: EitherEdge node -> node Source # to :: EitherEdge node -> node Source #
Eq node => Eq (EitherEdge node) Source #
Instance details Defined in Data.Graph.Comfort Methods (==) :: EitherEdge node -> EitherEdge node -> Bool # (/=) :: EitherEdge node -> EitherEdge node -> Bool #
Ord node => Ord (EitherEdge node) Source #
Instance details Defined in Data.Graph.Comfort 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 #
Instance details Defined in Data.Graph.Comfort Methods showsPrec :: Int -> EitherEdge node -> ShowS # show :: EitherEdge node -> String # showList :: [EitherEdge node] -> ShowS #

Construction

empty :: Graph edge node edgeLabel nodeLabel Source #

Graph.isEmpty (Graph.empty :: MonoGraph)

Graph.isConsistent (Graph.empty :: MonoGraph)

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 #

\(TestGraph gr) -> gr == Graph.fromMap (Graph.nodeLabels gr) (Graph.edgeLabels gr)

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 #

\(TestGraph gr) n -> Graph.lookupNode n gr == Map.lookup n (Graph.nodeLabels gr)

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

\(GraphAndEdge gr e) -> Graph.lookupEdge e gr == Map.lookup e (Graph.edgeLabels gr)

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 #

\(TestGraph gr) -> Graph.mapNode id gr == gr

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 #

\(TestGraph gr) -> Graph.mapEdge id gr == gr

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 #

\(GraphAndEdge gr e) -> Graph.filterEdgeWithKey (\ei _ -> e/=ei) gr == Graph.deleteEdge e gr

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.

\(TestGraph gr) nl -> Graph.isConsistent $ evalTraverseNode nl gr

\(TestGraph gr) -> runIdentity (Graph.traverseNode (Identity . Char.toUpper) gr) == Graph.mapNode Char.toUpper gr

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.

\(TestGraph gr) el -> Graph.isConsistent $ evalTraverseEdge el gr

\(TestGraph gr) el -> runIdentity (Graph.traverseEdge (Identity . (el+)) gr) == Graph.mapEdge (el+) gr

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!

\(TestGraph gr) nl el -> Graph.isConsistent $ evalTraverse nl el gr

\(TestGraph gr) nl el -> evalTraverse nl el gr == evalTraverseNode nl (evalTraverseEdge el gr)

\(TestGraph gr) nl el -> evalTraverse nl el gr == evalTraverseEdge el (evalTraverseNode nl gr)

\(TestGraph gr) nl -> flip MS.evalState nl (Graph.traverseNode nodeAction gr) == flip MS.evalState nl (Graph.traverse nodeAction pure gr)

\(TestGraph gr) el -> flip MS.evalState el (Graph.traverseEdge edgeAction gr) == flip MS.evalState el (Graph.traverse pure edgeAction gr)

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

Minimal complete definition

reverseEdge

Instances

Instances details

Reverse DirEdge Source #
Instance details Defined in Data.Graph.Comfort Methods reverseEdge :: DirEdge node -> DirEdge node Source #

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

\(TestGraph gr) -> Graph.isConsistent (Graph.reverse gr)

\(TestGraph gr) -> Graph.reverse (Graph.reverse gr) == gr

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.

\(TestGraph gr) n -> Graph.isConsistent $ deleteNodeIfExists n gr

\(TestGraph gr) n nl -> Graph.deleteNode n (Graph.insertNode n nl gr) == deleteNodeIfExists n gr

\(TestGraph gr) -> let isolatedNodes = filter (isolated gr) $ Graph.nodes gr in not (null isolatedNodes) ==> QC.forAll (QC.elements isolatedNodes) $ \n nl -> Graph.insertNode n nl gr == Graph.insertNode n nl (Graph.deleteNode n gr)

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 #

\(GraphAndEdge gr e) -> Graph.isConsistent $ Graph.deleteEdge e gr

\(GraphAndEdge gr e) el -> Graph.deleteEdge e (Graph.insertEdge e el gr) == Graph.deleteEdge e gr

\(GraphAndEdge gr e) el -> Graph.insertEdge e el gr == Graph.insertEdge e el (Graph.deleteEdge e gr)

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.

\(TestGraph gr) n nl -> Graph.isConsistent $ Graph.insertNode n nl gr

\(TestGraph gr) n nl -> Graph.lookupNode n (Graph.insertNode n nl gr) == Just nl

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

\(GraphAndEdge gr e) el -> Graph.isConsistent $ Graph.insertEdge e el gr

\(GraphAndEdge gr e) el -> Graph.lookupEdge e (Graph.insertEdge e el gr) == Just el

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.