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

types

data Graph edge node edgeLabel nodeLabel Source

Instances

(Eq node, Eq edgeLabel, Eq nodeLabel, Eq1 edge) => Eq (Graph edge node edgeLabel nodeLabel)
(Ord node, Ord edgeLabel, Ord nodeLabel, Ord1 edge) => Ord (Graph edge node edgeLabel nodeLabel)
(Edge e, Ord n, Show1 e, Show n, Show el, Show nl) => Show (Graph e n el nl)
(Edge edge, Ord node) => Monoid (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, to :: edge node -> node Source

Instances

Edge EitherEdge
Edge UndirEdge
Edge DirEdge

data DirEdge node Source

Constructors

DirEdge node node

Instances

Functor DirEdge
Foldable DirEdge
Eq1 DirEdge
Ord1 DirEdge
Show1 DirEdge
Reverse DirEdge
Edge DirEdge
Eq node => Eq (DirEdge node)
Ord node => Ord (DirEdge node)
Show node => Show (DirEdge node)
Arbitrary n => Arbitrary (DirEdge n)

data UndirEdge node Source

Constructors

UndirEdge node node

Instances

Foldable UndirEdge
Eq1 UndirEdge
Ord1 UndirEdge
Show1 UndirEdge
Edge UndirEdge
Eq node => Eq (UndirEdge node)
Ord node => Ord (UndirEdge node)
Show node => Show (UndirEdge node)
(Arbitrary n, Ord n) => Arbitrary (UndirEdge n)

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

data EitherEdge node Source

Constructors

EDirEdge (DirEdge node)
EUndirEdge (UndirEdge node)

Instances

Foldable EitherEdge
Eq1 EitherEdge
Ord1 EitherEdge
Show1 EitherEdge
Edge EitherEdge
Eq node => Eq (EitherEdge node)
Ord node => Ord (EitherEdge node)
Show node => Show (EitherEdge node)

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

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

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

Methods

reverseEdge :: edge node -> edge node Source

Instances

Reverse DirEdge

reverse :: (Reverse e, Ord n) => Graph e n el nl -> Graph e n el nl 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

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.