| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Graph.Graph
Contents
Description
An implementation of labeled directed graphs, allowing multiple parallel edges.
The implementation is based on using integer identifiers for nodes and edges, and association lists to store additional information such as payloads, sources and targets.
Operation comments contain the operation time complexity in the Big-O notation http://en.wikipedia.org/wiki/Big_O_notation, denoting by v the number of nodes in a graph, and by e the number of edges in a graph.
- data Graph n e = Graph {}
- newtype NodeId = NodeId Int
- newtype EdgeId = EdgeId Int
- data Node n = Node {}
- data Edge e = Edge {}
- type NodeInContext n e = (Node n, NodeContext n e)
- type EdgeInContext n e = (NodeInContext n e, Edge e, NodeInContext n e)
- data NodeContext n e
- incidentEdges :: NodeContext n e -> [EdgeInContext n e]
- incomingEdges :: NodeContext n e -> [EdgeInContext n e]
- outgoingEdges :: NodeContext n e -> [EdgeInContext n e]
- null :: Graph n e -> Bool
- isNodeOf :: Graph n e -> NodeId -> Bool
- isEdgeOf :: Graph n e -> EdgeId -> Bool
- lookupNode :: NodeId -> Graph n e -> Maybe (Node n)
- lookupNodeInContext :: NodeId -> Graph n e -> Maybe (NodeInContext n e)
- lookupEdge :: EdgeId -> Graph n e -> Maybe (Edge e)
- lookupEdgeInContext :: EdgeId -> Graph n e -> Maybe (EdgeInContext n e)
- isAdjacentTo :: Graph n e -> NodeId -> NodeId -> Bool
- isIncidentTo :: Graph n e -> NodeId -> EdgeId -> Bool
- nodesOf :: Graph n e -> EdgeId -> Maybe (NodeId, NodeId)
- sourceOf :: Graph n e -> EdgeId -> Maybe NodeId
- sourceOfUnsafe :: Graph n e -> EdgeId -> NodeId
- targetOf :: Graph n e -> EdgeId -> Maybe NodeId
- targetOfUnsafe :: Graph n e -> EdgeId -> NodeId
- getIncidentEdges :: Graph n e -> NodeId -> [EdgeId]
- empty :: Graph n e
- build :: [Int] -> [(Int, Int, Int)] -> Graph (Maybe n) (Maybe e)
- fromNodesAndEdges :: [Node n] -> [Edge e] -> Graph n e
- insertNode :: NodeId -> Graph (Maybe n) e -> Graph (Maybe n) e
- insertNodeWithPayload :: NodeId -> n -> Graph n e -> Graph n e
- insertEdge :: EdgeId -> NodeId -> NodeId -> Graph n (Maybe e) -> Graph n (Maybe e)
- insertEdgeWithPayload :: EdgeId -> NodeId -> NodeId -> e -> Graph n e -> Graph n e
- removeNode :: NodeId -> Graph n e -> Graph n e
- removeNodeForced :: NodeId -> Graph n e -> Graph n e
- removeNodeAndIncidentEdges :: NodeId -> Graph n e -> Graph n e
- removeEdge :: EdgeId -> Graph n e -> Graph n e
- updateNodePayload :: NodeId -> Graph n e -> (n -> n) -> Graph n e
- updateEdgePayload :: EdgeId -> Graph n e -> (e -> e) -> Graph n e
- nodes :: Graph n e -> [Node n]
- edges :: Graph n e -> [Edge e]
- nodeIds :: Graph n e -> [NodeId]
- edgeIds :: Graph n e -> [EdgeId]
- nodesInContext :: Graph n e -> [NodeInContext n e]
- edgesInContext :: Graph n e -> [EdgeInContext n e]
- newNodes :: Graph n e -> [NodeId]
- newEdges :: Graph n e -> [EdgeId]
Graph Type
A directed graph, allowing parallel edges. Both nodes and edges have optional payloads of arbitrary types.
Every node and edge is identified by a unique integer. The "namespaces" of nodes and edges are independent, i.e. the same number may be used to identify both a node and an edge within the same graph.
Equality tests cost O(v² + e²), and disregards the payloads.
Type of node identifiers, which are essentially integers.
Type of edge identifiers, which are essentially integers.
Nodes from within a graph.
Edges from within a graph.
Contexts and Graph Traversal
In order to traverse or navigate through the graph, NodeContexts are provided. The context of a
node provides access to its incident edges and neighbour nodes without explicitly looking them up
in the graph. Internally, nodes and edges are still being looked up, so keep in mind there's no
performance benefit. This module, however, can guarantee that this implicit lookup will work, so
there's no need to deal with Maybe values.
As an example, depth-first search could be implemented as follows:
depthFirstSearch :: NodeInContext n e -> [Node n]
depthFirstSearch initialNode =
search IntSet.empty [initialNode]
where
search _ [] = []
search visitedNodes ((node, context) : rest) =
if node `IntSet.member` visitedNodes then
search visitedNodes rest
else
let
nextNodes =
[ target | (_, _, target) <- outgoingEdges context ]
in
node :: search (IntSet.insert (nodeId node) visitedNodes) nextNodestype NodeInContext n e = (Node n, NodeContext n e) Source #
Shorthand for having a node along with its context.
type EdgeInContext n e = (NodeInContext n e, Edge e, NodeInContext n e) Source #
Shorthand for having an edge along with its source and target in context.
Because of lazyness, constructing a value of this type does not evaluate the node lookup. Thus, forcing the evaluation of the nodes costs O(v). Keep this in mind when using values of this type.
data NodeContext n e Source #
Provides access to a node's incident edges.
incidentEdges :: NodeContext n e -> [EdgeInContext n e] Source #
Get the edges that are incident on the current node.
O(e), plus the cost of evaluating the nodes of the result (see EdgeInContext).
incomingEdges :: NodeContext n e -> [EdgeInContext n e] Source #
Get the edges that have the current node as target.
O(e), plus the cost of evaluating the nodes of the result (see EdgeInContext).
outgoingEdges :: NodeContext n e -> [EdgeInContext n e] Source #
Get the edges that have the current node as source.
O(e), plus the cost of evaluating the nodes of the result (see EdgeInContext).
Neighbour nodes
In order to access the neighbour nodes of the edges, one may simply go through the edges, e.g.
map (\(_, _, target) -> target) . outgoingEdges map (\(source, _, _) -> source) . incomingEdges
These operations were not added to the graph API because it is not yet clear which of them are commonly used, and which names would be appropriate. If you identify the need for such an operation, submit an issue on github.
Query
isNodeOf :: Graph n e -> NodeId -> Bool Source #
Test if a node identifier is contained in the graph. O(v).
isEdgeOf :: Graph n e -> EdgeId -> Bool Source #
Test if an edge identifier is contained in the graph. O(e).
lookupNode :: NodeId -> Graph n e -> Maybe (Node n) Source #
Look up the node with given identifier in the graph. O(v).
lookupNodeInContext :: NodeId -> Graph n e -> Maybe (NodeInContext n e) Source #
Look up the node with given identifier, along with its context, in the graph. O(v).
lookupEdge :: EdgeId -> Graph n e -> Maybe (Edge e) Source #
Look up the edge with given identifier in the graph. O(e).
lookupEdgeInContext :: EdgeId -> Graph n e -> Maybe (EdgeInContext n e) Source #
Look up the edge with given identifier, along with its context, in the graph.
O(e), plus the cost of evaluating the nodes of the result (see EdgeInContext).
isAdjacentTo :: Graph n e -> NodeId -> NodeId -> Bool Source #
Test if the given nodes are adjacent. O(e²)
isIncidentTo :: Graph n e -> NodeId -> EdgeId -> Bool Source #
Test if the given edge has given node as source or target. O(e).
nodesOf :: Graph n e -> EdgeId -> Maybe (NodeId, NodeId) Source #
Deprecated: This function performs unnecessary dictionary lookups. Try using lookupNode, lookupNodeInContext, nodes or nodesInContext instead.
Gets a pair containing the source and target of the given edge. O(e).
sourceOf :: Graph n e -> EdgeId -> Maybe NodeId Source #
Deprecated: This function performs unnecessary dictionary lookups. Try using lookupNode, lookupNodeInContext, nodes or nodesInContext instead.
Gets the source of the given edge. O(e).
sourceOfUnsafe :: Graph n e -> EdgeId -> NodeId Source #
Deprecated: This function performs unnecessary dictionary lookups. Try using lookupNode, lookupNodeInContext, nodes or nodesInContext instead.
Gets the source of the given edge, crashing if no such edge exists. O(e).
targetOf :: Graph n e -> EdgeId -> Maybe NodeId Source #
Deprecated: This function performs unnecessary dictionary lookups. Try using lookupNode, lookupNodeInContext, nodes or nodesInContext instead.
Gets the target of the given edge. O(e).
targetOfUnsafe :: Graph n e -> EdgeId -> NodeId Source #
Deprecated: This function performs unnecessary dictionary lookups. Try using lookupNode, lookupNodeInContext, nodes or nodesInContext instead.
Gets the target of the given edge, crashing if no such edge exists. O(e).
getIncidentEdges :: Graph n e -> NodeId -> [EdgeId] Source #
Deprecated: This function performs unnecessary dictionary lookups. Try using lookupNode, lookupNodeInContext, nodes or nodesInContext instead.
Gets a list of all edges incident to the given node. O(e²)
Construction
build :: [Int] -> [(Int, Int, Int)] -> Graph (Maybe n) (Maybe e) Source #
Build a graph from lists of nodes and edges. Edges with undefined source or target are ignored and omitted from the resulting graph. O(v + e*v)
fromNodesAndEdges :: [Node n] -> [Edge e] -> Graph n e Source #
Build a graph from lists of nodes and edges. Edges with undefined source or target are ignored and omitted from the resulting graph. O(v + e*v)
Insertion
insertNode :: NodeId -> Graph (Maybe n) e -> Graph (Maybe n) e Source #
Insert a node with given identifier into a graph, without payload. If a node with the given identifier aready exists, its payload is removed. O(v).
insertNodeWithPayload :: NodeId -> n -> Graph n e -> Graph n e Source #
Insert a node with given identifier and payload into a graph. If a node with the given identifier already exists, its payload is updated. O(v).
insertEdge :: EdgeId -> NodeId -> NodeId -> Graph n (Maybe e) -> Graph n (Maybe e) Source #
(insertEdge e src tgt g) will insert an edge with identifier e from src to tgt in graph
g, without payload. If src or tgt are not nodes of g, the graph is not modified. If an
edge with identifier e already exists, it is updated. O(v + e).
insertEdgeWithPayload :: EdgeId -> NodeId -> NodeId -> e -> Graph n e -> Graph n e Source #
(insertEdgeWithPayload e src tgt p g) will insert an edge with identifier e from src to
tgt in graph g with payload p. If src or tgt are not nodes of g, the graph is not
modified. If an edge with identifier e already exists, it is updated. O(v + e).
Delete
removeNode :: NodeId -> Graph n e -> Graph n e Source #
Removes the given node from the graph, unless it has any incident edges. O(v + e²).
removeNodeForced :: NodeId -> Graph n e -> Graph n e Source #
Removes the given node from the graph, even if it has any incident edges. It does not verify if the node has incident edges, thus it may generate invalid graphs.
removeNodeAndIncidentEdges :: NodeId -> Graph n e -> Graph n e Source #
Removes the given node and all incident edges from the graph. O(v + e)
Update
updateNodePayload :: NodeId -> Graph n e -> (n -> n) -> Graph n e Source #
Update the node's payload, applying the given function on it. O(v).
updateEdgePayload :: EdgeId -> Graph n e -> (e -> e) -> Graph n e Source #
Update the edge's payload, applying the function on it. O(e).
Conversion
Lists
nodesInContext :: Graph n e -> [NodeInContext n e] Source #
List of all nodes from the graph, along with their contexts. O(v).
edgesInContext :: Graph n e -> [EdgeInContext n e] Source #
List of all edges from the graph, along with their contexts.
O(e), plus the cost of evaluating the nodes of the result (see EdgeInContext).