| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Algorithm.SCC
Description
Generating strongly connected components: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
The only modification is that this algorithm considers SCCs wrt to some frontier. A frontier is a set of nodes that is not passed, i.e., we consider a subgraph bounded by (up to not including) the frontier.
We assume the existence of a function post :: G -> Int -> IS.IntSet that returns, given the graph and the current node, a set of next nodes. We also assume the existence of a function V :: G -> IS.IntSet that returns all vertices.
I could get none of the Data.Graph functions to work properly, hence this reimplementation.
Synopsis
- data SCC_state = SCC_State {
- scc_indices :: IntMap Int
- scc_lowlinks :: IntMap Int
- scc_index :: Int
- scc_stack :: [Int]
- scc_return :: [IntSet]
- set_index_of :: Key -> (SCC_state -> Int) -> SCC_state -> SCC_state
- set_lowlink_of :: Key -> (SCC_state -> Int) -> SCC_state -> SCC_state
- set_index :: (SCC_state -> Int) -> SCC_state -> SCC_state
- push :: Int -> SCC_state -> SCC_state
- pop_and_return :: Int -> SCC_state -> SCC_state
- strongconnect :: IntGraph g => g -> Int -> IntSet -> State SCC_state ()
- compute_all_sccs :: IntGraph g => g -> IntSet -> State SCC_state ()
- init_scc_state :: SCC_state
- scc_of :: IntGraph g => g -> Int -> IntSet -> [IntSet]
- all_sccs :: IntGraph g => g -> IntSet -> [IntSet]
- graph_nontrivial_scc :: Graph -> IntSet
- graph_find_next :: Graph -> Maybe Int
Documentation
Constructors
| SCC_State | |
Fields
| |
graph_nontrivial_scc :: Graph -> IntSet Source #
retrieve a non-trivial SCC, if any exists