fgl 5.4.2.2 → 5.4.2.3
raw patch · 9 files changed
+33/−436 lines, 9 filesnew-uploaderPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- Data/Graph/Inductive/PatriciaTree.hs +27/−12
- LICENSE +2/−1
- doc/CHANGES +0/−120
- doc/README +0/−115
- fgl.cabal +4/−4
- prologue.txt +0/−1
- test/bcc.hs +0/−16
- test/benchmark.hs +0/−138
- test/test.hs +0/−29
Data/Graph/Inductive/PatriciaTree.hs view
@@ -1,3 +1,5 @@+{-# LANGUAGE ScopedTypeVariables #-}+ -- |An efficient implementation of 'Data.Graph.Inductive.Graph.Graph' -- using big-endian patricia tree (i.e. "Data.IntMap"). --@@ -25,12 +27,13 @@ import qualified Data.IntMap as IM import Data.List import Data.Maybe+import Control.Arrow(second) -data Gr a b = Gr (GraphRep a b)+newtype Gr a b = Gr (GraphRep a b) type GraphRep a b = IntMap (Context' a b)-type Context' a b = (IntMap b, a, IntMap b)+type Context' a b = (IntMap [b], a, IntMap [b]) type UGr = Gr () () @@ -56,7 +59,8 @@ ix = fst . fst . fromJust labEdges (Gr g) = do (node, (_, _, s)) <- IM.toList g- (next, label) <- IM.toList s+ (next, labels) <- IM.toList s+ label <- labels return (node, next, label) @@ -103,8 +107,8 @@ g1 = IM.adjust addSucc' v g g2 = IM.adjust addPred' w g1 - addSucc' (ps, l', ss) = (ps, l', IM.insert w l ss)- addPred' (ps, l', ss) = (IM.insert v l ps, l', ss)+ addSucc' (ps, l', ss) = (ps, l', IM.insertWith addLists w [l] ss)+ addPred' (ps, l', ss) = (IM.insertWith addLists v [l] ps, l', ss) {-# RULES@@ -134,15 +138,17 @@ fastEMap f (Gr g) = Gr (IM.map f' g) where f' :: Context' a b -> Context' a c- f' (ps, a, ss) = (IM.map f ps, a, IM.map f ss)+ f' (ps, a, ss) = (IM.map (map f) ps, a, IM.map (map f) ss) -toAdj :: IntMap b -> Adj b-toAdj = map swap . IM.toList+toAdj :: IntMap [b] -> Adj b+toAdj = concatMap expand . IM.toList+ where+ expand (n,ls) = map (flip (,) n) ls -fromAdj :: Adj b -> IntMap b-fromAdj = IM.fromList . map swap+fromAdj :: Adj b -> IntMap [b]+fromAdj = IM.fromListWith addLists . map (second return . swap) toContext :: Node -> Context' a b -> Context a b@@ -159,12 +165,21 @@ swap (a, b) = (b, a) +-- A version of @++@ where order isn't important, so @xs ++ [x]@+-- becomes @x:xs@. Used when we have to have a function of type @[a]+-- -> [a] -> [a]@ but one of the lists is just going to be a single+-- element (and it isn't possible to tell which).+addLists :: [a] -> [a] -> [a]+addLists [a] as = a : as+addLists as [a] = a : as+addLists xs ys = xs ++ ys+ addSucc :: GraphRep a b -> Node -> [(b, Node)] -> GraphRep a b addSucc g _ [] = g addSucc g v ((l, p) : rest) = addSucc g' v rest where g' = IM.adjust f p g- f (ps, l', ss) = (ps, l', IM.insert v l ss)+ f (ps, l', ss) = (ps, l', IM.insertWith addLists v [l] ss) addPred :: GraphRep a b -> Node -> [(b, Node)] -> GraphRep a b@@ -172,7 +187,7 @@ addPred g v ((l, s) : rest) = addPred g' v rest where g' = IM.adjust f s g- f (ps, l', ss) = (IM.insert v l ps, l', ss)+ f (ps, l', ss) = (IM.insertWith addLists v [l] ps, l', ss) clearSucc :: GraphRep a b -> Node -> [Node] -> GraphRep a b
LICENSE view
@@ -1,4 +1,5 @@-Copyright (c) 1999-2007, Martin Erwig+Copyright (c) 1999-2008, Martin Erwig+ 2010, Ivan Lazar Miljenovic All rights reserved. Redistribution and use in source and binary forms, with or without
− doc/CHANGES
@@ -1,120 +0,0 @@-CHANGES (FGL/HASKELL, Version: November 2008)-------------------------------------------------November 2008---------------* Bugfix in Graphviz.sq---June 2008-----------* bug fix in bcc by Reid Barton-* added new dynamic graph implementation: - Data.Graph.Inductive.PatriciaTree (thanks to Pho)-* added test/benchmark.hs: a benchmark to compare Tree and PatriciaTree- implementations (thanks to Pho)---May 2008----------* added Setup.hs to tar file-* reimplementation of Data.Graph.Inductive.Query.Dominators- by Bertram Felgenhauer:- It was buggy and very slow for large graphs. See- http://www.haskell.org/pipermail/haskell-cafe/2008-April/041739.html- This patch also adds a new function, iDom, that returns the immediate- dominators of the graph nodes.-* Exported xdf*With functions from DFS.hs-* many little cleanups thanks to many people - (use 'darcs changes' to see the details)---April 2007------------* changed the implementation for inspection functions (suc, pred, ...)- to correct the behavior in the presence of loops - (thanks to Ralf Juengling for pointing out the inconsistency)---June 2006-----------* fixed a bug in findP (thanks to lnagy@fit.edu)-* added function delLEdge in Graph.hs (thanks to Jose Labra)-* changed implementation of updFM and mkGraph (thanks to Don Stewart)---February 2005---------------* fixed an import error in Basic.hs -* removed Eq instance of gr because it caused overlapping instance problems.- Instead the function equal defined in Graph.hs can be used-* added some more functions to the export list of DFS.hs-* changed the definition of LPath into a newtype to avoid- overlapping instances with lists-* fixed the Makefile (for GHC and GHCi)---January 2004--------------* bug fix for nearestNode (src/Data/Graph/Inductive/Query/GVD.hs)-Update contributed by Aetion Technologies LLC (www.aetion.com)-* Refactor into hierarchical namespace-* Build changes:- - build a standard haskell library (libHSfgl.a, HSfgl.o)- - install as ghc package (fgl), uses Auto so no -package is needed-* Automatic Node generation for labels: Data.Graph.Inductive.NodeMap-* Graphviz output: Data.Graph.Inductive.Graphviz---September 2002----------------* Introduction of graph classes-* Monadic graphs and graph computation monad-* Graph implementation based on balanced (AVL) trees -* Fast graph implementation based on IO arrays-* New algorithms:- - Maximum flow- - Articulation points- - biconnected components- - dominators- - transitive closure-* minor changes in utility functions- - changed signatures (swapped order of arguments) of - functions context and lab to be consistent with other graph functions- - changed function first in RootPath: not existing path is now reported - as an empty list and will not produce an error- - esp version that returns a list of labeled edges- (to find minimum label in maxflow algorithm)- - BFS uses amortized O(1) queue- - Heap stores key and value separately- - ...---March 2001------------* Changes to User Guide-* a couple of new functions-* some internal changes---April 2000------------* User Guide-* Systematic structure for all depth-first search functions-* Graph Voronoi diagram-* Several small changes and additions in utility functions---February 2000---------------* Representation for inward-directed trees-* Breadth-first search-* Dijkstra's algorithm-* Minimum-spanning-tree algorithm---August 1999-------------* First Haskell version-
− doc/README
@@ -1,115 +0,0 @@--------------------------------------------------------------------------------FGL - Functional Graph Library, Version: January 2004----------------------------------------------------------------------------------CONTENTS- A. CONTENTS- B. TESTING- C. CREDITS- D. CONTACT-----------------------------------------------------------------------------------A. CONTENTS--In addition to the files doc/README, doc/COPYRIGHT, doc/CHANGES, Makefile,-package.conf.in, and prologue.txt this distribution consists of the following-28 Haskell files.--(A) These files define inductive graphs and basic operations:-- Data/Graph/Inductive.hs - Main module- Data/Graph/Inductive/Graph.hs - Static and dynamic graph classes,- derived types & operations- Data/Graph/Inductive/Tree.hs - Dynamic graph implementation- Data/Graph/Inductive/Basic.hs - Basic graph operations (gmap,- grev, ...)- Data/Graph/Inductive/NodeMap.hs - Automatic generation of Nodes- from labels.- Data/Graph/Inductive/Graphviz.hs - Graphviz output.- Data/Graph/Inductive/Monad/Monad.hs - Monadic (static) graph class- based on balanced search trees- Data/Graph/Inductive/Monad/IOArray.hs - Static graph implementation based- on IO Arrays---(B) Example graphs:-- Data/Graph/Inductive/Example.hs - Example graphs- --(C) Implementation of graph algorithms:-- Data/Graph/Inductive/Query.hs - Main query module- Data/Graph/Inductive/Query/DFS.hs - Depth-first search and- derived operations (topsort,- scc, ...)- Data/Graph/Inductive/Query/BFS.hs - Breadth-first search and- "edge" shortest paths- Data/Graph/Inductive/Query/SP.hs - Shortest paths (Dijkstra's- algorithm)- Data/Graph/Inductive/Query/GVD.hs - Graph voronoi diagram- Data/Graph/Inductive/Query/MST.hs - Minimum spanning tree (Prim's- algorithm)- Data/Graph/Inductive/Query/Indep.hs - Independent node sets- Data/Graph/Inductive/Query/MaxFlow.hs - Edmonds/Karp maximum flow- algorithm- Data/Graph/Inductive/Query/MaxFlow2.hs - Alternative implementations- of the Edmonds/Karp algorithm- Data/Graph/Inductive/Query/ArtPoint.hs - Articulation points- Data/Graph/Inductive/Query/BCC.hs - Biconnected components- Data/Graph/Inductive/Query/Dominators.hs - Dominators- Data/Graph/Inductive/Query/TransClos.hs - Transitive closure- Data/Graph/Inductive/Query/Monad.hs - Graph transformer monad and- monadic graph algorithms- --(D) Some auxiliary modules:-- Data/Graph/Inductive/Inductive/RootPath.hs - Inward-directed trees- Data/Graph/Inductive/Inductive/Heap.hs - Pairing heaps - Data/Graph/Inductive/Inductive/Queue.hs - Amortized O(1) queue- implementation - Data/Graph/Inductive/Inductive/FiniteMap.hs - Binary-search-tree- implementation of maps- Data/Graph/Inductive/Inductive/Thread.hs - Auxiliary module used in Graph- (subject to future change)- ----------------------------------------------------------------------------------B. TESTING--B.1 GHC-- 1. Run the test program: "ghci test/test.hs"---B.2 Hugs-- 1. Start Hugs: "hugs -98 +o"- - 2. Load the FGL: ":l Data.Graph.Inductive.Example"-- 3. Play with it, e.g., enter: "sp 1 3 clr528"-----------------------------------------------------------------------------------C. CREDITS--I am grateful to many people who have helped me with bug reports, questions,-comments, and implementations to improve the FGL. In particular, I would like-to thank Martin Boehme, Luis Zeron, and Hal Daume for their contributions.-Moreover, I would like to thank Abe Egnor and Isaac Jones at Aetion-Technologies who refactored the modules into the new hierarchical name space-and who have added two modules (see also the file CHANGES).-----------------------------------------------------------------------------------D. BUG REPORTS, QUESTIONS, SUGGESTIONS, ...--Please email comments, bug reports, etc. to erwig@cs.orst.edu
fgl.cabal view
@@ -1,9 +1,9 @@ name: fgl-version: 5.4.2.2+version: 5.4.2.3 license: BSD3 license-file: LICENSE-author: Martin Erwig-maintainer: Martin Erwig+author: Martin Erwig, Ivan Lazar Miljenovic+maintainer: Ivan.Miljenovic@gmail.com, tomberek@gmail.com homepage: http://web.engr.oregonstate.edu/~erwig/fgl/haskell category: Data Structures synopsis: Martin Erwig's Functional Graph Library@@ -37,6 +37,6 @@ Data.Graph.Inductive.Query.SP, Data.Graph.Inductive.Query.TransClos, Data.Graph.Inductive-build-depends: base, mtl, containers, array+build-depends: base < 5, mtl, containers, array extensions: MultiParamTypeClasses, OverlappingInstances, FlexibleInstances, ScopedTypeVariables build-type: Simple
− prologue.txt
@@ -1,1 +0,0 @@-Martin Erwig\'s Functional Graph Library.
− test/bcc.hs
@@ -1,16 +0,0 @@-module Main where--import Data.Graph.Inductive-import List--mkUndirectedUGraph v e = mkUGraph v [ (x, y) | (x0, y0) <- e, (x, y) <- [(x0, y0), (y0, x0)] ]--graph :: Gr () ()-graph = mkUndirectedUGraph [1..5] [(1, 2), (2, 3), (2, 4), (3, 5)]--bccEdges g = sort (concat $ map edges $ bcc g) == sort (edges g)--prop_bcc = bccEdges graph--main = do- print prop_bcc
− test/benchmark.hs
@@ -1,138 +0,0 @@-{-- Install microbench to build this program:- http://hackage.haskell.org/cgi-bin/hackage-scripts/package/microbench-- % ghc -O --make benchmark- % ./benchmark- [1 of 1] Compiling Main ( benchmark.hs, benchmark.o )- Linking benchmark ...- * insNode into AVL tree: ..................- 8.877ns per iteration / 112655.53 per second.- * insNode into PATRICIA tree: .....................- 1.788ns per iteration / 559342.86 per second.- * insEdge into AVL tree: ...........- 2833.029ns per iteration / 352.98 per second.- * insEdge into PATRICIA tree: ...................- 4.625ns per iteration / 216224.60 per second.- * gmap on AVL tree: ................- 32.754ns per iteration / 30530.57 per second.- * gmap on PATRICIA tree: .....................- 1.623ns per iteration / 616056.37 per second.- * nmap on AVL tree: ................- 35.455ns per iteration / 28204.95 per second.- * nmap on PATRICIA tree: .....................- 1.713ns per iteration / 583758.06 per second.- * emap on AVL tree: ...........- 4416.303ns per iteration / 226.43 per second.- * emap on PATRICIA tree: ...................- 4.532ns per iteration / 220663.09 per second.--}--import Data.Graph.Inductive.Graph-import qualified Data.Graph.Inductive.Tree as AVL-import qualified Data.Graph.Inductive.PatriciaTree as Patricia-import Microbench---main :: IO ()-main = do microbench "insNode into AVL tree" insNodeAVL- microbench "insNode into PATRICIA tree" insNodePatricia-- microbench "insEdge into AVL tree" insEdgeAVL- microbench "insEdge into PATRICIA tree" insEdgePatricia-- microbench "gmap on AVL tree" gmapAVL- microbench "gmap on PATRICIA tree" gmapPatricia-- microbench "nmap on AVL tree" nmapAVL- microbench "nmap on PATRICIA tree" nmapPatricia-- microbench "emap on AVL tree" emapAVL- microbench "emap on PATRICIA tree" emapPatricia---insNodeAVL :: Int -> AVL.UGr-insNodeAVL = insNodes' empty---insNodePatricia :: Int -> Patricia.UGr-insNodePatricia = insNodes' empty---{-# INLINE insNodes' #-}-insNodes' :: DynGraph gr => gr () b -> Int -> gr () b-insNodes' g 0 = g-insNodes' g n = let [v] = newNodes 1 g- g' = insNode (v, ()) g- in- insNodes' g' (n - 1)---insEdgeAVL :: Int -> AVL.UGr-insEdgeAVL n = insEdges' (insNodeAVL n) n---insEdgePatricia :: Int -> Patricia.UGr-insEdgePatricia n = insEdges' (insNodePatricia n) n---{-# INLINE insEdges' #-}-insEdges' :: DynGraph gr => gr a () -> Int -> gr a ()-insEdges' g 0 = g-insEdges' g n = let g' = insEdge (1, n, ()) g- in- insEdges' g' (n - 1)---gmapAVL :: Int -> AVL.Gr Int ()-gmapAVL n- = let g = insNodeAVL n- g' = gmap f g- f (ps, v, _, ss) = (ps, v, v, ss)- in- g'---gmapPatricia :: Int -> Patricia.Gr Int ()-gmapPatricia n- = let g = insNodePatricia n- g' = gmap f g- f (ps, v, _, ss) = (ps, v, v, ss)- in- g'---nmapAVL :: Int -> AVL.Gr Int ()-nmapAVL n- = let g = insNodeAVL n- g' = nmap f g- f _ = n- in- g'---nmapPatricia :: Int -> Patricia.Gr Int ()-nmapPatricia n- = let g = insNodePatricia n- g' = nmap f g- f _ = n- in- g'---emapAVL :: Int -> AVL.Gr () Int-emapAVL n- = let g = insEdgeAVL n- g' = emap f g- f _ = n- in- g'---emapPatricia :: Int -> Patricia.Gr () Int-emapPatricia n- = let g = insEdgePatricia n- g' = emap f g- f _ = n- in- g'
− test/test.hs
@@ -1,29 +0,0 @@-module Main where--import Data.Graph.Inductive-import Data.Graph.Inductive.Example--main :: IO ()-main = return ()--m486 :: NodeMap String-m486 = fromGraph clr486--t1 :: Gr String ()-t1 = insMapEdge m486 ("shirt", "watch", ()) clr486--t2 :: Gr String ()-t2 = insMapEdge m486 ("watch", "pants", ()) t1--t3 :: Gr Char String-t3 = run_ empty $- do insMapNodeM 'a'- insMapNodeM 'b'- insMapNodeM 'c'- insMapEdgesM [('a', 'b', "right"),- ('b', 'a', "left"),- ('b', 'c', "down"),- ('c', 'a', "up")]--t4 :: Gr String ()-t4 = run_ clr486 $ insMapEdgeM ("shirt", "watch", ())