libgraph 1.4 → 1.5

raw patch · 4 files changed

+32/−4 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/Graph/Libgraph.hs +1/−0
• Data/Graph/Libgraph/Core.hs +27/−1
• Data/Graph/Libgraph/Dot.hs +2/−1
• libgraph.cabal +2/−2

@@ -30,6 +30,7 @@ , display , collapse , remove+, treeDepth ) where import Data.Graph.Libgraph.Core import Data.Graph.Libgraph.DepthFirst

@@ -1,7 +1,8 @@ module Data.Graph.Libgraph.Core where import Data.Maybe import Data.List-import Debug.Trace(traceStack)+import Data.Map.Strict(Map)+import qualified Data.Map.Strict as Map  -------------------------------------------------------------------------------- -- External representation of graphs@@ -46,6 +47,18 @@ succs :: Eq vertex => Graph vertex arc -> vertex -> [vertex] succs g v = map target $ filter ((== v) . source) (arcs g) ++succCache :: Ord vertex => Graph vertex arc -> (vertex -> [vertex])+succCache g = \v -> case Map.lookup v m of +                        Nothing -> []+                        (Just ws) -> ws++  where m = foldl (\m' (Arc v w _) -> insertCon v w m') Map.empty (arcs g)+  ++insertCon :: Ord k => k -> a -> Map k [a] -> Map k [a]+insertCon i x = Map.insertWith (\[x] xs->x:xs) i [x]+ -- | Direct predecessors of a vertex. preds :: Eq vertex => Graph vertex arc -> vertex -> [vertex] preds g v = map source $ filter ((== v) . target) (arcs g)@@ -102,3 +115,16 @@  fstList :: [(a,b)] -> [a] fstList = fst . unzip++---++treeDepth :: Ord v => Graph v a -> Int+treeDepth g = treeDepth' [] (root g)+  where suc = succCache g++        treeDepth' seen v+          | v `elem` seen = 1+          | otherwise     = case suc v of+             [] -> 0+             cs -> 1 + (maximum . map (treeDepth' (v:seen)) $ cs)+

@@ -26,7 +26,8 @@ showVertex :: (vertex->(String,String)) -> (vertex,Int) -> String showVertex vLabel (v,i) =   let (lbl,extra) = vLabel v-  in  vName i ++ " [label=\"" ++ escape lbl ++ "\"" ++ extra ++ "]\n"+  in  vName i ++ " [label=" ++ lbl ++ "" ++ extra ++ "]\n"+  -- in  vName i ++ " [label=\"" ++ escape lbl ++ "\"" ++ extra ++ "]\n"  showArc :: Eq vertex => [(vertex,Int)] -> (Arc vertex arc->String) -> (Arc vertex arc) -> String showArc vs aLabel a

@@ -1,5 +1,5 @@ Name:           libgraph
-Version:        1.4
+Version:        1.5
 Homepage:      http://maartenfaddegon.nl
 Synopsis:       Store and manipulate data in a graph.
 Description:    A graph type, analysis of graphs and manipulation of graphs.
@@ -25,7 +25,7 @@                      Data.Graph.Libgraph.Dagify
                      Data.Graph.Libgraph.AlgoDebug
   default-language:  Haskell2010
-  ghc-prof-options:  -auto-all
+-- ghc-prof-options:  -auto-all
 
 -- Executable Libgraph-test
 --   Build-Depends:     base >= 4 && < 5, monads-tf, process