digraph 0.2.3 → 0.3.0

raw patch · 5 files changed

+55/−3 lines, 5 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +11/−0
• digraph.cabal +1/−1
• src/Data/DiGraph.hs +15/−0
• src/Data/DiGraph/FloydWarshall.hs +1/−2
• test/Data/DiGraph/Test.hs +27/−0

@@ -1,5 +1,16 @@ # Revision history for digraph +## 0.3.0 -- 2023-02-03++* Fix `fromAdjacencySets` and to preserve edge direction. This affects+  the functions for computing shortest paths, distance, and diameter. These+  functions now return correct results for directed graphs. Before these+  functions silently turned the input into an undirected graph. (Contributed by+  [Geometer1729](https://github.com/Geometer1729))++* Add `pentagon` and `ascendingCube` to the list of known graphs.+  (Contributed by [Geometer1729](https://github.com/Geometer1729))+ ## 0.2.3 -- 2023-02-02  * Support ghc-9.2 and ghc-9.4

@@ -1,6 +1,6 @@ cabal-version: 2.4 name: digraph-version: 0.2.3+version: 0.3.0 synopsis: Directed Graphs description: Directed graphs implementation that is based on unordered-containers homepage: https://github.com/kadena-io/digraph

@@ -82,6 +82,8 @@ , petersonGraph , twentyChainGraph , hoffmanSingleton+, pentagon+, ascendingCube  ) where @@ -612,3 +614,16 @@         , i <- [0 .. 4]         , let b = q_off i ((h * i + j) `mod` 5)         ]++pentagon :: DiGraph Int+pentagon = fromEdges $ HS.fromList [(i,(i+1) `mod` 5) | i <- [0..4] ]++ascendingCube :: DiGraph (Int,Int,Int)+ascendingCube = fromEdges $ HS.fromList $ mconcat+  [ [ ((0,a,b),(1,a,b))+    , ((a,0,b),(a,1,b))+    , ((a,b,0),(a,b,1))+    ]+  | a <- [0,1]+  , b <- [0,1]+  ]

@@ -66,7 +66,7 @@ -- -- (uses massiv) --- | Assumes that the input is an undirected graph and that the vertex+-- | Assumes that the input is an directed graph and that the vertex -- set is a prefix of the natural numbers. -- fromAdjacencySets :: AdjacencySets -> DenseAdjMatrix@@ -75,7 +75,6 @@     n = HM.size g     go (i :. j)         | isEdge (i, j) = 1-        | isEdge (j, i) = 1         | otherwise = 0     isEdge (a, b) = maybe False (HS.member b) $ HM.lookup a g 

@@ -40,6 +40,9 @@     , ("isSymmetric", property $ isSymmetric g)     ] +properties_directed :: Eq a => Hashable a => DiGraph a -> [(String, Property)]+properties_directed = filter ((/=) "isSymmetric" . fst) . properties_undirected+ properties_emptyGraph :: Natural -> [(String, Property)] properties_emptyGraph n = prefixProperties ("emptyGraph of order " <> show n <> ": ")     $ ("order == " <> show n, order g === n)@@ -92,6 +95,28 @@   where     g = hoffmanSingleton +properties_pentagon :: [(String,Property)]+properties_pentagon = prefixProperties "Pentagon: "+    $ ("order == 5",order g === 5)+    : ("size == 5",symSize g === 5)+    : ("outDegree == 1",maxOutDegree g === 1)+    : ("isRegular", property $ isRegular g)+    : ("diameter == 4", diameter g === Just 4)+    : properties_directed g+  where+    g = pentagon++properties_ascendingCube :: [(String,Property)]+properties_ascendingCube = prefixProperties "Ascending Cube: "+    $ ("order == 8",order g === 8)+    : ("size == 12",symSize g === 12)+    : ("outDegree == 3",maxOutDegree g === 3)+    : ("isIrRegular", property $ not $ isRegular g)+    : ("diameter == Nothing", diameter g === Nothing)+    : properties_directed g+  where+    g = ascendingCube+ -- | Test Properties. -- properties :: [(String, Property)]@@ -102,4 +127,6 @@     , properties_petersonGraph     , properties_twentyChainGraph     , properties_hoffmanSingletonGraph+    , properties_pentagon+    , properties_ascendingCube     ]