fgl 5.4.2.0 → 5.4.2.2
raw patch · 10 files changed
+405/−22 lines, 10 filesdep ~basenew-uploaderPVP: major bump suggested
API removals or changes: PVP suggests a major version bump
Dependency ranges changed: base
API changes (from Hackage documentation)
- Data.Graph.Inductive.Graph: instance [overlap ok] (Show a) => Show (LPath a)
- Data.Graph.Inductive.Internal.RootPath: instance [overlap ok] (Eq a) => Eq (LPath a)
- Data.Graph.Inductive.Internal.RootPath: instance [overlap ok] (Ord a) => Ord (LPath a)
- Data.Graph.Inductive.Query.ArtPoint: instance [overlap ok] (Eq a) => Eq (DFSTree a)
- Data.Graph.Inductive.Query.ArtPoint: instance [overlap ok] (Eq a) => Eq (LOWTree a)
- Data.Graph.Inductive.Query.Monad: instance [overlap ok] (Monad m) => Monad (GT m g)
+ Data.Graph.Inductive.Graph: instance [overlap ok] Show a => Show (LPath a)
+ Data.Graph.Inductive.Internal.RootPath: instance [overlap ok] Eq a => Eq (LPath a)
+ Data.Graph.Inductive.Internal.RootPath: instance [overlap ok] Ord a => Ord (LPath a)
+ Data.Graph.Inductive.PatriciaTree: data Gr a b
+ Data.Graph.Inductive.PatriciaTree: instance [overlap ok] DynGraph Gr
+ Data.Graph.Inductive.PatriciaTree: instance [overlap ok] Graph Gr
+ Data.Graph.Inductive.PatriciaTree: type UGr = Gr () ()
+ Data.Graph.Inductive.Query.ArtPoint: instance [overlap ok] Eq a => Eq (DFSTree a)
+ Data.Graph.Inductive.Query.ArtPoint: instance [overlap ok] Eq a => Eq (LOWTree a)
+ Data.Graph.Inductive.Query.Monad: instance [overlap ok] Monad m => Monad (GT m g)
- Data.Graph.Inductive.Basic: efilter :: (DynGraph gr) => (LEdge b -> Bool) -> gr a b -> gr a b
+ Data.Graph.Inductive.Basic: efilter :: DynGraph gr => (LEdge b -> Bool) -> gr a b -> gr a b
- Data.Graph.Inductive.Basic: elfilter :: (DynGraph gr) => (b -> Bool) -> gr a b -> gr a b
+ Data.Graph.Inductive.Basic: elfilter :: DynGraph gr => (b -> Bool) -> gr a b -> gr a b
- Data.Graph.Inductive.Basic: gfold :: (Graph gr) => ((Context a b) -> [Node]) -> ((Context a b) -> c -> d) -> (Maybe d -> c -> c, c) -> [Node] -> gr a b -> c
+ Data.Graph.Inductive.Basic: gfold :: Graph gr => ((Context a b) -> [Node]) -> ((Context a b) -> c -> d) -> (Maybe d -> c -> c, c) -> [Node] -> gr a b -> c
- Data.Graph.Inductive.Basic: grev :: (DynGraph gr) => gr a b -> gr a b
+ Data.Graph.Inductive.Basic: grev :: DynGraph gr => gr a b -> gr a b
- Data.Graph.Inductive.Basic: gsel :: (Graph gr) => (Context a b -> Bool) -> gr a b -> [Context a b]
+ Data.Graph.Inductive.Basic: gsel :: Graph gr => (Context a b -> Bool) -> gr a b -> [Context a b]
- Data.Graph.Inductive.Basic: hasLoop :: (Graph gr) => gr a b -> Bool
+ Data.Graph.Inductive.Basic: hasLoop :: Graph gr => gr a b -> Bool
- Data.Graph.Inductive.Basic: isSimple :: (Graph gr) => gr a b -> Bool
+ Data.Graph.Inductive.Basic: isSimple :: Graph gr => gr a b -> Bool
- Data.Graph.Inductive.Basic: unlab :: (DynGraph gr) => gr a b -> gr () ()
+ Data.Graph.Inductive.Basic: unlab :: DynGraph gr => gr a b -> gr () ()
- Data.Graph.Inductive.Example: genLNodes :: (Enum a) => a -> Int -> [LNode a]
+ Data.Graph.Inductive.Example: genLNodes :: Enum a => a -> Int -> [LNode a]
- Data.Graph.Inductive.Example: star :: (Graph gr) => Int -> gr () ()
+ Data.Graph.Inductive.Example: star :: Graph gr => Int -> gr () ()
- Data.Graph.Inductive.Example: starM :: (GraphM m gr) => Int -> m (gr () ())
+ Data.Graph.Inductive.Example: starM :: GraphM m gr => Int -> m (gr () ())
- Data.Graph.Inductive.Example: ucycle :: (Graph gr) => Int -> gr () ()
+ Data.Graph.Inductive.Example: ucycle :: Graph gr => Int -> gr () ()
- Data.Graph.Inductive.Example: ucycleM :: (GraphM m gr) => Int -> m (gr () ())
+ Data.Graph.Inductive.Example: ucycleM :: GraphM m gr => Int -> m (gr () ())
- Data.Graph.Inductive.Graph: (&) :: (DynGraph gr) => Context a b -> gr a b -> gr a b
+ Data.Graph.Inductive.Graph: (&) :: DynGraph gr => Context a b -> gr a b -> gr a b
- Data.Graph.Inductive.Graph: buildGr :: (DynGraph gr) => [Context a b] -> gr a b
+ Data.Graph.Inductive.Graph: buildGr :: DynGraph gr => [Context a b] -> gr a b
- Data.Graph.Inductive.Graph: class (Graph gr) => DynGraph gr
+ Data.Graph.Inductive.Graph: class Graph gr => DynGraph gr
- Data.Graph.Inductive.Graph: context :: (Graph gr) => gr a b -> Node -> Context a b
+ Data.Graph.Inductive.Graph: context :: Graph gr => gr a b -> Node -> Context a b
- Data.Graph.Inductive.Graph: deg :: (Graph gr) => gr a b -> Node -> Int
+ Data.Graph.Inductive.Graph: deg :: Graph gr => gr a b -> Node -> Int
- Data.Graph.Inductive.Graph: delEdge :: (DynGraph gr) => Edge -> gr a b -> gr a b
+ Data.Graph.Inductive.Graph: delEdge :: DynGraph gr => Edge -> gr a b -> gr a b
- Data.Graph.Inductive.Graph: delEdges :: (DynGraph gr) => [Edge] -> gr a b -> gr a b
+ Data.Graph.Inductive.Graph: delEdges :: DynGraph gr => [Edge] -> gr a b -> gr a b
- Data.Graph.Inductive.Graph: delNode :: (Graph gr) => Node -> gr a b -> gr a b
+ Data.Graph.Inductive.Graph: delNode :: Graph gr => Node -> gr a b -> gr a b
- Data.Graph.Inductive.Graph: delNodes :: (Graph gr) => [Node] -> gr a b -> gr a b
+ Data.Graph.Inductive.Graph: delNodes :: Graph gr => [Node] -> gr a b -> gr a b
- Data.Graph.Inductive.Graph: edges :: (Graph gr) => gr a b -> [Edge]
+ Data.Graph.Inductive.Graph: edges :: Graph gr => gr a b -> [Edge]
- Data.Graph.Inductive.Graph: emap :: (DynGraph gr) => (b -> c) -> gr a b -> gr a c
+ Data.Graph.Inductive.Graph: emap :: DynGraph gr => (b -> c) -> gr a b -> gr a c
- Data.Graph.Inductive.Graph: empty :: (Graph gr) => gr a b
+ Data.Graph.Inductive.Graph: empty :: Graph gr => gr a b
- Data.Graph.Inductive.Graph: gelem :: (Graph gr) => Node -> gr a b -> Bool
+ Data.Graph.Inductive.Graph: gelem :: Graph gr => Node -> gr a b -> Bool
- Data.Graph.Inductive.Graph: gmap :: (DynGraph gr) => (Context a b -> Context c d) -> gr a b -> gr c d
+ Data.Graph.Inductive.Graph: gmap :: DynGraph gr => (Context a b -> Context c d) -> gr a b -> gr c d
- Data.Graph.Inductive.Graph: indeg :: (Graph gr) => gr a b -> Node -> Int
+ Data.Graph.Inductive.Graph: indeg :: Graph gr => gr a b -> Node -> Int
- Data.Graph.Inductive.Graph: inn :: (Graph gr) => gr a b -> Node -> [LEdge b]
+ Data.Graph.Inductive.Graph: inn :: Graph gr => gr a b -> Node -> [LEdge b]
- Data.Graph.Inductive.Graph: insEdge :: (DynGraph gr) => LEdge b -> gr a b -> gr a b
+ Data.Graph.Inductive.Graph: insEdge :: DynGraph gr => LEdge b -> gr a b -> gr a b
- Data.Graph.Inductive.Graph: insEdges :: (DynGraph gr) => [LEdge b] -> gr a b -> gr a b
+ Data.Graph.Inductive.Graph: insEdges :: DynGraph gr => [LEdge b] -> gr a b -> gr a b
- Data.Graph.Inductive.Graph: insNode :: (DynGraph gr) => LNode a -> gr a b -> gr a b
+ Data.Graph.Inductive.Graph: insNode :: DynGraph gr => LNode a -> gr a b -> gr a b
- Data.Graph.Inductive.Graph: insNodes :: (DynGraph gr) => [LNode a] -> gr a b -> gr a b
+ Data.Graph.Inductive.Graph: insNodes :: DynGraph gr => [LNode a] -> gr a b -> gr a b
- Data.Graph.Inductive.Graph: isEmpty :: (Graph gr) => gr a b -> Bool
+ Data.Graph.Inductive.Graph: isEmpty :: Graph gr => gr a b -> Bool
- Data.Graph.Inductive.Graph: lab :: (Graph gr) => gr a b -> Node -> Maybe a
+ Data.Graph.Inductive.Graph: lab :: Graph gr => gr a b -> Node -> Maybe a
- Data.Graph.Inductive.Graph: labEdges :: (Graph gr) => gr a b -> [LEdge b]
+ Data.Graph.Inductive.Graph: labEdges :: Graph gr => gr a b -> [LEdge b]
- Data.Graph.Inductive.Graph: labNodes :: (Graph gr) => gr a b -> [LNode a]
+ Data.Graph.Inductive.Graph: labNodes :: Graph gr => gr a b -> [LNode a]
- Data.Graph.Inductive.Graph: lpre :: (Graph gr) => gr a b -> Node -> [(Node, b)]
+ Data.Graph.Inductive.Graph: lpre :: Graph gr => gr a b -> Node -> [(Node, b)]
- Data.Graph.Inductive.Graph: lsuc :: (Graph gr) => gr a b -> Node -> [(Node, b)]
+ Data.Graph.Inductive.Graph: lsuc :: Graph gr => gr a b -> Node -> [(Node, b)]
- Data.Graph.Inductive.Graph: match :: (Graph gr) => Node -> gr a b -> Decomp gr a b
+ Data.Graph.Inductive.Graph: match :: Graph gr => Node -> gr a b -> Decomp gr a b
- Data.Graph.Inductive.Graph: matchAny :: (Graph gr) => gr a b -> GDecomp gr a b
+ Data.Graph.Inductive.Graph: matchAny :: Graph gr => gr a b -> GDecomp gr a b
- Data.Graph.Inductive.Graph: mkGraph :: (Graph gr) => [LNode a] -> [LEdge b] -> gr a b
+ Data.Graph.Inductive.Graph: mkGraph :: Graph gr => [LNode a] -> [LEdge b] -> gr a b
- Data.Graph.Inductive.Graph: mkUGraph :: (Graph gr) => [Node] -> [Edge] -> gr () ()
+ Data.Graph.Inductive.Graph: mkUGraph :: Graph gr => [Node] -> [Edge] -> gr () ()
- Data.Graph.Inductive.Graph: neighbors :: (Graph gr) => gr a b -> Node -> [Node]
+ Data.Graph.Inductive.Graph: neighbors :: Graph gr => gr a b -> Node -> [Node]
- Data.Graph.Inductive.Graph: newNodes :: (Graph gr) => Int -> gr a b -> [Node]
+ Data.Graph.Inductive.Graph: newNodes :: Graph gr => Int -> gr a b -> [Node]
- Data.Graph.Inductive.Graph: nmap :: (DynGraph gr) => (a -> c) -> gr a b -> gr c b
+ Data.Graph.Inductive.Graph: nmap :: DynGraph gr => (a -> c) -> gr a b -> gr c b
- Data.Graph.Inductive.Graph: noNodes :: (Graph gr) => gr a b -> Int
+ Data.Graph.Inductive.Graph: noNodes :: Graph gr => gr a b -> Int
- Data.Graph.Inductive.Graph: nodeRange :: (Graph gr) => gr a b -> (Node, Node)
+ Data.Graph.Inductive.Graph: nodeRange :: Graph gr => gr a b -> (Node, Node)
- Data.Graph.Inductive.Graph: nodes :: (Graph gr) => gr a b -> [Node]
+ Data.Graph.Inductive.Graph: nodes :: Graph gr => gr a b -> [Node]
- Data.Graph.Inductive.Graph: out :: (Graph gr) => gr a b -> Node -> [LEdge b]
+ Data.Graph.Inductive.Graph: out :: Graph gr => gr a b -> Node -> [LEdge b]
- Data.Graph.Inductive.Graph: outdeg :: (Graph gr) => gr a b -> Node -> Int
+ Data.Graph.Inductive.Graph: outdeg :: Graph gr => gr a b -> Node -> Int
- Data.Graph.Inductive.Graph: pre :: (Graph gr) => gr a b -> Node -> [Node]
+ Data.Graph.Inductive.Graph: pre :: Graph gr => gr a b -> Node -> [Node]
- Data.Graph.Inductive.Graph: suc :: (Graph gr) => gr a b -> Node -> [Node]
+ Data.Graph.Inductive.Graph: suc :: Graph gr => gr a b -> Node -> [Node]
- Data.Graph.Inductive.Graph: ufold :: (Graph gr) => ((Context a b) -> c -> c) -> c -> gr a b -> c
+ Data.Graph.Inductive.Graph: ufold :: Graph gr => ((Context a b) -> c -> c) -> c -> gr a b -> c
- Data.Graph.Inductive.Internal.FiniteMap: accumFM :: (Ord a) => FiniteMap a b -> a -> (b -> b -> b) -> b -> FiniteMap a b
+ Data.Graph.Inductive.Internal.FiniteMap: accumFM :: Ord a => FiniteMap a b -> a -> (b -> b -> b) -> b -> FiniteMap a b
- Data.Graph.Inductive.Internal.FiniteMap: addToFM :: (Ord a) => FiniteMap a b -> a -> b -> FiniteMap a b
+ Data.Graph.Inductive.Internal.FiniteMap: addToFM :: Ord a => FiniteMap a b -> a -> b -> FiniteMap a b
- Data.Graph.Inductive.Internal.FiniteMap: data (Ord a) => FiniteMap a b
+ Data.Graph.Inductive.Internal.FiniteMap: data Ord a => FiniteMap a b
- Data.Graph.Inductive.Internal.FiniteMap: delFromFM :: (Ord a) => FiniteMap a b -> a -> FiniteMap a b
+ Data.Graph.Inductive.Internal.FiniteMap: delFromFM :: Ord a => FiniteMap a b -> a -> FiniteMap a b
- Data.Graph.Inductive.Internal.FiniteMap: elemFM :: (Ord a) => FiniteMap a b -> a -> Bool
+ Data.Graph.Inductive.Internal.FiniteMap: elemFM :: Ord a => FiniteMap a b -> a -> Bool
- Data.Graph.Inductive.Internal.FiniteMap: emptyFM :: (Ord a) => FiniteMap a b
+ Data.Graph.Inductive.Internal.FiniteMap: emptyFM :: Ord a => FiniteMap a b
- Data.Graph.Inductive.Internal.FiniteMap: fmToList :: (Ord a) => FiniteMap a b -> [(a, b)]
+ Data.Graph.Inductive.Internal.FiniteMap: fmToList :: Ord a => FiniteMap a b -> [(a, b)]
- Data.Graph.Inductive.Internal.FiniteMap: lookupFM :: (Ord a) => FiniteMap a b -> a -> Maybe b
+ Data.Graph.Inductive.Internal.FiniteMap: lookupFM :: Ord a => FiniteMap a b -> a -> Maybe b
- Data.Graph.Inductive.Internal.FiniteMap: maxFM :: (Ord a) => FiniteMap a b -> Maybe (a, b)
+ Data.Graph.Inductive.Internal.FiniteMap: maxFM :: Ord a => FiniteMap a b -> Maybe (a, b)
- Data.Graph.Inductive.Internal.FiniteMap: minFM :: (Ord a) => FiniteMap a b -> Maybe (a, b)
+ Data.Graph.Inductive.Internal.FiniteMap: minFM :: Ord a => FiniteMap a b -> Maybe (a, b)
- Data.Graph.Inductive.Internal.FiniteMap: predFM :: (Ord a) => FiniteMap a b -> a -> Maybe (a, b)
+ Data.Graph.Inductive.Internal.FiniteMap: predFM :: Ord a => FiniteMap a b -> a -> Maybe (a, b)
- Data.Graph.Inductive.Internal.FiniteMap: rangeFM :: (Ord a) => FiniteMap a b -> a -> a -> [b]
+ Data.Graph.Inductive.Internal.FiniteMap: rangeFM :: Ord a => FiniteMap a b -> a -> a -> [b]
- Data.Graph.Inductive.Internal.FiniteMap: sizeFM :: (Ord a) => FiniteMap a b -> Int
+ Data.Graph.Inductive.Internal.FiniteMap: sizeFM :: Ord a => FiniteMap a b -> Int
- Data.Graph.Inductive.Internal.FiniteMap: splitFM :: (Ord a) => FiniteMap a b -> a -> Maybe (FiniteMap a b, (a, b))
+ Data.Graph.Inductive.Internal.FiniteMap: splitFM :: Ord a => FiniteMap a b -> a -> Maybe (FiniteMap a b, (a, b))
- Data.Graph.Inductive.Internal.FiniteMap: splitMinFM :: (Ord a) => FiniteMap a b -> Maybe (FiniteMap a b, (a, b))
+ Data.Graph.Inductive.Internal.FiniteMap: splitMinFM :: Ord a => FiniteMap a b -> Maybe (FiniteMap a b, (a, b))
- Data.Graph.Inductive.Internal.FiniteMap: succFM :: (Ord a) => FiniteMap a b -> a -> Maybe (a, b)
+ Data.Graph.Inductive.Internal.FiniteMap: succFM :: Ord a => FiniteMap a b -> a -> Maybe (a, b)
- Data.Graph.Inductive.Internal.FiniteMap: updFM :: (Ord a) => FiniteMap a b -> a -> (b -> b) -> FiniteMap a b
+ Data.Graph.Inductive.Internal.FiniteMap: updFM :: Ord a => FiniteMap a b -> a -> (b -> b) -> FiniteMap a b
- Data.Graph.Inductive.Internal.Heap: build :: (Ord a) => [(a, b)] -> Heap a b
+ Data.Graph.Inductive.Internal.Heap: build :: Ord a => [(a, b)] -> Heap a b
- Data.Graph.Inductive.Internal.Heap: data (Ord a) => Heap a b
+ Data.Graph.Inductive.Internal.Heap: data Ord a => Heap a b
- Data.Graph.Inductive.Internal.Heap: deleteMin :: (Ord a) => Heap a b -> Heap a b
+ Data.Graph.Inductive.Internal.Heap: deleteMin :: Ord a => Heap a b -> Heap a b
- Data.Graph.Inductive.Internal.Heap: empty :: (Ord a) => Heap a b
+ Data.Graph.Inductive.Internal.Heap: empty :: Ord a => Heap a b
- Data.Graph.Inductive.Internal.Heap: findMin :: (Ord a) => Heap a b -> (a, b)
+ Data.Graph.Inductive.Internal.Heap: findMin :: Ord a => Heap a b -> (a, b)
- Data.Graph.Inductive.Internal.Heap: heapsort :: (Ord a) => [a] -> [a]
+ Data.Graph.Inductive.Internal.Heap: heapsort :: Ord a => [a] -> [a]
- Data.Graph.Inductive.Internal.Heap: insert :: (Ord a) => (a, b) -> Heap a b -> Heap a b
+ Data.Graph.Inductive.Internal.Heap: insert :: Ord a => (a, b) -> Heap a b -> Heap a b
- Data.Graph.Inductive.Internal.Heap: isEmpty :: (Ord a) => Heap a b -> Bool
+ Data.Graph.Inductive.Internal.Heap: isEmpty :: Ord a => Heap a b -> Bool
- Data.Graph.Inductive.Internal.Heap: merge :: (Ord a) => Heap a b -> Heap a b -> Heap a b
+ Data.Graph.Inductive.Internal.Heap: merge :: Ord a => Heap a b -> Heap a b -> Heap a b
- Data.Graph.Inductive.Internal.Heap: mergeAll :: (Ord a) => [Heap a b] -> Heap a b
+ Data.Graph.Inductive.Internal.Heap: mergeAll :: Ord a => [Heap a b] -> Heap a b
- Data.Graph.Inductive.Internal.Heap: splitMin :: (Ord a) => Heap a b -> (a, b, Heap a b)
+ Data.Graph.Inductive.Internal.Heap: splitMin :: Ord a => Heap a b -> (a, b, Heap a b)
- Data.Graph.Inductive.Internal.Heap: toList :: (Ord a) => Heap a b -> [(a, b)]
+ Data.Graph.Inductive.Internal.Heap: toList :: Ord a => Heap a b -> [(a, b)]
- Data.Graph.Inductive.Internal.Heap: unit :: (Ord a) => a -> b -> Heap a b
+ Data.Graph.Inductive.Internal.Heap: unit :: Ord a => a -> b -> Heap a b
- Data.Graph.Inductive.Monad: class (Monad m) => GraphM m gr
+ Data.Graph.Inductive.Monad: class Monad m => GraphM m gr
- Data.Graph.Inductive.Monad: contextM :: (GraphM m gr) => m (gr a b) -> Node -> m (Context a b)
+ Data.Graph.Inductive.Monad: contextM :: GraphM m gr => m (gr a b) -> Node -> m (Context a b)
- Data.Graph.Inductive.Monad: delNodeM :: (GraphM m gr) => Node -> m (gr a b) -> m (gr a b)
+ Data.Graph.Inductive.Monad: delNodeM :: GraphM m gr => Node -> m (gr a b) -> m (gr a b)
- Data.Graph.Inductive.Monad: delNodesM :: (GraphM m gr) => [Node] -> m (gr a b) -> m (gr a b)
+ Data.Graph.Inductive.Monad: delNodesM :: GraphM m gr => [Node] -> m (gr a b) -> m (gr a b)
- Data.Graph.Inductive.Monad: edgesM :: (GraphM m gr) => m (gr a b) -> m [Edge]
+ Data.Graph.Inductive.Monad: edgesM :: GraphM m gr => m (gr a b) -> m [Edge]
- Data.Graph.Inductive.Monad: emptyM :: (GraphM m gr) => m (gr a b)
+ Data.Graph.Inductive.Monad: emptyM :: GraphM m gr => m (gr a b)
- Data.Graph.Inductive.Monad: isEmptyM :: (GraphM m gr) => m (gr a b) -> m Bool
+ Data.Graph.Inductive.Monad: isEmptyM :: GraphM m gr => m (gr a b) -> m Bool
- Data.Graph.Inductive.Monad: labEdgesM :: (GraphM m gr) => m (gr a b) -> m [LEdge b]
+ Data.Graph.Inductive.Monad: labEdgesM :: GraphM m gr => m (gr a b) -> m [LEdge b]
- Data.Graph.Inductive.Monad: labM :: (GraphM m gr) => m (gr a b) -> Node -> m (Maybe a)
+ Data.Graph.Inductive.Monad: labM :: GraphM m gr => m (gr a b) -> Node -> m (Maybe a)
- Data.Graph.Inductive.Monad: labNodesM :: (GraphM m gr) => m (gr a b) -> m [LNode a]
+ Data.Graph.Inductive.Monad: labNodesM :: GraphM m gr => m (gr a b) -> m [LNode a]
- Data.Graph.Inductive.Monad: matchAnyM :: (GraphM m gr) => m (gr a b) -> m (GDecomp gr a b)
+ Data.Graph.Inductive.Monad: matchAnyM :: GraphM m gr => m (gr a b) -> m (GDecomp gr a b)
- Data.Graph.Inductive.Monad: matchM :: (GraphM m gr) => Node -> m (gr a b) -> m (Decomp gr a b)
+ Data.Graph.Inductive.Monad: matchM :: GraphM m gr => Node -> m (gr a b) -> m (Decomp gr a b)
- Data.Graph.Inductive.Monad: mkGraphM :: (GraphM m gr) => [LNode a] -> [LEdge b] -> m (gr a b)
+ Data.Graph.Inductive.Monad: mkGraphM :: GraphM m gr => [LNode a] -> [LEdge b] -> m (gr a b)
- Data.Graph.Inductive.Monad: mkUGraphM :: (GraphM m gr) => [Node] -> [Edge] -> m (gr () ())
+ Data.Graph.Inductive.Monad: mkUGraphM :: GraphM m gr => [Node] -> [Edge] -> m (gr () ())
- Data.Graph.Inductive.Monad: newNodesM :: (GraphM m gr) => Int -> m (gr a b) -> m [Node]
+ Data.Graph.Inductive.Monad: newNodesM :: GraphM m gr => Int -> m (gr a b) -> m [Node]
- Data.Graph.Inductive.Monad: noNodesM :: (GraphM m gr) => m (gr a b) -> m Int
+ Data.Graph.Inductive.Monad: noNodesM :: GraphM m gr => m (gr a b) -> m Int
- Data.Graph.Inductive.Monad: nodeRangeM :: (GraphM m gr) => m (gr a b) -> m (Node, Node)
+ Data.Graph.Inductive.Monad: nodeRangeM :: GraphM m gr => m (gr a b) -> m (Node, Node)
- Data.Graph.Inductive.Monad: nodesM :: (GraphM m gr) => m (gr a b) -> m [Node]
+ Data.Graph.Inductive.Monad: nodesM :: GraphM m gr => m (gr a b) -> m [Node]
- Data.Graph.Inductive.Monad: ufoldM :: (GraphM m gr) => ((Context a b) -> c -> c) -> c -> m (gr a b) -> m c
+ Data.Graph.Inductive.Monad: ufoldM :: GraphM m gr => ((Context a b) -> c -> c) -> c -> m (gr a b) -> m c
- Data.Graph.Inductive.NodeMap: data (Ord a) => NodeMap a
+ Data.Graph.Inductive.NodeMap: data Ord a => NodeMap a
- Data.Graph.Inductive.NodeMap: mkEdge :: (Ord a) => NodeMap a -> (a, a, b) -> Maybe (LEdge b)
+ Data.Graph.Inductive.NodeMap: mkEdge :: Ord a => NodeMap a -> (a, a, b) -> Maybe (LEdge b)
- Data.Graph.Inductive.NodeMap: mkEdges :: (Ord a) => NodeMap a -> [(a, a, b)] -> Maybe [LEdge b]
+ Data.Graph.Inductive.NodeMap: mkEdges :: Ord a => NodeMap a -> [(a, a, b)] -> Maybe [LEdge b]
- Data.Graph.Inductive.NodeMap: mkNode :: (Ord a) => NodeMap a -> a -> (LNode a, NodeMap a)
+ Data.Graph.Inductive.NodeMap: mkNode :: Ord a => NodeMap a -> a -> (LNode a, NodeMap a)
- Data.Graph.Inductive.NodeMap: mkNode_ :: (Ord a) => NodeMap a -> a -> LNode a
+ Data.Graph.Inductive.NodeMap: mkNode_ :: Ord a => NodeMap a -> a -> LNode a
- Data.Graph.Inductive.NodeMap: mkNodes :: (Ord a) => NodeMap a -> [a] -> ([LNode a], NodeMap a)
+ Data.Graph.Inductive.NodeMap: mkNodes :: Ord a => NodeMap a -> [a] -> ([LNode a], NodeMap a)
- Data.Graph.Inductive.NodeMap: mkNodes_ :: (Ord a) => NodeMap a -> [a] -> [LNode a]
+ Data.Graph.Inductive.NodeMap: mkNodes_ :: Ord a => NodeMap a -> [a] -> [LNode a]
- Data.Graph.Inductive.NodeMap: new :: (Ord a) => NodeMap a
+ Data.Graph.Inductive.NodeMap: new :: Ord a => NodeMap a
- Data.Graph.Inductive.Query.ArtPoint: ap :: (Graph gr) => gr a b -> [Node]
+ Data.Graph.Inductive.Query.ArtPoint: ap :: Graph gr => gr a b -> [Node]
- Data.Graph.Inductive.Query.BCC: bcc :: (DynGraph gr) => gr a b -> [gr a b]
+ Data.Graph.Inductive.Query.BCC: bcc :: DynGraph gr => gr a b -> [gr a b]
- Data.Graph.Inductive.Query.BFS: bfe :: (Graph gr) => Node -> gr a b -> [Edge]
+ Data.Graph.Inductive.Query.BFS: bfe :: Graph gr => Node -> gr a b -> [Edge]
- Data.Graph.Inductive.Query.BFS: bfen :: (Graph gr) => [Edge] -> gr a b -> [Edge]
+ Data.Graph.Inductive.Query.BFS: bfen :: Graph gr => [Edge] -> gr a b -> [Edge]
- Data.Graph.Inductive.Query.BFS: bfs :: (Graph gr) => Node -> gr a b -> [Node]
+ Data.Graph.Inductive.Query.BFS: bfs :: Graph gr => Node -> gr a b -> [Node]
- Data.Graph.Inductive.Query.BFS: bfsWith :: (Graph gr) => (Context a b -> c) -> Node -> gr a b -> [c]
+ Data.Graph.Inductive.Query.BFS: bfsWith :: Graph gr => (Context a b -> c) -> Node -> gr a b -> [c]
- Data.Graph.Inductive.Query.BFS: bfsn :: (Graph gr) => [Node] -> gr a b -> [Node]
+ Data.Graph.Inductive.Query.BFS: bfsn :: Graph gr => [Node] -> gr a b -> [Node]
- Data.Graph.Inductive.Query.BFS: bfsnWith :: (Graph gr) => (Context a b -> c) -> [Node] -> gr a b -> [c]
+ Data.Graph.Inductive.Query.BFS: bfsnWith :: Graph gr => (Context a b -> c) -> [Node] -> gr a b -> [c]
- Data.Graph.Inductive.Query.BFS: bft :: (Graph gr) => Node -> gr a b -> RTree
+ Data.Graph.Inductive.Query.BFS: bft :: Graph gr => Node -> gr a b -> RTree
- Data.Graph.Inductive.Query.BFS: esp :: (Graph gr) => Node -> Node -> gr a b -> Path
+ Data.Graph.Inductive.Query.BFS: esp :: Graph gr => Node -> Node -> gr a b -> Path
- Data.Graph.Inductive.Query.BFS: lbft :: (Graph gr) => Node -> gr a b -> LRTree b
+ Data.Graph.Inductive.Query.BFS: lbft :: Graph gr => Node -> gr a b -> LRTree b
- Data.Graph.Inductive.Query.BFS: lesp :: (Graph gr) => Node -> Node -> gr a b -> LPath b
+ Data.Graph.Inductive.Query.BFS: lesp :: Graph gr => Node -> Node -> gr a b -> LPath b
- Data.Graph.Inductive.Query.BFS: level :: (Graph gr) => Node -> gr a b -> [(Node, Int)]
+ Data.Graph.Inductive.Query.BFS: level :: Graph gr => Node -> gr a b -> [(Node, Int)]
- Data.Graph.Inductive.Query.BFS: leveln :: (Graph gr) => [(Node, Int)] -> gr a b -> [(Node, Int)]
+ Data.Graph.Inductive.Query.BFS: leveln :: Graph gr => [(Node, Int)] -> gr a b -> [(Node, Int)]
- Data.Graph.Inductive.Query.DFS: components :: (Graph gr) => gr a b -> [[Node]]
+ Data.Graph.Inductive.Query.DFS: components :: Graph gr => gr a b -> [[Node]]
- Data.Graph.Inductive.Query.DFS: dff :: (Graph gr) => [Node] -> gr a b -> [Tree Node]
+ Data.Graph.Inductive.Query.DFS: dff :: Graph gr => [Node] -> gr a b -> [Tree Node]
- Data.Graph.Inductive.Query.DFS: dff' :: (Graph gr) => gr a b -> [Tree Node]
+ Data.Graph.Inductive.Query.DFS: dff' :: Graph gr => gr a b -> [Tree Node]
- Data.Graph.Inductive.Query.DFS: dffWith :: (Graph gr) => CFun a b c -> [Node] -> gr a b -> [Tree c]
+ Data.Graph.Inductive.Query.DFS: dffWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [Tree c]
- Data.Graph.Inductive.Query.DFS: dffWith' :: (Graph gr) => CFun a b c -> gr a b -> [Tree c]
+ Data.Graph.Inductive.Query.DFS: dffWith' :: Graph gr => CFun a b c -> gr a b -> [Tree c]
- Data.Graph.Inductive.Query.DFS: dfs :: (Graph gr) => [Node] -> gr a b -> [Node]
+ Data.Graph.Inductive.Query.DFS: dfs :: Graph gr => [Node] -> gr a b -> [Node]
- Data.Graph.Inductive.Query.DFS: dfs' :: (Graph gr) => gr a b -> [Node]
+ Data.Graph.Inductive.Query.DFS: dfs' :: Graph gr => gr a b -> [Node]
- Data.Graph.Inductive.Query.DFS: dfsWith :: (Graph gr) => CFun a b c -> [Node] -> gr a b -> [c]
+ Data.Graph.Inductive.Query.DFS: dfsWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [c]
- Data.Graph.Inductive.Query.DFS: dfsWith' :: (Graph gr) => CFun a b c -> gr a b -> [c]
+ Data.Graph.Inductive.Query.DFS: dfsWith' :: Graph gr => CFun a b c -> gr a b -> [c]
- Data.Graph.Inductive.Query.DFS: isConnected :: (Graph gr) => gr a b -> Bool
+ Data.Graph.Inductive.Query.DFS: isConnected :: Graph gr => gr a b -> Bool
- Data.Graph.Inductive.Query.DFS: noComponents :: (Graph gr) => gr a b -> Int
+ Data.Graph.Inductive.Query.DFS: noComponents :: Graph gr => gr a b -> Int
- Data.Graph.Inductive.Query.DFS: rdff :: (Graph gr) => [Node] -> gr a b -> [Tree Node]
+ Data.Graph.Inductive.Query.DFS: rdff :: Graph gr => [Node] -> gr a b -> [Tree Node]
- Data.Graph.Inductive.Query.DFS: rdff' :: (Graph gr) => gr a b -> [Tree Node]
+ Data.Graph.Inductive.Query.DFS: rdff' :: Graph gr => gr a b -> [Tree Node]
- Data.Graph.Inductive.Query.DFS: rdfs :: (Graph gr) => [Node] -> gr a b -> [Node]
+ Data.Graph.Inductive.Query.DFS: rdfs :: Graph gr => [Node] -> gr a b -> [Node]
- Data.Graph.Inductive.Query.DFS: rdfs' :: (Graph gr) => gr a b -> [Node]
+ Data.Graph.Inductive.Query.DFS: rdfs' :: Graph gr => gr a b -> [Node]
- Data.Graph.Inductive.Query.DFS: reachable :: (Graph gr) => Node -> gr a b -> [Node]
+ Data.Graph.Inductive.Query.DFS: reachable :: Graph gr => Node -> gr a b -> [Node]
- Data.Graph.Inductive.Query.DFS: scc :: (Graph gr) => gr a b -> [[Node]]
+ Data.Graph.Inductive.Query.DFS: scc :: Graph gr => gr a b -> [[Node]]
- Data.Graph.Inductive.Query.DFS: topsort :: (Graph gr) => gr a b -> [Node]
+ Data.Graph.Inductive.Query.DFS: topsort :: Graph gr => gr a b -> [Node]
- Data.Graph.Inductive.Query.DFS: topsort' :: (Graph gr) => gr a b -> [a]
+ Data.Graph.Inductive.Query.DFS: topsort' :: Graph gr => gr a b -> [a]
- Data.Graph.Inductive.Query.DFS: udff :: (Graph gr) => [Node] -> gr a b -> [Tree Node]
+ Data.Graph.Inductive.Query.DFS: udff :: Graph gr => [Node] -> gr a b -> [Tree Node]
- Data.Graph.Inductive.Query.DFS: udff' :: (Graph gr) => gr a b -> [Tree Node]
+ Data.Graph.Inductive.Query.DFS: udff' :: Graph gr => gr a b -> [Tree Node]
- Data.Graph.Inductive.Query.DFS: udfs :: (Graph gr) => [Node] -> gr a b -> [Node]
+ Data.Graph.Inductive.Query.DFS: udfs :: Graph gr => [Node] -> gr a b -> [Node]
- Data.Graph.Inductive.Query.DFS: udfs' :: (Graph gr) => gr a b -> [Node]
+ Data.Graph.Inductive.Query.DFS: udfs' :: Graph gr => gr a b -> [Node]
- Data.Graph.Inductive.Query.DFS: xdfWith :: (Graph gr) => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> ([Tree c], gr a b)
+ Data.Graph.Inductive.Query.DFS: xdfWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> ([Tree c], gr a b)
- Data.Graph.Inductive.Query.DFS: xdffWith :: (Graph gr) => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [Tree c]
+ Data.Graph.Inductive.Query.DFS: xdffWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [Tree c]
- Data.Graph.Inductive.Query.DFS: xdfsWith :: (Graph gr) => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [c]
+ Data.Graph.Inductive.Query.DFS: xdfsWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [c]
- Data.Graph.Inductive.Query.Dominators: dom :: (Graph gr) => gr a b -> Node -> [(Node, [Node])]
+ Data.Graph.Inductive.Query.Dominators: dom :: Graph gr => gr a b -> Node -> [(Node, [Node])]
- Data.Graph.Inductive.Query.Dominators: iDom :: (Graph gr) => gr a b -> Node -> [(Node, Node)]
+ Data.Graph.Inductive.Query.Dominators: iDom :: Graph gr => gr a b -> Node -> [(Node, Node)]
- Data.Graph.Inductive.Query.GVD: nearestDist :: (Real b) => Node -> Voronoi b -> Maybe b
+ Data.Graph.Inductive.Query.GVD: nearestDist :: Real b => Node -> Voronoi b -> Maybe b
- Data.Graph.Inductive.Query.GVD: nearestNode :: (Real b) => Node -> Voronoi b -> Maybe Node
+ Data.Graph.Inductive.Query.GVD: nearestNode :: Real b => Node -> Voronoi b -> Maybe Node
- Data.Graph.Inductive.Query.GVD: nearestPath :: (Real b) => Node -> Voronoi b -> Maybe Path
+ Data.Graph.Inductive.Query.GVD: nearestPath :: Real b => Node -> Voronoi b -> Maybe Path
- Data.Graph.Inductive.Query.GVD: voronoiSet :: (Real b) => Node -> Voronoi b -> [Node]
+ Data.Graph.Inductive.Query.GVD: voronoiSet :: Real b => Node -> Voronoi b -> [Node]
- Data.Graph.Inductive.Query.Indep: indep :: (DynGraph gr) => gr a b -> [Node]
+ Data.Graph.Inductive.Query.Indep: indep :: DynGraph gr => gr a b -> [Node]
- Data.Graph.Inductive.Query.MST: msPath :: (Real b) => LRTree b -> Node -> Node -> Path
+ Data.Graph.Inductive.Query.MST: msPath :: Real b => LRTree b -> Node -> Node -> Path
- Data.Graph.Inductive.Query.Monad: apply' :: (Monad m) => GT m g a -> g -> m (a, g)
+ Data.Graph.Inductive.Query.Monad: apply' :: Monad m => GT m g a -> g -> m (a, g)
- Data.Graph.Inductive.Query.Monad: applyWith :: (Monad m) => (a -> b) -> GT m g a -> m g -> m (b, g)
+ Data.Graph.Inductive.Query.Monad: applyWith :: Monad m => (a -> b) -> GT m g a -> m g -> m (b, g)
- Data.Graph.Inductive.Query.Monad: applyWith' :: (Monad m) => (a -> b) -> GT m g a -> g -> m (b, g)
+ Data.Graph.Inductive.Query.Monad: applyWith' :: Monad m => (a -> b) -> GT m g a -> g -> m (b, g)
- Data.Graph.Inductive.Query.Monad: condMGT :: (Monad m) => (m s -> m Bool) -> GT m s a -> GT m s a -> GT m s a
+ Data.Graph.Inductive.Query.Monad: condMGT :: Monad m => (m s -> m Bool) -> GT m s a -> GT m s a -> GT m s a
- Data.Graph.Inductive.Query.Monad: condMGT' :: (Monad m) => (s -> Bool) -> GT m s a -> GT m s a -> GT m s a
+ Data.Graph.Inductive.Query.Monad: condMGT' :: Monad m => (s -> Bool) -> GT m s a -> GT m s a -> GT m s a
- Data.Graph.Inductive.Query.Monad: dffM :: (GraphM m gr) => [Node] -> GT m (gr a b) [Tree Node]
+ Data.Graph.Inductive.Query.Monad: dffM :: GraphM m gr => [Node] -> GT m (gr a b) [Tree Node]
- Data.Graph.Inductive.Query.Monad: dfsGT :: (GraphM m gr) => [Node] -> GT m (gr a b) [Node]
+ Data.Graph.Inductive.Query.Monad: dfsGT :: GraphM m gr => [Node] -> GT m (gr a b) [Node]
- Data.Graph.Inductive.Query.Monad: dfsM :: (GraphM m gr) => [Node] -> m (gr a b) -> m [Node]
+ Data.Graph.Inductive.Query.Monad: dfsM :: GraphM m gr => [Node] -> m (gr a b) -> m [Node]
- Data.Graph.Inductive.Query.Monad: dfsM' :: (GraphM m gr) => m (gr a b) -> m [Node]
+ Data.Graph.Inductive.Query.Monad: dfsM' :: GraphM m gr => m (gr a b) -> m [Node]
- Data.Graph.Inductive.Query.Monad: getContext :: (GraphM m gr) => GT m (gr a b) (Context a b)
+ Data.Graph.Inductive.Query.Monad: getContext :: GraphM m gr => GT m (gr a b) (Context a b)
- Data.Graph.Inductive.Query.Monad: getNode :: (GraphM m gr) => GT m (gr a b) Node
+ Data.Graph.Inductive.Query.Monad: getNode :: GraphM m gr => GT m (gr a b) Node
- Data.Graph.Inductive.Query.Monad: getNodes :: (GraphM m gr) => GT m (gr a b) [Node]
+ Data.Graph.Inductive.Query.Monad: getNodes :: GraphM m gr => GT m (gr a b) [Node]
- Data.Graph.Inductive.Query.Monad: graphDff :: (GraphM m gr) => [Node] -> m (gr a b) -> m [Tree Node]
+ Data.Graph.Inductive.Query.Monad: graphDff :: GraphM m gr => [Node] -> m (gr a b) -> m [Tree Node]
- Data.Graph.Inductive.Query.Monad: graphDff' :: (GraphM m gr) => m (gr a b) -> m [Tree Node]
+ Data.Graph.Inductive.Query.Monad: graphDff' :: GraphM m gr => m (gr a b) -> m [Tree Node]
- Data.Graph.Inductive.Query.Monad: graphFilter :: (GraphM m gr) => (Context a b -> Bool) -> m (gr a b) -> m [Context a b]
+ Data.Graph.Inductive.Query.Monad: graphFilter :: GraphM m gr => (Context a b -> Bool) -> m (gr a b) -> m [Context a b]
- Data.Graph.Inductive.Query.Monad: graphFilterM :: (GraphM m gr) => (Context a b -> Bool) -> GT m (gr a b) [Context a b]
+ Data.Graph.Inductive.Query.Monad: graphFilterM :: GraphM m gr => (Context a b -> Bool) -> GT m (gr a b) [Context a b]
- Data.Graph.Inductive.Query.Monad: graphNodes :: (GraphM m gr) => m (gr a b) -> m [Node]
+ Data.Graph.Inductive.Query.Monad: graphNodes :: GraphM m gr => m (gr a b) -> m [Node]
- Data.Graph.Inductive.Query.Monad: graphNodesM :: (GraphM m gr) => GT m (gr a b) [Node]
+ Data.Graph.Inductive.Query.Monad: graphNodesM :: GraphM m gr => GT m (gr a b) [Node]
- Data.Graph.Inductive.Query.Monad: graphNodesM0 :: (GraphM m gr) => GT m (gr a b) [Node]
+ Data.Graph.Inductive.Query.Monad: graphNodesM0 :: GraphM m gr => GT m (gr a b) [Node]
- Data.Graph.Inductive.Query.Monad: graphRec :: (GraphM m gr) => GT m (gr a b) c -> (c -> d -> d) -> d -> GT m (gr a b) d
+ Data.Graph.Inductive.Query.Monad: graphRec :: GraphM m gr => GT m (gr a b) c -> (c -> d -> d) -> d -> GT m (gr a b) d
- Data.Graph.Inductive.Query.Monad: graphUFold :: (GraphM m gr) => (Context a b -> c -> c) -> c -> GT m (gr a b) c
+ Data.Graph.Inductive.Query.Monad: graphUFold :: GraphM m gr => (Context a b -> c -> c) -> c -> GT m (gr a b) c
- Data.Graph.Inductive.Query.Monad: recMGT :: (Monad m) => (m s -> m Bool) -> GT m s a -> (a -> b -> b) -> b -> GT m s b
+ Data.Graph.Inductive.Query.Monad: recMGT :: Monad m => (m s -> m Bool) -> GT m s a -> (a -> b -> b) -> b -> GT m s b
- Data.Graph.Inductive.Query.Monad: recMGT' :: (Monad m) => (s -> Bool) -> GT m s a -> (a -> b -> b) -> b -> GT m s b
+ Data.Graph.Inductive.Query.Monad: recMGT' :: Monad m => (s -> Bool) -> GT m s a -> (a -> b -> b) -> b -> GT m s b
- Data.Graph.Inductive.Query.Monad: runGT :: (Monad m) => GT m g a -> m g -> m a
+ Data.Graph.Inductive.Query.Monad: runGT :: Monad m => GT m g a -> m g -> m a
- Data.Graph.Inductive.Query.Monad: sucGT :: (GraphM m gr) => Node -> GT m (gr a b) (Maybe [Node])
+ Data.Graph.Inductive.Query.Monad: sucGT :: GraphM m gr => Node -> GT m (gr a b) (Maybe [Node])
- Data.Graph.Inductive.Query.Monad: sucM :: (GraphM m gr) => Node -> m (gr a b) -> m (Maybe [Node])
+ Data.Graph.Inductive.Query.Monad: sucM :: GraphM m gr => Node -> m (gr a b) -> m (Maybe [Node])
- Data.Graph.Inductive.Query.TransClos: trc :: (DynGraph gr) => gr a b -> gr a ()
+ Data.Graph.Inductive.Query.TransClos: trc :: DynGraph gr => gr a b -> gr a ()
Files
- Data/Graph/Inductive/Graphviz.hs +6/−5
- Data/Graph/Inductive/PatriciaTree.hs +191/−0
- Data/Graph/Inductive/Query/BCC.hs +12/−11
- doc/CHANGES +38/−2
- fgl.cabal +4/−4
- setup/Main.hi binary
- setup/Main.o binary
- setup/setup too large to diff
- test/bcc.hs +16/−0
- test/benchmark.hs +138/−0
Data/Graph/Inductive/Graphviz.hs view
@@ -57,11 +57,12 @@ graphviz' g = graphviz g "fgl" (8.5,11.0) (1,1) Landscape sq :: String -> String-sq ('"':s) | last s == '"' = init s- | otherwise = s-sq ('\'':s) | last s == '\'' = init s- | otherwise = s-sq s = s+sq s@[c] = s+sq ('"':s) | last s == '"' = init s+ | otherwise = s+sq ('\'':s) | last s == '\'' = init s+ | otherwise = s+sq s = s sl :: (Show a) => a -> String sl a =
+ Data/Graph/Inductive/PatriciaTree.hs view
@@ -0,0 +1,191 @@+-- |An efficient implementation of 'Data.Graph.Inductive.Graph.Graph'+-- using big-endian patricia tree (i.e. "Data.IntMap").+--+-- This module provides the following specialised functions to gain+-- more performance, using GHC's RULES pragma:+--+-- * 'Data.Graph.Inductive.Graph.insNode'+--+-- * 'Data.Graph.Inductive.Graph.insEdge'+--+-- * 'Data.Graph.Inductive.Graph.gmap'+--+-- * 'Data.Graph.Inductive.Graph.nmap'+--+-- * 'Data.Graph.Inductive.Graph.emap'++module Data.Graph.Inductive.PatriciaTree+ ( Gr+ , UGr+ )+ where++import Data.Graph.Inductive.Graph+import Data.IntMap (IntMap)+import qualified Data.IntMap as IM+import Data.List+import Data.Maybe+++data 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 UGr = Gr () ()+++instance Graph Gr where+ -- required members+ empty = Gr IM.empty+ isEmpty (Gr g) = IM.null g+ match = matchGr+ mkGraph vs es = (insEdges' . insNodes vs) empty+ where+ insEdges' g = foldl' (flip insEdge) g es++ labNodes (Gr g) = [ (node, label)+ | (node, (_, label, _)) <- IM.toList g ]++ -- overriding members for efficiency+ noNodes (Gr g) = IM.size g+ nodeRange (Gr g)+ | IM.null g = (0, 0)+ | otherwise = (ix (IM.minViewWithKey g), ix (IM.maxViewWithKey g))+ where+ ix = fst . fst . fromJust++ labEdges (Gr g) = do (node, (_, _, s)) <- IM.toList g+ (next, label) <- IM.toList s+ return (node, next, label)+++instance DynGraph Gr where+ (p, v, l, s) & (Gr g)+ = let !g1 = IM.insert v (fromAdj p, l, fromAdj s) g+ !g2 = addSucc g1 v p+ !g3 = addPred g2 v s+ in+ Gr g3+++matchGr :: Node -> Gr a b -> Decomp Gr a b+matchGr node (Gr g)+ = case IM.lookup node g of+ Nothing+ -> (Nothing, Gr g)++ Just (p, label, s)+ -> let !g1 = IM.delete node g+ !p' = IM.delete node p+ !s' = IM.delete node s+ !g2 = clearPred g1 node (IM.keys s')+ !g3 = clearSucc g2 node (IM.keys p')+ in+ (Just (toAdj p', node, label, toAdj s), Gr g3)+++{-# RULES+ "insNode/Data.Graph.Inductive.PatriciaTree" insNode = fastInsNode+ #-}+fastInsNode :: LNode a -> Gr a b -> Gr a b+fastInsNode (v, l) (Gr g) = g' `seq` Gr g'+ where+ g' = IM.insert v (IM.empty, l, IM.empty) g+++{-# RULES+ "insEdge/Data.Graph.Inductive.PatriciaTree" insEdge = fastInsEdge+ #-}+fastInsEdge :: LEdge b -> Gr a b -> Gr a b+fastInsEdge (v, w, l) (Gr g) = g2 `seq` Gr g2+ where+ 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)+++{-# RULES+ "gmap/Data.Graph.Inductive.PatriciaTree" gmap = fastGMap+ #-}+fastGMap :: forall a b c d. (Context a b -> Context c d) -> Gr a b -> Gr c d+fastGMap f (Gr g) = Gr (IM.mapWithKey f' g)+ where+ f' :: Node -> Context' a b -> Context' c d+ f' = ((fromContext . f) .) . toContext+++{-# RULES+ "nmap/Data.Graph.Inductive.PatriciaTree" nmap = fastNMap+ #-}+fastNMap :: forall a b c. (a -> c) -> Gr a b -> Gr c b+fastNMap f (Gr g) = Gr (IM.map f' g)+ where+ f' :: Context' a b -> Context' c b+ f' (ps, a, ss) = (ps, f a, ss)+++{-# RULES+ "emap/Data.Graph.Inductive.PatriciaTree" emap = fastEMap+ #-}+fastEMap :: forall a b c. (b -> c) -> Gr a b -> Gr a c+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)+++toAdj :: IntMap b -> Adj b+toAdj = map swap . IM.toList+++fromAdj :: Adj b -> IntMap b+fromAdj = IM.fromList . map swap+++toContext :: Node -> Context' a b -> Context a b+toContext v (ps, a, ss)+ = (toAdj ps, v, a, toAdj ss)+++fromContext :: Context a b -> Context' a b+fromContext (ps, _, a, ss)+ = (fromAdj ps, a, fromAdj ss)+++swap :: (a, b) -> (b, a)+swap (a, b) = (b, a)+++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)+++addPred :: GraphRep a b -> Node -> [(b, Node)] -> GraphRep a b+addPred g _ [] = g+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)+++clearSucc :: GraphRep a b -> Node -> [Node] -> GraphRep a b+clearSucc g _ [] = g+clearSucc g v (p:rest) = clearSucc g' v rest+ where+ g' = IM.adjust f p g+ f (ps, l, ss) = (ps, l, IM.delete v ss)+++clearPred :: GraphRep a b -> Node -> [Node] -> GraphRep a b+clearPred g _ [] = g+clearPred g v (s:rest) = clearPred g' v rest+ where+ g' = IM.adjust f s g+ f (ps, l, ss) = (IM.delete v ps, l, ss)
Data/Graph/Inductive/Query/BCC.hs view
@@ -25,14 +25,15 @@ lc'= map (\g->[ e | e <- s, gelem (snd e) g]) gs --------------------------------------------------------------------------------- Given a node v and a list of graphs, this functions returns the graph which--- v belongs to.+-- Given a node v and a list of graphs, this function returns the graph which+-- v belongs to, together with a list of the remaining graphs. -------------------------------------------------------------------------------findGraph :: DynGraph gr => Node -> [gr a b] -> Decomp gr a b+findGraph :: DynGraph gr => Node -> [gr a b] -> (Decomp gr a b, [gr a b]) findGraph _ [] = error "findGraph: empty graph list" findGraph v (g:gs) = case match v g of- (Nothing, _) -> findGraph v gs- (Just c, g') -> (Just c, g')+ (Nothing, g) -> let (d, gs') = findGraph v gs+ in (d, g : gs')+ (Just c, g') -> ((Just c, g'), gs) ------------------------------------------------------------------------------ -- Given a graph g and its articulation points, this function disconnects g@@ -40,12 +41,12 @@ -- resulting disconnected graph. ------------------------------------------------------------------------------ splitGraphs :: DynGraph gr => [gr a b] -> [Node] -> [gr a b]-splitGraphs gs [] = gs-splitGraphs [] _ = error "splitGraphs: empty graph list"-splitGraphs (g:gs) (v:vs) = splitGraphs (gs''++gs) vs - where gs'' = embedContexts c gs'- gs' = gComponents g'- (Just c,g') = findGraph v (g:gs)+splitGraphs gs [] = gs+splitGraphs [] _ = error "splitGraphs: empty graph list"+splitGraphs gs (v:vs) = splitGraphs (gs''++gs''') vs + where gs'' = embedContexts c gs'+ gs' = gComponents g'+ ((Just c,g'), gs''') = findGraph v gs {-| Finds the bi-connected components of an undirected connected graph.
doc/CHANGES view
@@ -1,5 +1,41 @@-CHANGES (FGL/HASKELL, Version: June 2006)---------------------------------------------+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 ---------
fgl.cabal view
@@ -1,5 +1,5 @@ name: fgl-version: 5.4.2.0+version: 5.4.2.2 license: BSD3 license-file: LICENSE author: Martin Erwig@@ -7,7 +7,6 @@ homepage: http://web.engr.oregonstate.edu/~erwig/fgl/haskell category: Data Structures synopsis: Martin Erwig's Functional Graph Library-description: Martin Erwig's Functional Graph Library. exposed-modules: Data.Graph.Inductive.Internal.FiniteMap, Data.Graph.Inductive.Internal.Heap,@@ -20,6 +19,7 @@ Data.Graph.Inductive.Graphviz, Data.Graph.Inductive.Monad, Data.Graph.Inductive.NodeMap,+ Data.Graph.Inductive.PatriciaTree, Data.Graph.Inductive.Query, Data.Graph.Inductive.Tree, Data.Graph.Inductive.Monad.IOArray,@@ -37,6 +37,6 @@ Data.Graph.Inductive.Query.SP, Data.Graph.Inductive.Query.TransClos, Data.Graph.Inductive-build-type: Simple build-depends: base, mtl, containers, array-extensions: MultiParamTypeClasses, OverlappingInstances, FlexibleInstances+extensions: MultiParamTypeClasses, OverlappingInstances, FlexibleInstances, ScopedTypeVariables+build-type: Simple
− setup/Main.hi
binary file changed (558 → absent bytes)
− setup/Main.o
binary file changed (1932 → absent bytes)
− setup/setup
file too large to diff
+ test/bcc.hs view
@@ -0,0 +1,16 @@+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 view
@@ -0,0 +1,138 @@+{-+ 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'