topograph 1.0.0.1 → 1.0.0.2

raw patch · 2 files changed

+37/−20 lines, 2 filesdep ~basedep ~base-compatdep ~base-orphans

Dependency ranges changed: base, base-compat, base-orphans

Files

• src/Topograph.hs +28/−14
• topograph.cabal +9/−6

@@ -67,33 +67,47 @@  -- $setup ----- Graph used in examples:------ <<dag-original.png>>------ >>> let example :: Map Char (Set Char); example = Map.map Set.fromList $ Map.fromList [('a', "bxde"), ('b', "d"), ('x', "de"), ('d', "e"), ('e', "")]+-- Initial setup and imports: -- -- >>> :set -XRecordWildCards -- >>> import Data.Monoid (All (..)) -- >>> import Data.Foldable (traverse_)--- >>> import Data.List (elemIndex)+-- >>> import Data.List (elemIndex, sort) -- >>> import Data.Tree (Tree (..))+-- >>> import Data.Map (Map)+-- >>> import Data.Set (Set)+-- >>> import qualified Data.Tree as T+-- >>> import qualified Data.Map as Map+-- >>> import qualified Data.Set as Set --+-- Some compatibility imports+--+-- >>> import Control.Applicative+-- >>> import Data.Foldable (traverse_, foldMap)+--+-- Graph used in examples:+--+-- <<dag-original.png>>+--+-- >>> let example :: Map Char (Set Char); example = Map.map Set.fromList $ Map.fromList [('a', "bxde"), ('b', "d"), ('x', "de"), ('d', "e"), ('e', "")]+-- -- == Few functions to be used in examples -- -- To make examples slightly shorter: ----- >>> let fmap2 = fmap . fmap--- >>> let fmap3 = fmap . fmap2--- >>> let traverse2_ = traverse_ . traverse_--- >>> let traverse3_ = traverse_ . traverse2_+-- >>> let fmap2 f = fmap (fmap f)+-- >>> let fmap3 f = fmap (fmap2 f)+-- >>> let traverse2_ f = traverse_ (traverse_ f)+-- >>> let traverse3_ f = traverse_ (traverse2_ f) -- -- To display trees: -- -- >>> let dispTree :: Show a => Tree a -> IO (); dispTree = go 0 where go i (T.Node x xs) = putStrLn (replicate (i * 2) ' ' ++ show x) >> traverse_ (go (succ i)) xs ---+-- And fold them (this function is available in recent @containers@): --+-- >>> let foldTree f = go where go (T.Node x ts) = f x (map go ts)+--  ------------------------------------------------------------------------------- -- Graph@@ -127,7 +141,7 @@     , gEdges        :: i -> [i]        -- ^ /O(1)/. Outgoing edges. Note: target indices are larger than source index.     , gDiff         :: i -> i -> Int   -- ^ /O(1)/. Upper bound of the path length. Negative means there aren't path.     , gVerticeCount :: Int             -- ^ /O(1)/. @'gVerticeCount' g = 'length' ('gVertices' g)@-    , gVertexIndex  :: i -> Int        -- ^ /O(1)/. @'Just' ('verticeIndex' g x) = 'elemIndex' x ('gVertices' g)@. Note, there are no efficient way to convert 'Int' into 'i', convertion back and forth is discouraged on purpose.+    , gVertexIndex  :: i -> Int        -- ^ /O(1)/. @'Just' ('verticeIndex' g x) = 'elemIndex' x ('gVertices' g)@. Note, there are no efficient way to convert 'Int' into 'i', conversion back and forth is discouraged on purpose.     }  -- | Run action on topologically sorted representation of the graph.@@ -277,7 +291,7 @@ -- <<dag-tree.png>> -- -- >>> let t = runG example $ \g@G{..} -> fmap3 gFromVertex $ allPathsTree g <$> gToVertex 'a' <*> gToVertex 'e'--- >>> fmap3 (T.foldTree $ \a bs -> if null bs then [[a]] else concatMap (map (a:)) bs) t+-- >>> fmap3 (foldTree $ \a bs -> if null bs then [[a]] else concatMap (map (a:)) bs) t -- Right (Just (Just ["axde","axe","abde","ade","ae"])) -- -- >>> fmap3 (Set.fromList . treePairs) t@@ -579,7 +593,7 @@ treePairs (T.Node i js) =     [ (i, j) | T.Node j _ <- js ] ++ concatMap treePairs js --- | Consequtive pairs.+-- | Consecutive pairs. -- -- >>> pairs [1..10] -- [(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10)]

@@ -1,6 +1,6 @@ cabal-version:   2.2 name:            topograph-version:         1.0.0.1+version:         1.0.0.2 synopsis:        Directed acyclic graphs. category:        Data, Graph description:@@ -35,8 +35,11 @@    || ==8.2.2    || ==8.4.4    || ==8.6.5-   || ==8.8.3-   || ==8.10.1+   || ==8.8.4+   || ==8.10.4+   || ==9.0.2+   || ==9.2.4+   || ==9.4.1  source-repository head   type:     git@@ -45,11 +48,11 @@ library   exposed-modules:  Topograph   build-depends:-    , base          >=4.6     && <4.15-    , base-compat   ^>=0.10.5 || ^>=0.11.0+    , base          >=4.6     && <4.18+    , base-compat   ^>=0.10.5 || ^>=0.11.0 || ^>=0.12.0     , base-orphans  ^>=0.8     , containers    ^>=0.5.0.0 || ^>=0.6.0.1-    , vector        ^>=0.12+    , vector        ^>=0.12 || ^>=0.13    other-extensions:     RankNTypes