graphite 0.9.3.0 → 0.9.4.0
raw patch · 4 files changed
+27/−23 lines, 4 filesdep +semigroupsPVP: major bump suggested
API removals or changes: PVP suggests a major version bump
Dependencies added: semigroups
API changes (from Hackage documentation)
- Data.Graph.DGraph: instance Data.Hashable.Class.Hashable v => Data.Semigroup.Semigroup (Data.Graph.DGraph.DGraph v e)
- Data.Graph.DGraph: instance Data.Hashable.Class.Hashable v => GHC.Base.Monoid (Data.Graph.DGraph.DGraph v e)
- Data.Graph.Types: join :: Graph g => g v e -> g v e -> g v e
- Data.Graph.UGraph: instance Data.Hashable.Class.Hashable v => Data.Semigroup.Semigroup (Data.Graph.UGraph.UGraph v e)
- Data.Graph.UGraph: instance Data.Hashable.Class.Hashable v => GHC.Base.Monoid (Data.Graph.UGraph.UGraph v e)
+ Data.Graph.DGraph: instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => Data.Semigroup.Semigroup (Data.Graph.DGraph.DGraph v e)
+ Data.Graph.DGraph: instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => GHC.Base.Monoid (Data.Graph.DGraph.DGraph v e)
+ Data.Graph.Types: isolatedVertices :: (Graph g, Hashable v, Eq v) => g v e -> [v]
+ Data.Graph.UGraph: instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => Data.Semigroup.Semigroup (Data.Graph.UGraph.UGraph v e)
+ Data.Graph.UGraph: instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => GHC.Base.Monoid (Data.Graph.UGraph.UGraph v e)
- Data.Graph.Types: class Graph g where size = length . edgePairs density g = (2 * (e - n + 1)) / (n * (n - 3) + 2) where n = fromIntegral $ order g e = fromIntegral $ size g edgePairs g = tripleToPair <$> edgeTriples g adjacentVertices g v = tripleDestVertex <$> adjacentVertices' g v reachableAdjacentVertices g v = tripleDestVertex <$> reachableAdjacentVertices' g v degrees g = vertexDegree g <$> vertices g maxDegree = maximum . degrees minDegree = minimum . degrees avgDegree g = fromIntegral (2 * size g) / fromIntegral (order g) insertVertices vs g = foldl' (flip insertVertex) g vs incidentEdgePairs g v = tripleToPair <$> incidentEdgeTriples g v insertEdgeTriples es g = foldl' (flip insertEdgeTriple) g es insertEdgePair (v1, v2) = insertEdgeTriple (v1, v2, ()) insertEdgePairs es g = foldl' (flip insertEdgePair) g es removeVertices vs g = foldl' (flip removeVertex) g vs removeEdgePairs es g = foldl' (flip removeEdgePair) g es removeEdgePairAndVertices (v1, v2) g = removeVertex v2 $ removeVertex v1 $ removeEdgePair (v1, v2) g fromList links = go links empty where go [] g = g go ((v, es) : rest) g = go rest $ foldr (\ (v', e) g' -> insertEdgeTriple (v, v', e) g') (insertVertex v g) es
+ Data.Graph.Types: class Graph g where size = length . edgePairs density g = (2 * (e - n + 1)) / (n * (n - 3) + 2) where n = fromIntegral $ order g e = fromIntegral $ size g edgePairs g = tripleToPair <$> edgeTriples g adjacentVertices g v = tripleDestVertex <$> adjacentVertices' g v reachableAdjacentVertices g v = tripleDestVertex <$> reachableAdjacentVertices' g v degrees g = vertexDegree g <$> vertices g maxDegree = maximum . degrees minDegree = minimum . degrees avgDegree g = fromIntegral (2 * size g) / fromIntegral (order g) insertVertices vs g = foldl' (flip insertVertex) g vs incidentEdgePairs g v = tripleToPair <$> incidentEdgeTriples g v insertEdgeTriples es g = foldl' (flip insertEdgeTriple) g es insertEdgePair (v1, v2) = insertEdgeTriple (v1, v2, ()) insertEdgePairs es g = foldl' (flip insertEdgePair) g es removeVertices vs g = foldl' (flip removeVertex) g vs removeEdgePairs es g = foldl' (flip removeEdgePair) g es removeEdgePairAndVertices (v1, v2) g = removeVertex v2 $ removeVertex v1 $ removeEdgePair (v1, v2) g isolatedVertices g = filter (\ v -> vertexDegree g v == 0) $ vertices g fromList links = go links empty where go [] g = g go ((v, es) : rest) g = go rest $ foldr (\ (v', e) g' -> insertEdgeTriple (v, v', e) g') (insertVertex v g) es
- Data.Graph.Types: intersection :: Graph g => g v e -> g v e -> g v e
+ Data.Graph.Types: intersection :: (Graph g, Hashable v, Eq v, Eq e) => g v e -> g v e -> g v e
- Data.Graph.Types: union :: Graph g => g v e -> g v e -> g v e
+ Data.Graph.Types: union :: (Graph g, Hashable v, Eq v) => g v e -> g v e -> g v e
Files
- graphite.cabal +2/−1
- src/Data/Graph/DGraph.hs +9/−6
- src/Data/Graph/Types.hs +7/−9
- src/Data/Graph/UGraph.hs +9/−7
graphite.cabal view
@@ -1,5 +1,5 @@ name: graphite-version: 0.9.3.0+version: 0.9.4.0 synopsis: Graphs and networks library description: Represent, analyze and visualize graphs homepage: https://github.com/alx741/graphite#readme@@ -28,6 +28,7 @@ , Data.Graph.Visualize build-depends: base >= 4.7 && < 5 , QuickCheck+ , semigroups , bytestring , cassava , containers
src/Data/Graph/DGraph.hs view
@@ -4,7 +4,7 @@ module Data.Graph.DGraph where -import Data.List (foldl')+import Data.List (foldl', intersect) import Data.Semigroup import GHC.Generics (Generic) @@ -34,11 +34,11 @@ xs <- readPrec return (fromList xs) -instance (Hashable v) => Monoid (DGraph v e) where+instance (Hashable v, Eq v) => Monoid (DGraph v e) where mempty = empty mappend = union -instance (Hashable v) => Semigroup (DGraph v e) where+instance (Hashable v, Eq v) => Semigroup (DGraph v e) where (<>) = mappend instance (Hashable v, Eq v) => Functor (DGraph v) where@@ -110,9 +110,12 @@ where go bool v = bool && not (HM.member v $ getLinks v $ unDGraph g) - union = undefined- intersection = undefined- join = undefined+ union g1 g2 = insertArcs (toArcsList g1) $ insertVertices (vertices g1) g2++ intersection g1 g2 =+ insertVertices (isolatedVertices g1 `intersect` isolatedVertices g2) $+ fromArcsList (toArcsList g1 `intersect` toArcsList g2)+ toList (DGraph _ g) = zip vs $ fmap (\v -> HM.toList $ getLinks v g) vs
src/Data/Graph/Types.hs view
@@ -44,7 +44,7 @@ -- * Operations - -- | Retrieve the vertices of a graph+ -- | Retrieve all the vertices of a graph vertices :: g v e -> [v] -- | Retrieve the edges of a graph@@ -161,6 +161,10 @@ removeEdgePairAndVertices (v1, v2) g = removeVertex v2 $ removeVertex v1 $ removeEdgePair (v1, v2) g + -- | Retrieve the isolated vertices of a graph, if any+ isolatedVertices :: (Hashable v, Eq v) => g v e -> [v]+ isolatedVertices g = filter (\v -> vertexDegree g v == 0) $ vertices g+ -- | Tell if a graph is simple -- | A graph is @simple@ if it has no loops isSimple :: (Hashable v, Eq v) => g v e -> Bool@@ -169,16 +173,10 @@ -- * Binary operations -- | Union of two graphs- union :: g v e -> g v e -> g v e+ union :: (Hashable v, Eq v) => g v e -> g v e -> g v e -- | Intersection of two graphs- intersection :: g v e -> g v e -> g v e-- -- | Join two graphs- -- |- -- | The @join@ of two graphs G1 and G2 is a new graph where each vertex of- -- | G1 has an edge to all the vertices of G2- join :: g v e -> g v e -> g v e+ intersection :: (Hashable v, Eq v, Eq e) => g v e -> g v e -> g v e -- * Transformations
src/Data/Graph/UGraph.hs view
@@ -7,7 +7,7 @@ module Data.Graph.UGraph where import qualified Data.Foldable as F (toList)-import Data.List (foldl')+import Data.List (foldl', intersect) import Data.Semigroup import GHC.Generics (Generic) @@ -37,11 +37,11 @@ xs <- readPrec return (fromList xs) -instance (Hashable v) => Monoid (UGraph v e) where+instance (Hashable v, Eq v) => Monoid (UGraph v e) where mempty = empty mappend = union -instance (Hashable v) => Semigroup (UGraph v e) where+instance (Hashable v, Eq v) => Semigroup (UGraph v e) where (<>) = mappend instance (Hashable v, Eq v) => Functor (UGraph v) where@@ -105,10 +105,12 @@ where go bool v = bool && not (HM.member v $ getLinks v $ unUGraph g) - union = undefined- intersection = undefined- join = undefined+ union g1 g2 = insertEdges (toEdgesList g1) $ insertVertices (vertices g1) g2 + intersection g1 g2 =+ insertVertices (isolatedVertices g1 `intersect` isolatedVertices g2) $+ fromEdgesList (toEdgesList g1 `intersect` toEdgesList g2)+ toList (UGraph _ g) = zip vs $ fmap (\v -> HM.toList $ getLinks v g) vs where vs = HM.keys g @@ -194,7 +196,7 @@ prettyPrint :: (Hashable v, Eq v, Show v, Show e) => UGraph v e -> String prettyPrint g = "Isolated Vertices: "- <> show (filter (\v -> vertexDegree g v == 0) $ vertices g)+ <> show (isolatedVertices g) <> " " <> "Edges: " <> show (edges g)