Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
Mini.Data.Graph
Description
A structure representing unique vertices and their interrelations
Synopsis
- data Graph a
- graph :: (Map a (Set a) -> Map a (Set a) -> b) -> Graph a -> b
- distance :: Ord a => Graph a -> a -> a -> Maybe Int
- layers :: Ord a => Graph a -> a -> [[a]]
- path :: Ord a => Graph a -> a -> a -> Bool
- reachable :: Ord a => Graph a -> a -> [a]
- sort :: Ord a => Graph a -> [a]
- empty :: Graph a
- fromList :: Ord a => [(a, [a])] -> Graph a
- singleton :: a -> Graph a
- add :: Ord a => a -> Graph a -> Graph a
- remove :: Ord a => a -> Graph a -> Graph a
- connect :: Ord a => a -> [a] -> Graph a -> Graph a
- disconnect :: Ord a => a -> [a] -> Graph a -> Graph a
- transpose :: Graph a -> Graph a
- assocs :: Graph a -> [(a, [a])]
- edges :: Graph a -> [(a, a)]
- vertices :: Graph a -> [a]
- indegree :: Ord a => a -> Graph a -> Maybe Int
- indegrees :: Graph a -> [(a, Int)]
- outdegree :: Ord a => a -> Graph a -> Maybe Int
- outdegrees :: Graph a -> [(a, Int)]
- lookup :: Ord a => a -> Graph a -> Maybe [a]
- lookupGE :: Ord a => a -> Graph a -> Maybe (a, [a])
- lookupGT :: Ord a => a -> Graph a -> Maybe (a, [a])
- lookupLE :: Ord a => a -> Graph a -> Maybe (a, [a])
- lookupLT :: Ord a => a -> Graph a -> Maybe (a, [a])
- lookupMax :: Graph a -> Maybe (a, [a])
- lookupMin :: Graph a -> Maybe (a, [a])
- member :: Ord a => a -> Graph a -> Bool
- sourceMax :: Graph a -> Maybe a
- sourceMin :: Graph a -> Maybe a
- sources :: Graph a -> [a]
- sinkMax :: Graph a -> Maybe a
- sinkMin :: Graph a -> Maybe a
- sinks :: Graph a -> [a]
A Note on Performance
In order to provide a friendly user interface, some performance has been sacrificed. The internal adjacency lists are implemented via maps rather than arrays, meaning accesses are done in logarithmic time rather than constant time.
Type
A graph with directed edges between vertices of type a
Instances
Foldable Graph Source # | |
Defined in Mini.Data.Graph Methods fold :: Monoid m => Graph m -> m # foldMap :: Monoid m => (a -> m) -> Graph a -> m # foldMap' :: Monoid m => (a -> m) -> Graph a -> m # foldr :: (a -> b -> b) -> b -> Graph a -> b # foldr' :: (a -> b -> b) -> b -> Graph a -> b # foldl :: (b -> a -> b) -> b -> Graph a -> b # foldl' :: (b -> a -> b) -> b -> Graph a -> b # foldr1 :: (a -> a -> a) -> Graph a -> a # foldl1 :: (a -> a -> a) -> Graph a -> a # elem :: Eq a => a -> Graph a -> Bool # maximum :: Ord a => Graph a -> a # minimum :: Ord a => Graph a -> a # | |
Ord a => Monoid (Graph a) Source # | |
Ord a => Semigroup (Graph a) Source # | |
Show a => Show (Graph a) Source # | |
Eq a => Eq (Graph a) Source # | |
Ord a => Ord (Graph a) Source # | |
Primitive Recursion
Arguments
:: (Map a (Set a) -> Map a (Set a) -> b) | Function applied to the adjacency lists of the graph: incoming edges, outgoing edges |
-> Graph a | The graph |
-> b |
Primitive recursion on graphs (internally represented by adjacency lists)
Algorithms
distance :: Ord a => Graph a -> a -> a -> Maybe Int Source #
Get the shortest distance in a graph between a vertex and another
layers :: Ord a => Graph a -> a -> [[a]] Source #
Breadth-first search for the hierarchy in a graph from a starting vertex
path :: Ord a => Graph a -> a -> a -> Bool Source #
Check whether there is a path in a graph from a vertex to another
reachable :: Ord a => Graph a -> a -> [a] Source #
Get the reachable vertices in a graph from a starting vertex
Construction
Modification
add :: Ord a => a -> Graph a -> Graph a Source #
Add an isolated vertex to a graph unless already present
remove :: Ord a => a -> Graph a -> Graph a Source #
Remove a vertex and its associations from a graph
connect :: Ord a => a -> [a] -> Graph a -> Graph a Source #
Add edges from a vertex to a list of vertices in a graph
disconnect :: Ord a => a -> [a] -> Graph a -> Graph a Source #
Remove edges from a vertex to a list of vertices in a graph
Query
indegree :: Ord a => a -> Graph a -> Maybe Int Source #
Get the number of incoming edges to a vertex in a graph
indegrees :: Graph a -> [(a, Int)] Source #
Get the number of incoming edges of each vertex in a graph
outdegree :: Ord a => a -> Graph a -> Maybe Int Source #
Get the number of outgoing edges from a vertex in a graph
outdegrees :: Graph a -> [(a, Int)] Source #
Get the number of outgoing edges of each vertex in a graph
lookupGE :: Ord a => a -> Graph a -> Maybe (a, [a]) Source #
Get the associations of the least vertex greater than or equal to a vertex
lookupGT :: Ord a => a -> Graph a -> Maybe (a, [a]) Source #
Get the associations of the least vertex strictly greater than a vertex
lookupLE :: Ord a => a -> Graph a -> Maybe (a, [a]) Source #
Get the associations of the greatest vertex less than or equal to a vertex
lookupLT :: Ord a => a -> Graph a -> Maybe (a, [a]) Source #
Get the associations of the greatest vertex strictly less than a vertex
lookupMax :: Graph a -> Maybe (a, [a]) Source #
Get the associations of the maximum vertex from a graph