| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Digraph
Synopsis
- data Graph node
- graphFromEdgedVerticesOrd :: Ord key => [Node key payload] -> Graph (Node key payload)
- graphFromEdgedVerticesUniq :: Uniquable key => [Node key payload] -> Graph (Node key payload)
- data SCC vertex
- = AcyclicSCC vertex
- | CyclicSCC [vertex]
- data Node key payload = DigraphNode {
- node_payload :: payload
- node_key :: key
- node_dependencies :: [key]
- flattenSCC :: SCC vertex -> [vertex]
- flattenSCCs :: [SCC a] -> [a]
- stronglyConnCompG :: Graph node -> [SCC node]
- topologicalSortG :: Graph node -> [node]
- verticesG :: Graph node -> [node]
- edgesG :: Graph node -> [Edge node]
- hasVertexG :: Graph node -> node -> Bool
- reachableG :: Graph node -> node -> [node]
- reachablesG :: Graph node -> [node] -> [node]
- transposeG :: Graph node -> Graph node
- emptyG :: Graph node -> Bool
- findCycle :: forall payload key. Ord key => [Node key payload] -> Maybe [payload]
- stronglyConnCompFromEdgedVerticesOrd :: Ord key => [Node key payload] -> [SCC payload]
- stronglyConnCompFromEdgedVerticesOrdR :: Ord key => [Node key payload] -> [SCC (Node key payload)]
- stronglyConnCompFromEdgedVerticesUniq :: Uniquable key => [Node key payload] -> [SCC payload]
- stronglyConnCompFromEdgedVerticesUniqR :: Uniquable key => [Node key payload] -> [SCC (Node key payload)]
- data EdgeType
- classifyEdges :: forall key. Uniquable key => key -> (key -> [key]) -> [(key, key)] -> [((key, key), EdgeType)]
Documentation
graphFromEdgedVerticesUniq :: Uniquable key => [Node key payload] -> Graph (Node key payload) Source #
Strongly connected component.
Constructors
A single vertex that is not in any cycle.
A maximal set of mutually reachable vertices.
Instances
Instance details
Defined in Data.Graph
Methods
fold :: Monoid m => SCC m -> m #
foldMap :: Monoid m => (a -> m) -> SCC a -> m #
foldr :: (a -> b -> b) -> b -> SCC a -> b #
foldr' :: (a -> b -> b) -> b -> SCC a -> b #
foldl :: (b -> a -> b) -> b -> SCC a -> b #
foldl' :: (b -> a -> b) -> b -> SCC a -> b #
foldr1 :: (a -> a -> a) -> SCC a -> a #
foldl1 :: (a -> a -> a) -> SCC a -> a #
elem :: Eq a => a -> SCC a -> Bool #
maximum :: Ord a => SCC a -> a #
Since: containers-0.5.9
Instance details
Defined in Data.Graph
Instance details
Defined in Data.Graph
Methods
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SCC vertex -> c (SCC vertex) #
gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SCC vertex) #
toConstr :: SCC vertex -> Constr #
dataTypeOf :: SCC vertex -> DataType #
dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SCC vertex)) #
dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SCC vertex)) #
gmapT :: (forall b. Data b => b -> b) -> SCC vertex -> SCC vertex #
gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r #
gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r #
gmapQ :: (forall d. Data d => d -> u) -> SCC vertex -> [u] #
gmapQi :: Int -> (forall d. Data d => d -> u) -> SCC vertex -> u #
gmapM :: Monad m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) #
gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) #
gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) #
Instance details
Defined in Data.Graph
Instance details
Defined in Data.Graph
data Node key payload Source #
Representation for nodes of the Graph.
- The
payloadis user data, just carried around in this module - The
keyis the node identifier. Key has an Ord instance for performance reasons. - The
[key]are the dependencies of the node; it's ok to have extra keys in the dependencies that are not the key of any Node in the graph
Constructors
Fields
- node_payload :: payload
User data
- node_key :: key
User defined node id
- node_dependencies :: [key]
Dependencies/successors of the node
flattenSCC :: SCC vertex -> [vertex] #
The vertices of a strongly connected component.
flattenSCCs :: [SCC a] -> [a] #
The vertices of a list of strongly connected components.
stronglyConnCompG :: Graph node -> [SCC node] Source #
topologicalSortG :: Graph node -> [node] Source #
hasVertexG :: Graph node -> node -> Bool Source #
reachableG :: Graph node -> node -> [node] Source #
reachablesG :: Graph node -> [node] -> [node] Source #
Given a list of roots return all reachable nodes.
transposeG :: Graph node -> Graph node Source #
findCycle :: forall payload key. Ord key => [Node key payload] -> Maybe [payload] Source #
Find a reasonably short cycle a->b->c->a, in a strongly connected component. The input nodes are presumed to be a SCC, so you can start anywhere.
stronglyConnCompFromEdgedVerticesOrdR :: Ord key => [Node key payload] -> [SCC (Node key payload)] Source #
stronglyConnCompFromEdgedVerticesUniq :: Uniquable key => [Node key payload] -> [SCC payload] Source #
stronglyConnCompFromEdgedVerticesUniqR :: Uniquable key => [Node key payload] -> [SCC (Node key payload)] Source #
Edge direction based on DFS Classification
classifyEdges :: forall key. Uniquable key => key -> (key -> [key]) -> [(key, key)] -> [((key, key), EdgeType)] Source #
Given a start vertex, a way to get successors from a node and a list of (directed) edges classify the types of edges.