containers-good-graph (empty) → 0.6.4.1

raw patch · 7 files changed

+236/−0 lines, 7 filesdep +arraydep +basedep +containerssetup-changed

Dependencies added: array, base, containers, containers-good-graph, deepseq

Files

ChangeLog.md +3/−0
LICENSE +30/−0
README.md +16/−0
Setup.hs +2/−0
containers-good-graph.cabal +58/−0
src/Data/Graph/Good.hs +125/−0
test/Spec.hs +2/−0

+ ChangeLog.md view

@@ -0,0 +1,3 @@+# Changelog for containers-good-graph++## Unreleased changes

+ LICENSE view

@@ -0,0 +1,30 @@+Copyright Sandy Maguire (c) 2021++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Sandy Maguire nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

+ README.md view

@@ -0,0 +1,16 @@+# containers-good-graph++## Dedication++> That's a real [Parker Square](https://www.youtube.com/watch?v=aOT_bG-vWyg) kind of move.+>+> --Matt Parker+++## Overview++It's just `Data.Graph` from `containers`, except that it isn't *complete ass.*+`Data.Graph.Good` is a drop-in replacement, except that it makes everything+typesafe and means you can stop faffing about with partial maps to and from the+damn integers.+

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

+ containers-good-graph.cabal view

@@ -0,0 +1,58 @@+cabal-version: 1.12++-- This file has been generated from package.yaml by hpack version 0.33.0.+--+-- see: https://github.com/sol/hpack+--+-- hash: ffb8d4a03fc42fb7f821e0ed6855108b414919fb05eda9716ee6e37a5c0f4599++name:           containers-good-graph+version:        0.6.4.1+synopsis:       Data.Graph, but it doesn't suck!+description:    Please see the README on GitHub at <https://github.com/isovector/containers-good-graph#readme>+category:       Data Structures+homepage:       https://github.com/isovector/containers-good-graph#readme+bug-reports:    https://github.com/isovector/containers-good-graph/issues+author:         Sandy Maguire+maintainer:     sandy@sandymaguire.me+copyright:      Sandy Maguire+license:        BSD3+license-file:   LICENSE+build-type:     Simple+extra-source-files:+    README.md+    ChangeLog.md++source-repository head+  type: git+  location: https://github.com/isovector/containers-good-graph++library+  exposed-modules:+      Data.Graph.Good+  other-modules:+      Paths_containers_good_graph+  hs-source-dirs:+      src+  build-depends:+      array+    , base >=4.7 && <5+    , containers+    , deepseq+  default-language: Haskell2010++test-suite containers-good-graph-test+  type: exitcode-stdio-1.0+  main-is: Spec.hs+  other-modules:+      Paths_containers_good_graph+  hs-source-dirs:+      test+  ghc-options: -threaded -rtsopts -with-rtsopts=-N+  build-depends:+      array+    , base >=4.7 && <5+    , containers+    , containers-good-graph+    , deepseq+  default-language: Haskell2010

+ src/Data/Graph/Good.hs view

@@ -0,0 +1,125 @@+{-# OPTIONS_GHC -Wall #-}++module Data.Graph.Good+  ( Graph+  , graphFromEdges+  , vertices+  , edges+  , outdegree+  , indegree+  , transposeG+  , dfs+  , dff+  , topSort+  , reverseTopSort+  , components+  , scc+  , bcc+  , reachable+  , path+  ) where++import           Control.Applicative (empty)+import           Control.Arrow ((***))+import           Control.Monad ((<=<))+import           Data.Array (Ix, Array)+import qualified Data.Array as A+import qualified Data.Graph as G+import           Data.Maybe (mapMaybe, fromMaybe)+++data Graph v = Graph+  { g_graph :: G.Graph+  , g_from_vert :: G.Vertex -> v+  , g_to_vert :: v -> Maybe G.Vertex+  }+++graphFromEdges :: Ord v => [(v, [v])] -> Graph v+graphFromEdges vs =+  let (g, v_func, l) = G.graphFromEdges $ fmap (\(v, es) -> (v, v, es)) vs+   in Graph g (\vert -> let (v, _, _) = v_func vert in v) l+++vertices :: Graph v -> [v]+vertices g = fromVertices g $ overGraph G.vertices g+++edges :: Graph v -> [(v, v)]+edges g = fmap (g_from_vert g *** g_from_vert g) $ overGraph G.edges g+++overGraph :: (G.Graph -> r) -> Graph v -> r+overGraph f = f . g_graph+++lookupArr :: Ix k => Array k v -> k -> Maybe v+lookupArr arr ix =+  let (lo, hi) = A.bounds arr+   in case (lo <= ix && ix <= hi) of+        True -> Just $ arr A.! ix+        False -> Nothing+++outdegree :: Graph v -> v -> Maybe Int+outdegree g = lookupArr arr <=< g_to_vert g+  where+    arr = overGraph G.outdegree g+++indegree :: Graph v -> v -> Maybe Int+indegree g = lookupArr arr <=< g_to_vert g+  where+    arr = overGraph G.indegree g+++transposeG :: Graph v -> Graph v+transposeG g = g { g_graph = overGraph G.transposeG g }+++fromVertices :: Functor f => Graph v -> f G.Vertex -> f v+fromVertices = fmap . g_from_vert+++dfs :: Graph v -> [v] -> G.Forest v+dfs g vs =+  let verts = mapMaybe (g_to_vert g) vs+   in fmap (fromVertices g) $ overGraph G.dfs g verts+++dff :: Graph v -> G.Forest v+dff g = fmap (fromVertices g) $ overGraph G.dff g+++topSort :: Graph v -> [v]+topSort g = fromVertices g $ overGraph G.topSort g+++reverseTopSort :: Graph v -> [v]+reverseTopSort = reverse . topSort+++components :: Graph v -> G.Forest v+components g = fmap (fromVertices g) $ overGraph G.components g+++scc :: Graph v -> G.Forest v+scc g = fmap (fromVertices g) $ overGraph G.scc g+++bcc :: Graph v -> G.Forest [v]+bcc g = fmap (fmap $ fromVertices g) $ overGraph G.bcc g+++reachable :: Graph v -> v -> [v]+reachable g v = case g_to_vert g v of+  Nothing -> empty+  Just vert -> fromVertices g $ overGraph G.reachable g vert+++path :: Graph v -> v -> v -> Bool+path g v1 v2 = fromMaybe False $ do+  vert1 <- g_to_vert g v1+  vert2 <- g_to_vert g v2+  pure $ overGraph G.path g vert1 vert2+

+ test/Spec.hs view

@@ -0,0 +1,2 @@+main :: IO ()+main = putStrLn "Test suite not yet implemented"