Safe Haskell | None |
---|---|
Language | Haskell98 |
Directed graphs (can of course simulate undirected graphs).
Represented as adjacency maps.
Each source node maps to a adjacency map, which is a map from target nodes to edges.
This allows to get the outgoing edges in O(log n) time where
n
is the number of nodes in the graph. However, the set
of incoming edges can only be obtained in O(n log n),
or O(e) where e
is the total number of edges.
- newtype Graph n e = Graph {}
- invariant :: Ord n => Graph n e -> Bool
- edges :: Ord n => Graph n e -> [(n, n, e)]
- edgesFrom :: Ord n => Graph n e -> [n] -> [(n, n, e)]
- nodes :: Ord n => Graph n e -> Set n
- filterEdges :: Ord n => (e -> Bool) -> Graph n e -> Graph n e
- fromNodes :: Ord n => [n] -> Graph n e
- fromList :: (SemiRing e, Ord n) => [(n, n, e)] -> Graph n e
- empty :: Graph n e
- singleton :: Ord n => n -> n -> e -> Graph n e
- insert :: (SemiRing e, Ord n) => n -> n -> e -> Graph n e -> Graph n e
- removeNode :: Ord n => n -> Graph n e -> Graph n e
- removeEdge :: Ord n => n -> n -> Graph n e -> Graph n e
- union :: (SemiRing e, Ord n) => Graph n e -> Graph n e -> Graph n e
- unions :: (SemiRing e, Ord n) => [Graph n e] -> Graph n e
- lookup :: Ord n => n -> n -> Graph n e -> Maybe e
- neighbours :: Ord n => n -> Graph n e -> [(n, e)]
- sccs' :: Ord n => Graph n e -> [SCC n]
- sccs :: Ord n => Graph n e -> [[n]]
- acyclic :: Ord n => Graph n e -> Bool
- transitiveClosure1 :: (Eq e, SemiRing e, Ord n) => Graph n e -> Graph n e
- transitiveClosure :: (Eq e, SemiRing e, Ord n) => Graph n e -> Graph n e
- findPath :: (SemiRing e, Ord n) => (e -> Bool) -> n -> n -> Graph n e -> Maybe e
- allPaths :: (SemiRing e, Ord n, Ord c) => (e -> c) -> n -> n -> Graph n e -> [e]
- nodeIn :: (Ord n, Arbitrary n) => Graph n e -> Gen n
- edgeIn :: (Ord n, Arbitrary n, Arbitrary e) => Graph n e -> Gen (n, n, e)
- tests :: IO Bool
Documentation
Graph n e
is a directed graph with nodes in n
and edges in e
.
Only one edge between any two nodes.
Represented as "adjacency list", or rather, adjacency map.
This allows to get all outgoing edges for a node in O(log n)
time
where n
is the number of nodes of the graph.
Incoming edges can only be computed in O(n + e)
time where
e
is the number of edges.
invariant :: Ord n => Graph n e -> Bool Source
A structural invariant for the graphs.
The set of nodes is obtained by Map.keys . unGraph
meaning that each node, be it only the target of an edge,
must be assigned an adjacency map, albeit it could be empty.
See singleton
.
edgesFrom :: Ord n => Graph n e -> [n] -> [(n, n, e)] Source
All edges originating in the given nodes. (I.e., all outgoing edges for the given nodes.)
Roughly linear in the length of the result list O(result)
.
fromNodes :: Ord n => [n] -> Graph n e Source
Constructs a completely disconnected graph containing the given
nodes. O(n)
.
fromList :: (SemiRing e, Ord n) => [(n, n, e)] -> Graph n e Source
Constructs a graph from a list of edges. O(e)
singleton :: Ord n => n -> n -> e -> Graph n e Source
A graph with two nodes and a single connecting edge.
insert :: (SemiRing e, Ord n) => n -> n -> e -> Graph n e -> Graph n e Source
Insert an edge into the graph.
removeNode :: Ord n => n -> Graph n e -> Graph n e Source
Removes the given node, and all corresponding edges, from the graph.
removeEdge :: Ord n => n -> n -> Graph n e -> Graph n e Source
removeEdge n1 n2 g
removes the edge going from n1
to n2
, if
any.
neighbours :: Ord n => n -> Graph n e -> [(n, e)] Source
sccs' :: Ord n => Graph n e -> [SCC n] Source
The graph's strongly connected components, in reverse topological order.
sccs :: Ord n => Graph n e -> [[n]] Source
The graph's strongly connected components, in reverse topological order.
transitiveClosure1 :: (Eq e, SemiRing e, Ord n) => Graph n e -> Graph n e Source
Computes the transitive closure of the graph.
Note that this algorithm is not guaranteed to be correct (or terminate) for arbitrary semirings.
This function operates on the entire graph at once.
transitiveClosure :: (Eq e, SemiRing e, Ord n) => Graph n e -> Graph n e Source
Computes the transitive closure of the graph.
Note that this algorithm is not guaranteed to be correct (or terminate) for arbitrary semirings.
This function operates on one strongly connected component at a time.
allPaths :: (SemiRing e, Ord n, Ord c) => (e -> c) -> n -> n -> Graph n e -> [e] Source
allPaths classify a b g
returns a list of pathes (accumulated edge weights)
from node a
to node b
in g
.
Alternative intermediate pathes are only considered if they
are distinguished by the classify
function.
nodeIn :: (Ord n, Arbitrary n) => Graph n e -> Gen n Source
Generates a node from the graph. (Unless the graph is empty.)