algebraic-graphs 0.6 → 0.6.1
raw patch · 57 files changed
+404/−267 lines, 57 filesdep −mtldep ~inspection-testingdep ~transformersPVP: major bump suggested
API removals or changes: PVP suggests a major version bump
Dependencies removed: mtl
Dependency ranges changed: inspection-testing, transformers
API changes (from Hackage documentation)
- Algebra.Graph.Internal: forEach :: Applicative f => Set a -> (a -> f b) -> f ()
+ Algebra.Graph.Example.Todo: (>*<) :: Ord a => Todo a -> Todo a -> Todo a
+ Algebra.Graph.Example.Todo: (~*~) :: Ord a => Todo a -> Todo a -> Todo a
+ Algebra.Graph.Example.Todo: data Todo a
+ Algebra.Graph.Example.Todo: high :: Todo a -> Todo a
+ Algebra.Graph.Example.Todo: instance (Data.String.IsString a, GHC.Classes.Ord a) => Data.String.IsString (Algebra.Graph.Example.Todo.Todo a)
+ Algebra.Graph.Example.Todo: instance (Data.String.IsString a, GHC.Classes.Ord a) => GHC.Num.Num (Algebra.Graph.Example.Todo.Todo a)
+ Algebra.Graph.Example.Todo: instance (GHC.Show.Show a, GHC.Classes.Ord a) => GHC.Show.Show (Algebra.Graph.Example.Todo.Todo a)
+ Algebra.Graph.Example.Todo: instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Example.Todo.Todo a)
+ Algebra.Graph.Example.Todo: instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Example.Todo.Todo a)
+ Algebra.Graph.Example.Todo: low :: Todo a -> Todo a
+ Algebra.Graph.Example.Todo: priority :: Int -> Todo a -> Todo a
+ Algebra.Graph.Example.Todo: todo :: forall a. Ord a => Todo a -> Maybe [a]
Files
- CHANGES.md +4/−0
- LICENSE +1/−1
- README.md +1/−1
- algebraic-graphs.cabal +8/−7
- src/Algebra/Graph.hs +5/−5
- src/Algebra/Graph/Acyclic/AdjacencyMap.hs +1/−1
- src/Algebra/Graph/AdjacencyIntMap.hs +1/−1
- src/Algebra/Graph/AdjacencyIntMap/Algorithm.hs +53/−59
- src/Algebra/Graph/AdjacencyMap.hs +1/−1
- src/Algebra/Graph/AdjacencyMap/Algorithm.hs +54/−59
- src/Algebra/Graph/Bipartite/AdjacencyMap.hs +2/−2
- src/Algebra/Graph/Bipartite/AdjacencyMap/Algorithm.hs +10/−9
- src/Algebra/Graph/Class.hs +1/−1
- src/Algebra/Graph/Example/Todo.hs +63/−0
- src/Algebra/Graph/Export.hs +1/−1
- src/Algebra/Graph/Export/Dot.hs +1/−1
- src/Algebra/Graph/HigherKinded/Class.hs +1/−1
- src/Algebra/Graph/Internal.hs +5/−9
- src/Algebra/Graph/Label.hs +1/−1
- src/Algebra/Graph/Labelled.hs +1/−1
- src/Algebra/Graph/Labelled/AdjacencyMap.hs +1/−1
- src/Algebra/Graph/Labelled/Example/Automaton.hs +1/−1
- src/Algebra/Graph/Labelled/Example/Network.hs +1/−1
- src/Algebra/Graph/NonEmpty.hs +2/−2
- src/Algebra/Graph/NonEmpty/AdjacencyMap.hs +1/−1
- src/Algebra/Graph/Relation.hs +1/−1
- src/Algebra/Graph/Relation/Preorder.hs +1/−1
- src/Algebra/Graph/Relation/Reflexive.hs +1/−1
- src/Algebra/Graph/Relation/Symmetric.hs +1/−1
- src/Algebra/Graph/Relation/Transitive.hs +1/−1
- src/Algebra/Graph/ToGraph.hs +1/−1
- src/Algebra/Graph/Undirected.hs +1/−1
- src/Data/Graph/Typed.hs +1/−1
- test/Algebra/Graph/Test.hs +1/−1
- test/Algebra/Graph/Test/API.hs +1/−1
- test/Algebra/Graph/Test/Acyclic/AdjacencyMap.hs +1/−1
- test/Algebra/Graph/Test/AdjacencyIntMap.hs +1/−1
- test/Algebra/Graph/Test/AdjacencyMap.hs +1/−1
- test/Algebra/Graph/Test/Arbitrary.hs +1/−1
- test/Algebra/Graph/Test/Bipartite/AdjacencyMap.hs +1/−1
- test/Algebra/Graph/Test/Example/Todo.hs +81/−0
- test/Algebra/Graph/Test/Export.hs +1/−1
- test/Algebra/Graph/Test/Generic.hs +1/−1
- test/Algebra/Graph/Test/Graph.hs +1/−1
- test/Algebra/Graph/Test/Internal.hs +1/−1
- test/Algebra/Graph/Test/Label.hs +1/−1
- test/Algebra/Graph/Test/Labelled/AdjacencyMap.hs +1/−1
- test/Algebra/Graph/Test/Labelled/Graph.hs +1/−1
- test/Algebra/Graph/Test/NonEmpty/AdjacencyMap.hs +1/−1
- test/Algebra/Graph/Test/NonEmpty/Graph.hs +1/−1
- test/Algebra/Graph/Test/Relation.hs +1/−1
- test/Algebra/Graph/Test/Relation/Symmetric.hs +71/−0
- test/Algebra/Graph/Test/Relation/SymmetricRelation.hs +0/−71
- test/Algebra/Graph/Test/RewriteRules.hs +1/−1
- test/Algebra/Graph/Test/Undirected.hs +1/−1
- test/Data/Graph/Test/Typed.hs +1/−1
- test/Main.hs +3/−1
CHANGES.md view
@@ -1,5 +1,9 @@ # Change log +## 0.6.1++* Drop dependency on `mtl`.+ ## 0.6 * #276: Add `Monoid` and `Semigroup` instances.
LICENSE view
@@ -1,6 +1,6 @@ MIT License -Copyright (c) 2016-2021 Andrey Mokhov+Copyright (c) 2016-2022 Andrey Mokhov Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal
README.md view
@@ -1,6 +1,6 @@ # Algebraic graphs -[](https://hackage.haskell.org/package/algebraic-graphs) [](https://github.com/snowleopard/alga/actions)+[](https://hackage.haskell.org/package/algebraic-graphs) [](https://github.com/snowleopard/alga/actions) **Alga** is a library for algebraic construction and manipulation of graphs in Haskell. See [this Haskell Symposium paper](https://github.com/snowleopard/alga-paper) and the
algebraic-graphs.cabal view
@@ -1,18 +1,18 @@ cabal-version: 2.2 name: algebraic-graphs-version: 0.6+version: 0.6.1 synopsis: A library for algebraic graph construction and transformation license: MIT license-file: LICENSE author: Andrey Mokhov <andrey.mokhov@gmail.com>, github: @snowleopard maintainer: Andrey Mokhov <andrey.mokhov@gmail.com>, github: @snowleopard, Alexandre Moine <alexandre@moine.me>, github: @nobrakal-copyright: Andrey Mokhov, 2016-2021+copyright: Andrey Mokhov, 2016-2022 homepage: https://github.com/snowleopard/alga bug-reports: https://github.com/snowleopard/alga/issues category: Algebra, Algorithms, Data Structures, Graphs build-type: Simple-tested-with: GHC==9.0, GHC==8.10, GHC==8.8, GHC==8.6, GHC==8.4+tested-with: GHC==9.2, GHC==9.0, GHC==8.10, GHC==8.8, GHC==8.6, GHC==8.4 description: <https://github.com/snowleopard/alga Alga> is a library for algebraic construction and manipulation of graphs in Haskell. See <https://github.com/snowleopard/alga-paper this paper>@@ -68,10 +68,9 @@ common common-settings build-depends: array >= 0.4 && < 0.6,- base >= 4.7 && < 5,+ base >= 4.11 && < 5, containers >= 0.5.5.1 && < 0.8, deepseq >= 1.3.0.1 && < 1.5,- mtl >= 2.1 && < 2.3, transformers >= 0.4 && < 0.6 default-language: Haskell2010 default-extensions: ConstraintKinds@@ -113,6 +112,7 @@ Algebra.Graph.Bipartite.AdjacencyMap, Algebra.Graph.Bipartite.AdjacencyMap.Algorithm, Algebra.Graph.Class,+ Algebra.Graph.Example.Todo, Algebra.Graph.Export, Algebra.Graph.Export.Dot, Algebra.Graph.HigherKinded.Class,@@ -144,6 +144,7 @@ Algebra.Graph.Test.AdjacencyMap, Algebra.Graph.Test.Arbitrary, Algebra.Graph.Test.Bipartite.AdjacencyMap,+ Algebra.Graph.Test.Example.Todo Algebra.Graph.Test.Export, Algebra.Graph.Test.Generic, Algebra.Graph.Test.Graph,@@ -155,12 +156,12 @@ Algebra.Graph.Test.NonEmpty.AdjacencyMap, Algebra.Graph.Test.NonEmpty.Graph, Algebra.Graph.Test.Relation,- Algebra.Graph.Test.Relation.SymmetricRelation,+ Algebra.Graph.Test.Relation.Symmetric, Algebra.Graph.Test.RewriteRules, Data.Graph.Test.Typed build-depends: algebraic-graphs, extra >= 1.4 && < 2,- inspection-testing >= 0.4.2.2 && < 0.5,+ inspection-testing >= 0.4.6.0 && < 0.5, QuickCheck >= 2.14 && < 2.15 other-extensions: ConstrainedClassMethods TemplateHaskell
src/Algebra/Graph.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental@@ -52,7 +52,7 @@ import Control.Applicative (Alternative) import Control.DeepSeq import Control.Monad (MonadPlus (..))-import Control.Monad.State (runState, get, put)+import Control.Monad.Trans.State (runState, get, put) import Data.Foldable (toList) import Data.Maybe (fromMaybe) import Data.String@@ -61,9 +61,9 @@ import Algebra.Graph.Internal +import qualified Control.Applicative import qualified Algebra.Graph.AdjacencyMap as AM import qualified Algebra.Graph.AdjacencyIntMap as AIM-import qualified Control.Applicative as Ap import qualified Data.Graph as KL import qualified Data.IntSet as IntSet import qualified Data.Set as Set@@ -283,8 +283,8 @@ -- | `>>=` is a good consumer and producer. instance Monad Graph where- return = pure- g >>= f = buildg $ \e v o c -> foldg e (composeR (foldg e v o c) f) o c g+ return = pure+ g >>= f = buildg $ \e v o c -> foldg e (composeR (foldg e v o c) f) o c g {-# INLINE (>>=) #-} instance Alternative Graph where
src/Algebra/Graph/Acyclic/AdjacencyMap.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Acyclic.AdjacencyMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/AdjacencyIntMap.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.AdjacencyIntMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/AdjacencyIntMap/Algorithm.hs view
@@ -1,9 +1,8 @@-{-# language LambdaCase #-}-+{-# LANGUAGE LambdaCase #-} ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.AdjacencyIntMap.Algorithm--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : unstable@@ -32,10 +31,10 @@ ) where import Control.Monad-import Control.Monad.Cont-import Control.Monad.State.Strict+import Control.Monad.Trans.Cont+import Control.Monad.Trans.State.Strict import Data.Either-import Data.List.NonEmpty (NonEmpty(..),(<|))+import Data.List.NonEmpty (NonEmpty(..), (<|)) import Data.Tree import Algebra.Graph.AdjacencyIntMap@@ -44,16 +43,15 @@ import qualified Data.IntMap.Strict as IntMap import qualified Data.IntSet as IntSet --- | Compute the /breadth-first search/ forest of a graph, such that--- adjacent vertices are explored in increasing order with respect--- to their 'Ord' instance. The search is seeded by a list of--- argument vertices that will be the roots of the resulting--- forest. Duplicates in the list will have their first occurrence--- expanded and subsequent ones ignored. Argument vertices not in--- the graph are also ignored.+-- | Compute the /breadth-first search/ forest of a graph, such that adjacent+-- vertices are explored in increasing order according to their 'Ord' instance.+-- The search is seeded by a list of vertices that will become the roots of the+-- resulting forest. Duplicates in the list will have their first occurrence+-- expanded and subsequent ones ignored. The seed vertices that do not belong to+-- the graph are also ignored. ----- Let /L/ be the number of seed vertices. Complexity:--- /O((L+m)*min(n,W))/ time and /O(n)/ space.+-- Complexity: /O((L+m)*log n)/ time and /O(n)/ space, where /L/ is the number+-- of seed vertices. -- -- @ -- 'forest' (bfsForest [1,2] $ 'edge' 1 2) == 'vertices' [1,2]@@ -80,14 +78,13 @@ when new $ modify' (IntSet.insert v) return new --- | This is 'bfsForest' with the resulting forest converted to a--- level structure. Adjacent vertices are explored in increasing--- order with respect to their 'Ord' instance. Flattening the result--- via @'concat' . 'bfs' vs@ gives an enumeration of vertices--- reachable from @vs@ in breadth first order.+-- | A version of 'bfsForest' where the resulting forest is converted to a level+-- structure. Adjacent vertices are explored in the increasing order according+-- to their 'Ord' instance. Flattening the result via @'concat'@ @.@ @'bfs'@ @vs@+-- gives an enumeration of vertices reachable from @vs@ in the BFS order. ----- Let /L/ be the number of seed vertices. Complexity:--- /O((L+m)*min(n,W))/ time and /O(n)/ space.+-- Complexity: /O((L+m)*min(n,W))/ time and /O(n)/ space, where /L/ is the+-- number of seed vertices. -- -- @ -- bfs vs 'empty' == []@@ -108,11 +105,10 @@ bfs :: [Int] -> AdjacencyIntMap -> [[Int]] bfs vs = map concat . List.transpose . map levels . bfsForest vs --- | Compute the /depth-first search/ forest of a graph, where--- adjacent vertices are expanded in increasing order with respect--- to their 'Ord' instance.+-- | Compute the /depth-first search/ forest of a graph, where adjacent vertices+-- are explored in the increasing order according to their 'Ord' instance. ----- Complexity: /O((n+m)*min(n,W))/ time and /O(n)/ space.+-- Complexity: /O((n+m)*min(n,W))/ time and /O(n)/ space. -- -- @ -- dfsForest 'empty' == []@@ -135,15 +131,14 @@ dfsForest :: AdjacencyIntMap -> Forest Int dfsForest g = dfsForestFrom' (vertexList g) g --- | Compute the /depth-first search/ forest of a graph from the given--- vertices, where adjacent vertices are expanded in increasing--- order with respect to to their 'Ord' instance. Note that the--- resulting forest does not necessarily span the whole graph, as--- some vertices may be unreachable. Any of the given vertices which--- are not in the graph are ignored.+-- | Compute the /depth-first search/ forest of a graph starting from the given+-- seed vertices, where adjacent vertices are explored in the increasing order+-- according to their 'Ord' instance. Note that the resulting forest does not+-- necessarily span the whole graph, as some vertices may be unreachable. The+-- seed vertices which do not belong to the graph are ignored. ----- Let /L/ be the number of seed vertices. Complexity:--- /O((L+m)*min(n,W))/ time and /O(n)/ space.+-- Complexity: /O((L+m)*log n)/ time and /O(n)/ space, where /L/ be the number+-- of seed vertices. -- -- @ -- dfsForestFrom vs 'empty' == []@@ -179,12 +174,12 @@ when new $ modify' (IntSet.insert v) return new --- | Compute the vertices visited by /depth-first search/ in a graph--- from the given vertices. Adjacent vertices are explored in--- increasing order with respect to their 'Ord' instance.+-- | Return the list vertices visited by the /depth-first search/ in a graph,+-- starting from the given seed vertices. Adjacent vertices are explored in the+-- increasing order according to their 'Ord' instance. ----- Let /L/ be the number of seed vertices. Complexity:--- /O((L+m)*min(n,W))/ time and /O(n)/ space.+-- Complexity: /O((L+m)*log n)/ time and /O(n)/ space, where /L/ is the number+-- of seed vertices. -- -- @ -- dfs vs $ 'empty' == []@@ -202,11 +197,10 @@ dfs :: [Int] -> AdjacencyIntMap -> [Int] dfs vs = dfsForestFrom vs >=> flatten --- | Compute the list of vertices that are /reachable/ from a given--- source vertex in a graph. The vertices in the resulting list--- appear in /depth-first order/.+-- | Return the list of vertices that are /reachable/ from a given source vertex+-- in a graph. The vertices in the resulting list appear in the /depth-first order/. ----- Complexity: /O(m*min(n,W))/ time and /O(n)/ space.+-- Complexity: /O(m*log n)/ time and /O(n)/ space. -- -- @ -- reachable x $ 'empty' == []@@ -223,14 +217,14 @@ reachable x = dfs [x] type Cycle = NonEmpty+type Result = Either (Cycle Int) [Int] data NodeState = Entered | Exited data S = S { parent :: IntMap.IntMap Int , entry :: IntMap.IntMap NodeState , order :: [Int] } -topSort' :: (MonadState S m, MonadCont m)- => AdjacencyIntMap -> m (Either (Cycle Int) [Int])-topSort' g = callCC $ \cyclic ->+topSort' :: AdjacencyIntMap -> StateT S (Cont Result) Result+topSort' g = liftCallCC' callCC $ \cyclic -> do let vertices = map fst $ IntMap.toDescList $ adjacencyIntMap g adjacent = IntSet.toDescList . flip postIntSet g dfsRoot x = nodeState x >>= \case@@ -258,18 +252,17 @@ | head == curr = xs | otherwise = aux (parent IntMap.! curr <| xs) --- | Compute a topological sort of a DAG or discover a cycle.+-- | Compute a topological sort of a graph or discover a cycle. ----- Vertices are expanded in decreasing order with respect to their--- 'Ord' instance. This gives the lexicographically smallest--- topological ordering in the case of success. In the case of--- failure, the cycle is characterized by being the--- lexicographically smallest up to rotation with respect to @Ord--- (Dual Int)@ in the first connected component of the graph--- containing a cycle, where the connected components are ordered by--- their largest vertex with respect to @Ord a@.+-- Vertices are explored in the decreasing order according to their 'Ord'+-- instance. This gives the lexicographically smallest topological ordering in+-- the case of success. In the case of failure, the cycle is characterized by+-- being the lexicographically smallest up to rotation with respect to+-- @Ord@ @(Dual@ @Int)@ in the first connected component of the graph containing+-- a cycle, where the connected components are ordered by their largest vertex+-- with respect to @Ord a@. ----- Complexity: /O((n+m)*min(n,W))/ time and /O(n)/ space.+-- Complexity: /O((n+m)*min(n,W))/ time and /O(n)/ space. -- -- @ -- topSort (1 * 2 + 3 * 1) == Right [3,1,2]@@ -284,12 +277,13 @@ -- topSort . 'vertices' == Right . 'nub' . 'sort' -- @ topSort :: AdjacencyIntMap -> Either (Cycle Int) [Int]-topSort g = runContT (evalStateT (topSort' g) initialState) id where- initialState = S IntMap.empty IntMap.empty []+topSort g = runCont (evalStateT (topSort' g) initialState) id+ where+ initialState = S IntMap.empty IntMap.empty [] -- | Check if a given graph is /acyclic/. ----- Complexity: /O((n+m)*min(n,W))/ time and /O(n)/ space.+-- Complexity: /O((n+m)*min(n,W))/ time and /O(n)/ space. -- -- @ -- isAcyclic (1 * 2 + 3 * 1) == True
src/Algebra/Graph/AdjacencyMap.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.AdjacencyMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/AdjacencyMap/Algorithm.hs view
@@ -1,9 +1,8 @@-{-# language LambdaCase #-}-+{-# LANGUAGE LambdaCase #-} ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.AdjacencyMap.Algorithm--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : unstable@@ -28,10 +27,11 @@ ) where import Control.Monad-import Control.Monad.Cont-import Control.Monad.State.Strict+import Control.Monad.Trans.Cont+import Control.Monad.Trans.State.Strict+import Data.Foldable (for_) import Data.Either-import Data.List.NonEmpty (NonEmpty(..),(<|))+import Data.List.NonEmpty (NonEmpty(..), (<|)) import Data.Maybe import Data.Tree @@ -44,16 +44,15 @@ import qualified Data.Map.Strict as Map import qualified Data.Set as Set --- | Compute the /breadth-first search/ forest of a graph, such that--- adjacent vertices are explored in increasing order with respect--- to their 'Ord' instance. The search is seeded by a list of--- argument vertices that will be the roots of the resulting--- forest. Duplicates in the list will have their first occurrence--- expanded and subsequent ones ignored. Argument vertices not in--- the graph are also ignored.+-- | Compute the /breadth-first search/ forest of a graph, such that adjacent+-- vertices are explored in increasing order according to their 'Ord' instance.+-- The search is seeded by a list of vertices that will become the roots of the+-- resulting forest. Duplicates in the list will have their first occurrence+-- expanded and subsequent ones ignored. The seed vertices that do not belong to+-- the graph are also ignored. ----- Let /L/ be the number of seed vertices. Complexity:--- /O((L+m)*log n)/ time and /O(n)/ space.+-- Complexity: /O((L+m)*log n)/ time and /O(n)/ space, where /L/ is the number+-- of seed vertices. -- -- @ -- 'forest' (bfsForest [1,2] $ 'edge' 1 2) == 'vertices' [1,2]@@ -80,14 +79,13 @@ when new $ modify' (Set.insert v) return new --- | This is 'bfsForest' with the resulting forest converted to a--- level structure. Adjacent vertices are explored in increasing--- order with respect to their 'Ord' instance. Flattening the result--- via @'concat' . 'bfs' vs@ gives an enumeration of vertices--- reachable from @vs@ in breadth first order.+-- | A version of 'bfsForest' where the resulting forest is converted to a level+-- structure. Adjacent vertices are explored in the increasing order according+-- to their 'Ord' instance. Flattening the result via @'concat'@ @.@ @'bfs'@ @vs@+-- gives an enumeration of vertices reachable from @vs@ in the BFS order. ----- Let /L/ be the number of seed vertices. Complexity:--- /O((L+m)*log n)/ time and /O(n)/ space.+-- Complexity: /O((L+m)*min(n,W))/ time and /O(n)/ space, where /L/ is the+-- number of seed vertices. -- -- @ -- bfs vs 'empty' == []@@ -108,11 +106,10 @@ bfs :: Ord a => [a] -> AdjacencyMap a -> [[a]] bfs vs = map concat . List.transpose . map levels . bfsForest vs --- | Compute the /depth-first search/ forest of a graph, where--- adjacent vertices are expanded in increasing order with respect--- to their 'Ord' instance.+-- | Compute the /depth-first search/ forest of a graph, where adjacent vertices+-- are explored in the increasing order according to their 'Ord' instance. ----- Complexity: /O((n+m)*log n)/ time and /O(n)/ space.+-- Complexity: /O((n+m)*min(n,W))/ time and /O(n)/ space. -- -- @ -- dfsForest 'empty' == []@@ -135,15 +132,14 @@ dfsForest :: Ord a => AdjacencyMap a -> Forest a dfsForest g = dfsForestFrom' (vertexList g) g --- | Compute the /depth-first search/ forest of a graph from the given--- vertices, where adjacent vertices are expanded in increasing--- order with respect to their 'Ord' instance. Note that the--- resulting forest does not necessarily span the whole graph, as--- some vertices may be unreachable. Any of the given vertices which--- are not in the graph are ignored.+-- | Compute the /depth-first search/ forest of a graph starting from the given+-- seed vertices, where adjacent vertices are explored in the increasing order+-- according to their 'Ord' instance. Note that the resulting forest does not+-- necessarily span the whole graph, as some vertices may be unreachable. The+-- seed vertices which do not belong to the graph are ignored. ----- Let /L/ be the number of seed vertices. Complexity: /O((L+m)*log n)/--- time and /O(n)/ space.+-- Complexity: /O((L+m)*log n)/ time and /O(n)/ space, where /L/ be the number+-- of seed vertices. -- -- @ -- dfsForestFrom vs 'empty' == []@@ -179,12 +175,12 @@ when new $ modify' (Set.insert v) return new --- | Compute the vertices visited by /depth-first search/ in a graph--- from the given vertices. Adjacent vertices are expanded in--- increasing order with respect to their 'Ord' instance.+-- | Return the list vertices visited by the /depth-first search/ in a graph,+-- starting from the given seed vertices. Adjacent vertices are explored in the+-- increasing order according to their 'Ord' instance. ----- Let /L/ be the number of seed vertices. Complexity: /O((L+m)*log n)/--- time and /O(n)/ space.+-- Complexity: /O((L+m)*log n)/ time and /O(n)/ space, where /L/ is the number+-- of seed vertices. -- -- @ -- dfs vs $ 'empty' == []@@ -202,11 +198,10 @@ dfs :: Ord a => [a] -> AdjacencyMap a -> [a] dfs vs = dfsForestFrom vs >=> flatten --- | Compute the list of vertices that are /reachable/ from a given--- source vertex in a graph. The vertices in the resulting list--- appear in /depth-first order/.+-- | Return the list of vertices that are /reachable/ from a given source vertex+-- in a graph. The vertices in the resulting list appear in the /depth-first order/. ----- Complexity: /O(m*log n)/ time and /O(n)/ space.+-- Complexity: /O(m*log n)/ time and /O(n)/ space. -- -- @ -- reachable x $ 'empty' == []@@ -223,14 +218,14 @@ reachable x = dfs [x] type Cycle = NonEmpty+type Result a = Either (Cycle a) [a] data NodeState = Entered | Exited data S a = S { parent :: Map.Map a a , entry :: Map.Map a NodeState , order :: [a] } -topSort' :: (Ord a, MonadState (S a) m, MonadCont m)- => AdjacencyMap a -> m (Either (Cycle a) [a])-topSort' g = callCC $ \cyclic ->+topSort' :: Ord a => AdjacencyMap a -> StateT (S a) (Cont (Result a)) (Result a)+topSort' g = liftCallCC' callCC $ \cyclic -> do let vertices = map fst $ Map.toDescList $ adjacencyMap g adjacent = Set.toDescList . flip postSet g dfsRoot x = nodeState x >>= \case@@ -258,18 +253,17 @@ | head == curr = xs | otherwise = aux (parent Map.! curr <| xs) --- | Compute a topological sort of a DAG or discover a cycle.+-- | Compute a topological sort of a graph or discover a cycle. ----- Vertices are expanded in decreasing order with respect to their--- 'Ord' instance. This gives the lexicographically smallest--- topological ordering in the case of success. In the case of--- failure, the cycle is characterized by being the--- lexicographically smallest up to rotation with respect to @Ord--- (Dual a)@ in the first connected component of the graph--- containing a cycle, where the connected components are ordered by--- their largest vertex with respect to @Ord a@.+-- Vertices are explored in the decreasing order according to their 'Ord'+-- instance. This gives the lexicographically smallest topological ordering in+-- the case of success. In the case of failure, the cycle is characterized by+-- being the lexicographically smallest up to rotation with respect to+-- @Ord@ @(Dual@ @Int)@ in the first connected component of the graph containing+-- a cycle, where the connected components are ordered by their largest vertex+-- with respect to @Ord a@. ----- Complexity: /O((n+m)*log n)/ time and /O(n)/ space.+-- Complexity: /O((n+m)*min(n,W))/ time and /O(n)/ space. -- -- @ -- topSort (1 * 2 + 3 * 1) == Right [3,1,2]@@ -285,8 +279,9 @@ -- topSort . 'vertices' == Right . 'nub' . 'sort' -- @ topSort :: Ord a => AdjacencyMap a -> Either (Cycle a) [a]-topSort g = runContT (evalStateT (topSort' g) initialState) id where- initialState = S Map.empty Map.empty []+topSort g = runCont (evalStateT (topSort' g) initialState) id+ where+ initialState = S Map.empty Map.empty [] -- | Check if a given graph is /acyclic/. --@@ -343,7 +338,7 @@ gabowSCC :: Ord a => AdjacencyMap a -> State (StateSCC a) () gabowSCC g = do let dfs u = do p_u <- enter u- forEach (postSet u g) $ \v -> do+ for_ (postSet u g) $ \v -> do preorderId v >>= \case Nothing -> do updated <- dfs v
src/Algebra/Graph/Bipartite/AdjacencyMap.hs view
@@ -1,7 +1,7 @@ ---------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Bipartite.AdjacencyMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental@@ -55,7 +55,7 @@ import Control.Monad import Control.Monad.Trans.Maybe-import Control.Monad.State+import Control.Monad.Trans.State import Data.Either import Data.Foldable (asum) import Data.List ((\\), sort)
src/Algebra/Graph/Bipartite/AdjacencyMap/Algorithm.hs view
@@ -2,7 +2,7 @@ ---------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Bipartite.AdjacencyMap.Algorithm--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental@@ -35,8 +35,9 @@ import Algebra.Graph.Bipartite.AdjacencyMap import Control.Monad (guard, when)+import Control.Monad.Trans.Class (lift) import Control.Monad.Trans.Maybe (MaybeT(..))-import Control.Monad.State (MonadState(..), State, runState, modify)+import Control.Monad.Trans.State (State, runState, get, put, modify) import Control.Monad.ST (ST, runST) import Data.Either (fromLeft) import Data.Foldable (asum, foldl')@@ -127,19 +128,19 @@ dfs = asum [ processVertex v | v <- AM.vertexList g ] -- processVertex :: a -> PartMonad a- processVertex v = do partMap <- get+ processVertex v = do partMap <- lift get guard (Map.notMember v partMap) inVertex LeftPart v -- inVertex :: Part -> a -> PartMonad a inVertex vertexPart v = (v :) <$> do- modify (Map.insert v vertexPart)+ lift $ modify (Map.insert v vertexPart) let otherVertexPart = otherPart vertexPart asum [ onEdge otherVertexPart u | u <- Set.toAscList (AM.postSet v g) ] {-# INLINE onEdge #-} -- onEdge :: Part -> a -> PartMonad a- onEdge vertexPart v = do partMap <- get+ onEdge vertexPart v = do partMap <- lift get case Map.lookup v partMap of Nothing -> inVertex vertexPart v Just part -> do guard (vertexPart /= part)@@ -497,14 +498,14 @@ dfs = asum [ inVertex v | v <- leftVertexList g, not (leftCovered v m) ] inVertex :: a -> AugPathMonad a b- inVertex a = do (as, bs) <- get+ inVertex a = do (as, bs) <- lift get guard (a `Set.member` as)- put (Set.delete a as, bs)+ lift $ put (Set.delete a as, bs) asum [ onEdge a b | b <- neighbours a ] onEdge :: a -> b -> AugPathMonad a b- onEdge a b = addEdge a b <$> do (as, bs) <- get- put (as, Set.insert b bs)+ onEdge a b = addEdge a b <$> do (as, bs) <- lift get+ lift $ put (as, Set.insert b bs) case b `Map.lookup` pairOfRight m of Just a -> inVertex a Nothing -> return Nil
src/Algebra/Graph/Class.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Class--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
+ src/Algebra/Graph/Example/Todo.hs view
@@ -0,0 +1,63 @@+{-# LANGUAGE OverloadedStrings #-}+module Algebra.Graph.Example.Todo (Todo, todo, low, high, (~*~), (>*<), priority) where++import Data.Map (Map)+import Data.String++import Algebra.Graph.AdjacencyMap as AM+import Algebra.Graph.AdjacencyMap.Algorithm as AM+import Algebra.Graph.Class as C++import qualified Data.Map as Map++data Todo a = T (Map a Int) (AdjacencyMap a) deriving Show++instance Ord a => Eq (Todo a) where+ x == y = todo x == todo y++instance (IsString a, Ord a) => IsString (Todo a) where+ fromString = C.vertex . fromString++-- Lower the priority of items in a given todo list+low :: Todo a -> Todo a+low (T p g) = T (Map.map (subtract 1) p) g++-- Raise the priority of items in a given todo list+high :: Todo a -> Todo a+high (T p g) = T (Map.map (+1) p) g++-- Specify exact priority of items in a given todo list (default 0)+priority :: Int -> Todo a -> Todo a+priority x (T p g) = T (Map.map (const x) p) g++-- Pull the arguments together as close as possible+(~*~) :: Ord a => Todo a -> Todo a -> Todo a+x ~*~ y = low x `C.connect` high y++-- Repel the arguments as far as possible+(>*<) :: Ord a => Todo a -> Todo a -> Todo a+x >*< y = high x `C.connect` low y++todo :: forall a. Ord a => Todo a -> Maybe [a]+todo (T p g) =+ case AM.topSort $ gmap prioritise g of+ Left _ -> Nothing+ Right xs -> Just $ map snd xs+ where+ prioritise :: a -> (Int, a)+ prioritise x = (negate $ Map.findWithDefault 0 x p, x)++instance (IsString a, Ord a) => Num (Todo a) where+ fromInteger i = fromString $ show (fromInteger i :: Integer)+ (+) = C.overlay+ (*) = C.connect+ signum = const C.empty+ abs = id+ negate = id++instance Ord a => Graph (Todo a) where+ type Vertex (Todo a) = a+ empty = T Map.empty AM.empty+ vertex x = T (Map.singleton x 0) (C.vertex x)+ overlay (T p1 g1) (T p2 g2) = T (Map.unionWith (+) p1 p2) (C.overlay g1 g2)+ connect (T p1 g1) (T p2 g2) = T (Map.unionWith (+) p1 p2) (C.connect g1 g2)
src/Algebra/Graph/Export.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Export--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Export/Dot.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Export.Dot--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/HigherKinded/Class.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.HigherKinded.Class--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Internal.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Internal--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental@@ -23,8 +23,8 @@ maybeF, -- * Utilities- cartesianProductWith, forEach, coerce00, coerce10, coerce20, coerce01,- coerce11, coerce21+ cartesianProductWith, coerce00, coerce10, coerce20, coerce01, coerce11,+ coerce21 ) where import Data.Coerce@@ -113,8 +113,8 @@ foldr1Safe f = foldr (maybeF f) Nothing {-# INLINE foldr1Safe #-} --- | Auxiliary function that try to apply a function to a base case and a 'Maybe'--- value and return 'Just' the result or 'Just' the base case.+-- | An auxiliary function that tries to apply a function to a base case and a+-- 'Maybe' value and returns 'Just' the result or 'Just' the base case. maybeF :: (a -> b -> a) -> a -> Maybe b -> Maybe a maybeF f x = Just . maybe x (f x) {-# INLINE maybeF #-}@@ -125,10 +125,6 @@ cartesianProductWith :: Ord c => (a -> b -> c) -> Set a -> Set b -> Set c cartesianProductWith f x y = Set.fromList [ f a b | a <- Set.toAscList x, b <- Set.toAscList y ]---- | Perform an applicative action for each element of a set.-forEach :: Applicative f => Set a -> (a -> f b) -> f ()-forEach s f = Set.foldr (\a u -> f a *> u) (pure ()) s -- TODO: Get rid of this boilerplate.
src/Algebra/Graph/Label.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Label--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Labelled.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Labelled--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Labelled/AdjacencyMap.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Labelled.AdjacencyMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Labelled/Example/Automaton.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Labelled.Example.Automaton--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Labelled/Example/Network.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Labelled.Example.Network--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/NonEmpty.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.NonEmpty--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental@@ -54,7 +54,7 @@ import Control.DeepSeq import Control.Monad-import Control.Monad.State+import Control.Monad.Trans.State import Data.List.NonEmpty (NonEmpty (..)) import Data.String
src/Algebra/Graph/NonEmpty/AdjacencyMap.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.NonEmpty.AdjacencyMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Relation.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Relation--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Relation/Preorder.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Relation.Preorder--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Relation/Reflexive.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Relation.Reflexive--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Relation/Symmetric.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Relation.Symmetric--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Relation/Transitive.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Relation.Transitive--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/ToGraph.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.ToGraph--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Algebra/Graph/Undirected.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Undirected--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
src/Data/Graph/Typed.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Data.Graph.Typed--- Copyright : (c) Anton Lorenzen, Andrey Mokhov 2016-2021+-- Copyright : (c) Anton Lorenzen, Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : anfelor@posteo.de, andrey.mokhov@gmail.com -- Stability : unstable
test/Algebra/Graph/Test.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/API.hs view
@@ -3,7 +3,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.API--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/Acyclic/AdjacencyMap.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Acyclic.AdjacencyMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/AdjacencyIntMap.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.AdjacencyIntMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/AdjacencyMap.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.AdjacencyMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/Arbitrary.hs view
@@ -3,7 +3,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Arbitrary--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/Bipartite/AdjacencyMap.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Bipartite.AdjacencyMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
+ test/Algebra/Graph/Test/Example/Todo.hs view
@@ -0,0 +1,81 @@+{-# LANGUAGE OverloadedStrings #-}++module Algebra.Graph.Test.Example.Todo (+ testTodo+ ) where++import Algebra.Graph.Class+import Algebra.Graph.Test+import Algebra.Graph.Example.Todo++testTodo :: IO ()+testTodo = do+ putStrLn "\n============ Example.Todo (Holiday) ============"+ test "A todo list is semantically Maybe [a]" $+ todo ("presents" :: Todo String) == Just ["presents"]++ test "The overlay operator (+) adds non-dependent items to the todo list" $+ todo ("coat" + "presents" :: Todo String) == Just ["coat", "presents"]++ test "The connect operator (*) adds dependency between items" $+ let+ shopping :: Todo String = "presents" + "coat" + "scarf"+ holiday :: Todo String = shopping * "pack" * "travel"+ in todo (holiday + "scarf" * "coat")+ == Just ["presents","scarf","coat", "pack","travel"]++ test "Contradictory constraints make the todo list impossible to schedule" $+ let+ shopping :: Todo String = "presents" + "coat" + "scarf"+ holiday :: Todo String = shopping * "pack" * "travel"+ in todo (holiday + "travel" * "presents") == Nothing++ test "Introduce item priority to schedule the todo list" $+ let+ shopping :: Todo String+ shopping = "presents" + "coat" + low "phone wife" * "scarf"+ holiday :: Todo String+ holiday = shopping * "pack" * "travel" + "scarf" * "coat"+ in todo holiday+ == Just ["presents","phone wife","scarf","coat","pack","travel"]++ test "Custom connect operators pull/repel arguments during scheduling" $+ let+ shopping :: Todo String+ shopping = "presents" + "coat" + "phone wife" ~*~ "scarf"+ holiday :: Todo String+ holiday = shopping * "pack" * "travel" + "scarf" * "coat"+ in todo holiday+ == Just ["presents","phone wife","scarf","coat","pack","travel"]++ putStrLn "\n============ Example.Todo (Commandline) ============"+ test "The pull connect operator maintains command line semantics" $+ let+ cmdl :: Todo String+ cmdl = "gcc" * ("-c" ~*~ "src.c" + "-o" ~*~ "src.o")+ in todo cmdl == Just ["gcc","-c","src.c","-o","src.o"]++ test "Swapping flags are allowed by the commutative overlay opeartor" $+ let+ cmdl1 :: Todo String+ cmdl1 = "gcc" * ("-c" ~*~ "src.c" + "-o" ~*~ "src.o")+ cmdl2 :: Todo String+ cmdl2 = "gcc" * ("-o" ~*~ "src.o" + "-c" ~*~ "src.c")+ in cmdl1 == cmdl2++ test "The usual connect operator breaks semantics" $+ let+ cmdl :: Todo String+ cmdl = "gcc" * ("-c" * "src.c" + "-o" * "src.o")+ in+ todo cmdl == Just ["gcc","-c","-o","src.c","src.o"]++ test "Transform command lines by adding optimisation flag" $+ let+ cmdl :: Todo String+ cmdl = "gcc" * ("-c" ~*~ "src.c" + "-o" ~*~ "src.o")+ optimise :: Int -> Todo String -> Todo String+ optimise level = (* flag)+ where flag = vertex $ "-O" ++ show level+ in todo (optimise 2 cmdl) ==+ Just ["gcc","-c","src.c","-o","src.o","-O2"]
test/Algebra/Graph/Test/Export.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Export--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/Generic.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Generic--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/Graph.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Graph--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/Internal.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Internal--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/Label.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Label--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/Labelled/AdjacencyMap.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Labelled.AdjacencyMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/Labelled/Graph.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Labelled.Graph--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/NonEmpty/AdjacencyMap.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.NonEmpty.AdjacencyMap--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/NonEmpty/Graph.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.NonEmpty.Graph--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/Relation.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Relation--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
+ test/Algebra/Graph/Test/Relation/Symmetric.hs view
@@ -0,0 +1,71 @@+-----------------------------------------------------------------------------+-- |+-- Module : Algebra.Graph.Test.Relation.Symmetric+-- Copyright : (c) Andrey Mokhov 2016-2022+-- License : MIT (see the file LICENSE)+-- Maintainer : andrey.mokhov@gmail.com+-- Stability : experimental+--+-- Testsuite for "Algebra.Graph.Relation.Symmetric".+-----------------------------------------------------------------------------+module Algebra.Graph.Test.Relation.Symmetric (+ -- * Testsuite+ testSymmetricRelation+ ) where++import Algebra.Graph.Relation.Symmetric+import Algebra.Graph.Test+import Algebra.Graph.Test.API (toIntAPI, symmetricRelationAPI)+import Algebra.Graph.Test.Generic++import qualified Algebra.Graph.Relation as R++tPoly :: Testsuite Relation Ord+tPoly = ("Symmetric.Relation.", symmetricRelationAPI)++t :: TestsuiteInt Relation+t = fmap toIntAPI tPoly++type RI = R.Relation Int+type SRI = Relation Int++testSymmetricRelation :: IO ()+testSymmetricRelation = do+ putStrLn "\n============ Symmetric.Relation ============"+ test "Axioms of undirected graphs" $ size10 $ undirectedAxioms @SRI++ testConsistent t+ testSymmetricShow t++ putStrLn $ "\n============ Symmetric.Relation.toSymmetric ============"+ test "toSymmetric (edge 1 2) == edge 1 2" $+ toSymmetric (R.edge 1 2) == edge 1 (2 :: Int)++ test "toSymmetric . fromSymmetric == id" $ \(x :: SRI) ->+ (toSymmetric . fromSymmetric) x == id x++ test "fromSymmetric . toSymmetric == symmetricClosure" $ \(x :: RI) ->+ (fromSymmetric . toSymmetric) x == R.symmetricClosure x++ test "vertexCount . toSymmetric == vertexCount" $ \(x :: RI) ->+ vertexCount (toSymmetric x) == R.vertexCount x++ test "(*2) . edgeCount . toSymmetric >= edgeCount" $ \(x :: RI) ->+ ((*2) . edgeCount . toSymmetric) x >= R.edgeCount x++ putStrLn $ "\n============ Symmetric.Relation.fromSymmetric ============"+ test "fromSymmetric (edge 1 2) == edges [(1,2), (2,1)]" $+ fromSymmetric (edge 1 2) == R.edges [(1,2), (2,1 :: Int)]++ test "vertexCount . fromSymmetric == vertexCount" $ \(x :: SRI) ->+ (R.vertexCount . fromSymmetric) x == vertexCount x++ test "edgeCount . fromSymmetric <= (*2) . edgeCount" $ \(x :: SRI) ->+ (R.edgeCount . fromSymmetric) x <= ((*2) . edgeCount) x++ testSymmetricBasicPrimitives t+ testSymmetricIsSubgraphOf t+ testSymmetricToGraph t+ testSymmetricGraphFamilies t+ testSymmetricTransformations t+ testInduceJust tPoly
− test/Algebra/Graph/Test/Relation/SymmetricRelation.hs
@@ -1,71 +0,0 @@--------------------------------------------------------------------------------- |--- Module : Algebra.Graph.Test.Relation.SymmetricRelation--- Copyright : (c) Andrey Mokhov 2016-2021--- License : MIT (see the file LICENSE)--- Maintainer : andrey.mokhov@gmail.com--- Stability : experimental------ Testsuite for "Algebra.Graph.Relation.Symmetric".-------------------------------------------------------------------------------module Algebra.Graph.Test.Relation.SymmetricRelation (- -- * Testsuite- testSymmetricRelation- ) where--import Algebra.Graph.Relation.Symmetric-import Algebra.Graph.Test-import Algebra.Graph.Test.API (toIntAPI, symmetricRelationAPI)-import Algebra.Graph.Test.Generic--import qualified Algebra.Graph.Relation as R--tPoly :: Testsuite Relation Ord-tPoly = ("Symmetric.Relation.", symmetricRelationAPI)--t :: TestsuiteInt Relation-t = fmap toIntAPI tPoly--type RI = R.Relation Int-type SRI = Relation Int--testSymmetricRelation :: IO ()-testSymmetricRelation = do- putStrLn "\n============ Symmetric.Relation ============"- test "Axioms of undirected graphs" $ size10 $ undirectedAxioms @SRI-- testConsistent t- testSymmetricShow t-- putStrLn $ "\n============ Symmetric.Relation.toSymmetric ============"- test "toSymmetric (edge 1 2) == edge 1 2" $- toSymmetric (R.edge 1 2) == edge 1 (2 :: Int)-- test "toSymmetric . fromSymmetric == id" $ \(x :: SRI) ->- (toSymmetric . fromSymmetric) x == id x-- test "fromSymmetric . toSymmetric == symmetricClosure" $ \(x :: RI) ->- (fromSymmetric . toSymmetric) x == R.symmetricClosure x-- test "vertexCount . toSymmetric == vertexCount" $ \(x :: RI) ->- vertexCount (toSymmetric x) == R.vertexCount x-- test "(*2) . edgeCount . toSymmetric >= edgeCount" $ \(x :: RI) ->- ((*2) . edgeCount . toSymmetric) x >= R.edgeCount x-- putStrLn $ "\n============ Symmetric.Relation.fromSymmetric ============"- test "fromSymmetric (edge 1 2) == edges [(1,2), (2,1)]" $- fromSymmetric (edge 1 2) == R.edges [(1,2), (2,1 :: Int)]-- test "vertexCount . fromSymmetric == vertexCount" $ \(x :: SRI) ->- (R.vertexCount . fromSymmetric) x == vertexCount x-- test "edgeCount . fromSymmetric <= (*2) . edgeCount" $ \(x :: SRI) ->- (R.edgeCount . fromSymmetric) x <= ((*2) . edgeCount) x-- testSymmetricBasicPrimitives t- testSymmetricIsSubgraphOf t- testSymmetricToGraph t- testSymmetricGraphFamilies t- testSymmetricTransformations t- testInduceJust tPoly
test/Algebra/Graph/Test/RewriteRules.hs view
@@ -2,7 +2,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.RewriteRules--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Algebra/Graph/Test/Undirected.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Algebra.Graph.Test.Undirected--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : andrey.mokhov@gmail.com -- Stability : experimental
test/Data/Graph/Test/Typed.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Data.Graph.Test.Typed--- Copyright : (c) Andrey Mokhov 2016-2021+-- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : anfelor@posteo.de, andrey.mokhov@gmail.com -- Stability : experimental
test/Main.hs view
@@ -2,6 +2,7 @@ import Algebra.Graph.Test.AdjacencyIntMap import Algebra.Graph.Test.AdjacencyMap import Algebra.Graph.Test.Bipartite.AdjacencyMap+import Algebra.Graph.Test.Example.Todo import Algebra.Graph.Test.Export import Algebra.Graph.Test.Graph import Algebra.Graph.Test.Internal@@ -11,7 +12,7 @@ import Algebra.Graph.Test.NonEmpty.AdjacencyMap import Algebra.Graph.Test.NonEmpty.Graph import Algebra.Graph.Test.Relation-import Algebra.Graph.Test.Relation.SymmetricRelation+import Algebra.Graph.Test.Relation.Symmetric import Algebra.Graph.Test.Undirected import Data.Graph.Test.Typed @@ -44,5 +45,6 @@ go "NonEmpty.Graph" testNonEmptyGraph go "Relation" testRelation go "Symmetric.Relation" testSymmetricRelation+ go "Todo" testTodo go "Typed" testTyped go "Undirected" testUndirected