GraphSCC 1.0.1 → 1.0.2

raw patch · 2 files changed

+5/−3 lines, 2 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

- Data.Graph.SCC: stronglyConnComp :: (Ord key) => [(node, key, [key])] -> [SCC node]

+ Data.Graph.SCC: stronglyConnComp :: Ord key => [(node, key, [key])] -> [SCC node]

- Data.Graph.SCC: stronglyConnCompR :: (Ord key) => [(node, key, [key])] -> [SCC (node, key, [key])]

+ Data.Graph.SCC: stronglyConnCompR :: Ord key => [(node, key, [key])] -> [SCC (node, key, [key])]

Files

Data/Graph/ArraySCC.hs +4/−2
GraphSCC.cabal +1/−1

Data/Graph/ArraySCC.hs view

@@ -12,16 +12,18 @@  -- | Computes the strongly connected components (SCCs) of the graph in -- O(#edges + #vertices) time.  The resulting tuple contains:+-- --   * A (reversed) topologically sorted list of SCCs. --     Each SCCs is assigned a unique identifier of type 'Int'.+-- --   * An O(1) mapping from vertices in the original graph to the identifier---     of their SCC.  This mapping will raise an "out of bounds"+--     of their SCC.  This mapping will raise an \"out of bounds\" --     exception if it is applied to integers that do not correspond to --     vertices in the input graph. -- -- This function assumes that the adjacency lists in the original graph -- mention only nodes that are in the graph. Violating this assumption--- will result in "out of bounds" array exception.+-- will result in \"out of bounds\" array exception. scc :: Graph -> ([(Int,[Vertex])], Vertex -> Int) scc g = runST (   do ixes <- newArray (bounds g) 0

GraphSCC.cabal view

@@ -1,5 +1,5 @@ Name:             GraphSCC-Version:          1.0.1+Version:          1.0.2 License:          BSD3 License-file:     LICENSE Author:           Iavor S. Diatchki