graphs 0.7 → 0.7.1
raw patch · 4 files changed
+180/−17 lines, 4 filesdep +semigroupsdep ~basedep ~containersnew-uploaderPVP: major bump suggested
API removals or changes: PVP suggests a major version bump
Dependencies added: semigroups
Dependency ranges changed: base, containers
API changes (from Hackage documentation)
+ Data.Graph.Algorithm: instance (Data.Graph.Class.Graph g, Data.Semigroup.Semigroup m) => Data.Semigroup.Semigroup (Data.Graph.Algorithm.GraphSearch g m)
+ Data.Graph.Class: type family Edge g :: *;
+ Data.Graph.Class: }
- Data.Graph.AdjacencyList: class Graph g => AdjacencyListGraph g where outDegree v = liftM length (outEdges v) adjacentVertices = outEdges >=> mapM target
+ Data.Graph.AdjacencyList: class Graph g => AdjacencyListGraph g
- Data.Graph.Class: class (Monad g, Eq (Vertex g), Eq (Edge g)) => Graph g where type family Vertex g :: * type family Edge g :: *
+ Data.Graph.Class: class (Monad g, Eq (Vertex g), Eq (Edge g)) => Graph g where {
- Data.Graph.Class.AdjacencyList: class Graph g => AdjacencyListGraph g where outDegree v = liftM length (outEdges v) adjacentVertices = outEdges >=> mapM target
+ Data.Graph.Class.AdjacencyList: class Graph g => AdjacencyListGraph g
- Data.Graph.Class.Bidirectional: class AdjacencyListGraph g => BidirectionalGraph g where inDegree v = length `liftM` inEdges v incidentEdges v = liftM2 (++) (inEdges v) (outEdges v) degree v = liftM2 (+) (inDegree v) (outDegree v)
+ Data.Graph.Class.Bidirectional: class AdjacencyListGraph g => BidirectionalGraph g
Files
- .travis.yml +139/−1
- CHANGELOG.markdown +4/−0
- graphs.cabal +23/−10
- src/Data/Graph/Algorithm.hs +14/−6
.travis.yml view
@@ -1,4 +1,15 @@-language: haskell+# This Travis job script has been generated by a script via+#+# runghc make_travis_yml_2.hs '-o' '.travis.yml' '--irc-channel=irc.freenode.org#haskell-lens' '--no-no-tests-no-bench' '--no-installed' 'cabal.project'+#+# For more information, see https://github.com/hvr/multi-ghc-travis+#+language: c+sudo: false++git:+ submodules: false # whether to recursively clone submodules+ notifications: irc: channels:@@ -6,3 +17,130 @@ skip_join: true template: - "\x0313graphs\x03/\x0306%{branch}\x03 \x0314%{commit}\x03 %{build_url} %{message}"++cache:+ directories:+ - $HOME/.cabal/packages+ - $HOME/.cabal/store++before_cache:+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/build-reports.log+ # remove files that are regenerated by 'cabal update'+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/00-index.*+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/*.json+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.cache+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.tar+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.tar.idx++ - rm -rfv $HOME/.cabal/packages/head.hackage++matrix:+ include:+ - compiler: "ghc-7.0.4"+ # env: TEST=--disable-tests BENCH=--disable-benchmarks+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.0,ghc-7.0.4], sources: [hvr-ghc]}}+ - compiler: "ghc-7.2.2"+ # env: TEST=--disable-tests BENCH=--disable-benchmarks+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.0,ghc-7.2.2], sources: [hvr-ghc]}}+ - compiler: "ghc-7.4.2"+ # env: TEST=--disable-tests BENCH=--disable-benchmarks+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.0,ghc-7.4.2], sources: [hvr-ghc]}}+ - compiler: "ghc-7.6.3"+ # env: TEST=--disable-tests BENCH=--disable-benchmarks+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.0,ghc-7.6.3], sources: [hvr-ghc]}}+ - compiler: "ghc-7.8.4"+ # env: TEST=--disable-tests BENCH=--disable-benchmarks+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.0,ghc-7.8.4], sources: [hvr-ghc]}}+ - compiler: "ghc-7.10.3"+ # env: TEST=--disable-tests BENCH=--disable-benchmarks+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.0,ghc-7.10.3], sources: [hvr-ghc]}}+ - compiler: "ghc-8.0.2"+ # env: TEST=--disable-tests BENCH=--disable-benchmarks+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.0,ghc-8.0.2], sources: [hvr-ghc]}}+ - compiler: "ghc-8.2.2"+ # env: TEST=--disable-tests BENCH=--disable-benchmarks+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.0,ghc-8.2.2], sources: [hvr-ghc]}}+ - compiler: "ghc-8.4.1"+ env: GHCHEAD=true+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-head,ghc-8.4.1], sources: [hvr-ghc]}}+ - compiler: "ghc-head"+ env: GHCHEAD=true+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-head,ghc-head], sources: [hvr-ghc]}}++ allow_failures:+ - compiler: "ghc-7.0.4"+ - compiler: "ghc-7.2.2"+ - compiler: "ghc-8.4.1"+ - compiler: "ghc-head"++before_install:+ - HC=${CC}+ - HCPKG=${HC/ghc/ghc-pkg}+ - unset CC+ - ROOTDIR=$(pwd)+ - mkdir -p $HOME/.local/bin+ - "PATH=/opt/ghc/bin:/opt/ghc-ppa-tools/bin:$HOME/local/bin:$PATH"+ - HCNUMVER=$(( $(${HC} --numeric-version|sed -E 's/([0-9]+)\.([0-9]+)\.([0-9]+).*/\1 * 10000 + \2 * 100 + \3/') ))+ - echo $HCNUMVER++install:+ - cabal --version+ - echo "$(${HC} --version) [$(${HC} --print-project-git-commit-id 2> /dev/null || echo '?')]"+ - BENCH=${BENCH---enable-benchmarks}+ - TEST=${TEST---enable-tests}+ - HADDOCK=${HADDOCK-true}+ - INSTALLED=${INSTALLED-true}+ - GHCHEAD=${GHCHEAD-false}+ - travis_retry cabal update -v+ - "sed -i.bak 's/^jobs:/-- jobs:/' ${HOME}/.cabal/config"+ - rm -fv cabal.project cabal.project.local+ # Overlay Hackage Package Index for GHC HEAD: https://github.com/hvr/head.hackage+ - |+ if $GHCHEAD; then+ sed -i.bak 's/-- allow-newer:.*/allow-newer: *:base, *:template-haskell, *:ghc, *:Cabal/' ${HOME}/.cabal/config++ echo 'repository head.hackage' >> ${HOME}/.cabal/config+ echo ' url: http://head.hackage.haskell.org/' >> ${HOME}/.cabal/config+ echo ' secure: True' >> ${HOME}/.cabal/config+ echo ' root-keys: 07c59cb65787dedfaef5bd5f987ceb5f7e5ebf88b904bbd4c5cbdeb2ff71b740' >> ${HOME}/.cabal/config+ echo ' 2e8555dde16ebd8df076f1a8ef13b8f14c66bad8eafefd7d9e37d0ed711821fb' >> ${HOME}/.cabal/config+ echo ' 8f79fd2389ab2967354407ec852cbe73f2e8635793ac446d09461ffb99527f6e' >> ${HOME}/.cabal/config+ echo ' key-threshold: 3' >> ${HOME}/.cabal.config++ cabal new-update head.hackage -v+ fi+ - grep -Ev -- '^\s*--' ${HOME}/.cabal/config | grep -Ev '^\s*$'+ - "printf 'packages: \".\"\\n' > cabal.project"+ - cat cabal.project+ - if [ -f "./configure.ac" ]; then+ (cd "." && autoreconf -i);+ fi+ - rm -f cabal.project.freeze+ - cabal new-build -w ${HC} ${TEST} ${BENCH} --project-file="cabal.project" --dep -j2 all+ - rm -rf "."/.ghc.environment.* "."/dist+ - DISTDIR=$(mktemp -d /tmp/dist-test.XXXX)++# Here starts the actual work to be performed for the package under test;+# any command which exits with a non-zero exit code causes the build to fail.+script:+ # test that source-distributions can be generated+ - (cd "." && cabal sdist)+ - mv "."/dist/graphs-*.tar.gz ${DISTDIR}/+ - cd ${DISTDIR} || false+ - find . -maxdepth 1 -name '*.tar.gz' -exec tar -xvf '{}' \;+ - "printf 'packages: graphs-*/*.cabal\\n' > cabal.project"+ - cat cabal.project+++ # build & run tests, build benchmarks+ - cabal new-build -w ${HC} ${TEST} ${BENCH} all++ # cabal check+ - (cd graphs-* && cabal check)++ # haddock+ - rm -rf ./dist-newstyle+ - if $HADDOCK; then cabal new-haddock -w ${HC} ${TEST} ${BENCH} all; else echo "Skipping haddock generation";fi++# REGENDATA ["-o",".travis.yml","--irc-channel=irc.freenode.org#haskell-lens","--no-no-tests-no-bench","--no-installed","cabal.project"]+# EOF
CHANGELOG.markdown view
@@ -1,3 +1,7 @@+0.7.1 [2018.02.24]+------------------+* Add a `Semigroup` instance for `GraphSearch`.+ 0.7 --- * Build warning-free on GHC 7.10 and GHC 8.0-rc1
graphs.cabal view
@@ -1,6 +1,6 @@ name: graphs category: Algorithms, Data Structures, Graphs-version: 0.7+version: 0.7.1 license: BSD3 cabal-version: >= 1.6 license-file: LICENSE@@ -23,7 +23,7 @@ > import Data.Graph.AdjacencyList > import Data.Graph.Algorithm > import Data.Graph.Algorithm.DepthFirstSearch- . + . create an adjacency list where the vertices are labeled with integers. . > graph :: Array Int [Int]@@ -42,13 +42,13 @@   , exitV :: [Int]   , black :: [(Int, Int)]   } deriving Show- . + . instance Monoid Orderings where  mempty = Orderings [] [] [] [] []  mappend (Orderings a1 a2 a3 a4 a5)(Orderings b1 b2 b3 b4 b5) =   Orderings (a1 ++ b1) (a2 ++ b2) (a3 ++ b3) (a4 ++ b4) (a5 ++ b5) @- . + . The `dfs` function's first argument is of type `GraphSearch` which is a visitor containing the functions to be run at various times during the search. The second argument is the starting vertex for the search.@@ -56,13 +56,13 @@ @ orderings :: GraphSearch (AdjacencyList Int) Orderings orderings = GraphSearch-   (\v -> return $ mempty {enterV = [v]}-   (\e -> return $ mempty {enterE = [e]}-   (\e -> return $ mempty {gray = [e]}-   (\v -> return $ mempty {exitV = [v]}-   (\e -> return $ mempty {black = [e]}+   (\\v -> return $ mempty {enterV = [v]})+   (\\e -> return $ mempty {enterE = [e]})+   (\\e -> return $ mempty {gray = [e]})+   (\\v -> return $ mempty {exitV = [v]})+   (\\e -> return $ mempty {black = [e]}) @- . + . Finally `runAdjacencylist` unwraps the function in the `Adjacencylist` newtype and runs it on `graph`. .@@ -76,6 +76,15 @@ @ build-type: Simple+tested-with: GHC == 7.0.4+ , GHC == 7.2.2+ , GHC == 7.4.2+ , GHC == 7.6.3+ , GHC == 7.8.4+ , GHC == 7.10.3+ , GHC == 8.0.2+ , GHC == 8.2.2+ , GHC == 8.4.1 extra-source-files: .travis.yml CHANGELOG.markdown README.markdown @@ -95,6 +104,10 @@ transformers-compat >= 0.3 && < 1, containers >= 0.3 && < 0.6, void >= 0.5.5.1 && < 1++ if !impl(ghc >= 8.0)+ build-depends:+ semigroups >= 0.16 && < 1 exposed-modules: Data.Graph.AdjacencyList
src/Data/Graph/Algorithm.hs view
@@ -19,18 +19,21 @@ import Control.Monad #if __GLASGOW_HASKELL__ < 710 import Control.Applicative-import Data.Monoid+import Data.Monoid (Monoid(..)) #endif+#if !(MIN_VERSION_base(4,11,0))+import Data.Semigroup (Semigroup(..))+#endif import Data.Graph.Class -- | Graph search visitor data GraphSearch g m = GraphSearch- { enterVertex :: Vertex g -> g m -- called the first time a vertex is discovered- , enterEdge :: Edge g -> g m -- called the first time an edge is discovered, before enterVertex- , grayTarget :: Edge g -> g m -- called when we encounter a back edge to a vertex we're still processing- , exitVertex :: Vertex g -> g m -- called once we have processed all descendants of a vertex- , blackTarget :: Edge g -> g m -- called when we encounter a cross edge to a vertex we've already finished+ { enterVertex :: Vertex g -> g m -- ^ Called the first time a vertex is discovered+ , enterEdge :: Edge g -> g m -- ^ Called the first time an edge is discovered, before enterVertex+ , grayTarget :: Edge g -> g m -- ^ Called when we encounter a back edge to a vertex we're still processing+ , exitVertex :: Vertex g -> g m -- ^ Called once we have processed all descendants of a vertex+ , blackTarget :: Edge g -> g m -- ^ Called when we encounter a cross edge to a vertex we've already finished } instance Graph g => Functor (GraphSearch g) where@@ -65,6 +68,11 @@ (\v -> exitVertex m v >>= ($ v) . exitVertex . f) (\e -> blackTarget m e >>= ($ e) . blackTarget . f) +instance (Graph g, Semigroup m) => Semigroup (GraphSearch g m) where+ (<>) = liftM2 (<>)+ instance (Graph g, Monoid m) => Monoid (GraphSearch g m) where mempty = return mempty+#if !(MIN_VERSION_base(4,11,0)) mappend = liftM2 mappend+#endif