fgl-extras-decompositions 0.1.0.0 → 0.1.1.0
raw patch · 5 files changed
+65/−18 lines, 5 filesdep ~fglPVP ok
version bump matches the API change (PVP)
Dependency ranges changed: fgl
API changes (from Hackage documentation)
Files
- Data/Graph/Inductive/Query/Ear.hs +14/−5
- LICENSE +1/−1
- README.md +18/−0
- changelog.md +9/−0
- fgl-extras-decompositions.cabal +23/−12
Data/Graph/Inductive/Query/Ear.hs view
@@ -1,5 +1,3 @@-{-# LANGUAGE ScopedTypeVariables #-}-{-# LANGUAGE TupleSections #-} -- | Ear decomposition of a graph. @@ -20,29 +18,39 @@ -- | The 'ears' function takes a graph with no node or edge annotation and -- produces an ear decomposition. Each edge is annotated with a weight. Edges -- with the same weight are in the same ear.+-- Maon, Schieber, Vishkin (1986) ears :: forall gr . DynGraph gr => gr () () -> gr () Int ears g | isConnected g = gWs | otherwise = error "called ears on disconnected graph" where+ -- (1.1) create spanning tree t :: Tree Node [t] = dff' g tps = treeToPaths t te = treeToEdges t+ -- (1.2) graph without spanning tree edges g' = mkUGraph (nodes g) ((edges g \\ te) \\ (map swap te)) `asTypeOf` g- -- gE is the graph of all edges not in the spanning tree. The edge weight- -- is the distance between the tree root and the lowest common ancestor of- -- the two nodes making up each edge+ -- (2) gE is the graph of all edges not in the spanning tree. The edge+ -- weight is the distance between the tree root and the lowest common+ -- ancestor of the two nodes making up each edge gE :: gr () Int = mkGraph (labNodes g') (map (lca tps) $ labEdges g')+ -- (3.1) add back all tree edges (in both directions) gE' = mkGraph (labNodes gE) (labEdges gE ++ map (\(a,b) -> (a,b,0)) (te ++ map swap te))+ -- (3.2) for each edge in the tree, find the shortest-path weight+ -- TODO on second thought, is this right? teWs = map (shortestPaths gE') te+ -- build a new graph, adding edge weights, where all edges with the same+ -- weight belong to the same ear gWs = mkGraph (labNodes g') (labEdges gE ++ teWs ++ map swap12 teWs) shortestPaths :: Gr () Int -> Edge -> LEdge Int shortestPaths g (u,v) = (u,v,spLength u v g') where g' = delEdge (u,v) $ delEdge (v,u) g +-- | Lowest common ancestor calculation+ lca :: [[Node]] -> (LEdge ()) -> (LEdge Int) lca ps (u,v,()) | any null ps = error $ "null path: " ++ show ps@@ -61,6 +69,7 @@ treeToEdges (Node k xs) = map ((k,) . rootLabel) xs ++ concatMap treeToEdges xs -- paths+ treeToPaths :: Tree Node -> [[Node]] treeToPaths (Node k []) = [[k]] treeToPaths (Node k xs) = [[k]] ++ [ (k:ys) | ys <- concatMap treeToPaths xs ]
LICENSE view
@@ -1,4 +1,4 @@-Copyright Christian Hoener zu Siederdissen 2013+Copyright Christian Hoener zu Siederdissen 2013-2015 All rights reserved.
+ README.md view
@@ -0,0 +1,18 @@+graph decompositions+====================++[](https://travis-ci.org/choener/fgl-extras-decompositions)++A library of graph decomposition algorithms for Erwig's FGL. Currently, only+ear decompositions are included.++ear decomposition: <http://en.wikipedia.org/wiki/Ear_decomposition>++++#### Contact++Christian Hoener zu Siederdissen+choener@bioinf.uni-leipzig.de+Leipzig University, Leipzig, Germany+
+ changelog.md view
@@ -0,0 +1,9 @@+0.1.1.0+-------++- travis ci integration++0.1.0.0+-------++- initial creation
fgl-extras-decompositions.cabal view
@@ -1,17 +1,17 @@ Name: fgl-extras-decompositions-Version: 0.1.0.0+Version: 0.1.1.0 License: BSD3 License-file: LICENSE Author: Christian Hoener zu Siederdissen-Maintainer: choener@tbi.univie.ac.at-Copyright: Christian Hoener zu Siederdissen, 2013-Homepage: http://www.tbi.univie.ac.at/~choener/+Maintainer: choener@bioinf.uni-leipzig.de+Copyright: Christian Hoener zu Siederdissen, 2013 - 2015+Homepage: http://www.bioinf.uni-leipzig.de/~choener/ Stability: Experimental-Category: Data+Category: Data Structures, Graphs Build-type: Simple-Cabal-version: >=1.6-Synopsis:- Graph decomposition algorithms+Cabal-version: >= 1.10+tested-with: GHC == 7.8.4, GHC == 7.10.1+Synopsis: Graph decomposition algorithms Description: Graph decompositions of fgl graphs. This library is rather experimental.@@ -24,13 +24,24 @@ . Patches and ideas welcome. +++extra-source-files:+ changelog.md+ README.md+++ Library Exposed-modules: Data.Graph.Inductive.Query.Ear- Build-depends:- base >= 4 && <5 ,- containers ,- fgl >= 5.4+ Build-depends: base >= 4 && <5+ , containers+ , fgl >= 5.4 && < 5.6+ default-language:+ Haskell2010+ default-extensions: ScopedTypeVariables+ , TupleSections ghc-options: -O2