Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
- 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
- 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
- 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 where
- reverseEdge :: edge node -> edge node
- reverse :: (Reverse e, Ord n) => Graph e n el nl -> Graph e n el nl
- 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
(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
DirEdge node node |
UndirEdge node node |
data EitherEdge node Source
EDirEdge (DirEdge node) | |
EUndirEdge (UndirEdge node) |
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
fromList :: (Edge e, Ord n) => [LabeledNode n nl] -> [LabeledEdge 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
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
queries
lookupNode :: Ord n => n -> Graph e n el nl -> Maybe nl Source
pathExists :: (Edge edge, Ord node) => node -> node -> Graph edge node edgeLabel nodeLabel -> Bool Source
manipulate labels
mapNodeWithKey :: (n -> nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1 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
reverseEdge :: 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.
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.
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.