graphite 0.3.0.0 → 0.4.0.0

raw patch · 5 files changed

+61/−29 lines, 5 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• graphite.cabal +1/−1
• src/Data/Graph/Connectivity.hs +25/−10
• src/Data/Graph/DGraph.hs +25/−8
• src/Data/Graph/UGraph.hs +7/−7
• test/Data/Graph/DGraphSpec.hs +3/−3

@@ -1,5 +1,5 @@ name:                graphite-version:             0.3.0.0+version:             0.4.0.0 synopsis:            Graphs and networks library description:         Represent, analyze and visualize graphs homepage:            https://github.com/alx741/graphite#readme

@@ -50,26 +50,41 @@ -- | Tell if a graph is connected -- | An Undirected Graph is @connected@ when there is a path between every pair -- | of vertices-isConnected :: (Hashable v, Eq v) => UGraph v e -> Bool-isConnected g = foldl' (\b v -> b && (not $ isIsolated g v)) True $ vertices g+isConnected :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> Bool+-- FIXME: Use a O(n) algorithm+isConnected g = go vs True+    where+        vs = vertices g+        go _ False = False+        go [] bool = bool+        go (v':vs') bool =+            go vs' $ foldl' (\b v -> b && areConnected g v v') bool vs +-- | Tell if a graph is bridgeless+-- | A graph is @bridgeless@ if it has no edges that, when removed, split the+-- | graph in two isolated components+isBridgeless :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool+-- FIXME: Use a O(n) algorithm+isBridgeless g =+    foldl' (\b vs -> b && isConnected (removeEdgePair g vs)) True (edgePairs g)++-- | Tell if a 'UGraph' is orietable+-- | An undirected graph is @orietable@ if it can be converted into a directed+-- | graph that is @strongly connected@ (See 'isStronglyConnected')+isOrientable :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool+isOrientable g = isConnected g && isBridgeless g+ -- | Tell if a 'DGraph' is weakly connected -- | A Directed Graph is @weakly connected@ if the underlying undirected graph -- | is @connected@-isWeaklyConnected :: (Hashable v, Eq v) => DGraph v e -> Bool+isWeaklyConnected :: (Hashable v, Eq v, Ord v) => DGraph v e -> Bool isWeaklyConnected = isConnected . toUndirected  -- | Tell if a 'DGraph' is strongly connected -- | A Directed Graph is @strongly connected@ if it contains a directed path -- | on every pair of vertices isStronglyConnected :: (Hashable v, Eq v, Ord v) => DGraph v e -> Bool-isStronglyConnected g = go vs True-    where-        vs = vertices g-        go _ False = False-        go [] bool = bool-        go (v':vs') bool =-            go vs' $ foldl' (\b v -> b && (areConnected g v v')) bool vs+isStronglyConnected g = isConnected g  -- TODO -- * connected component

@@ -38,14 +38,24 @@      containsEdgePair = containsArc'     incidentEdgePairs g v = fmap toPair $ incidentArcs g v-    insertEdgePair g (v1, v2) = insertArc (Arc v1 v2 ()) g+    insertEdgePair g (v1, v2) = insertArc g (Arc v1 v2 ())     removeEdgePair = removeArc'     removeEdgePairAndVertices = removeArcAndVertices'      isSimple = undefined     isRegular = undefined -    fromAdjacencyMatrix = undefined+    fromAdjacencyMatrix m+        | length m /= length (head m) = Nothing+        | otherwise = Just $ insertArcs empty (foldl' genArcs [] labeledM)+            where+                labeledM :: [(Int, [(Int, Int)])]+                labeledM = zip [1..] $ fmap (zip [1..]) m++                genArcs :: [Arc Int ()] -> (Int, [(Int, Int)]) -> [Arc Int ()]+                genArcs as (i, vs) = as ++ fmap (\v -> Arc i v ()) connected+                    where connected = fst <$> filter (\(_, v) -> v /= 0) vs+     toAdjacencyMatrix = undefined  -- | The Degree Sequence of a 'DGraph' is a list of pairs (Indegree, Outdegree)@@ -53,7 +63,7 @@  instance (Arbitrary v, Arbitrary e, Hashable v, Num v, Ord v)  => Arbitrary (DGraph v e) where-    arbitrary = insertArcs <$> arbitrary <*> pure empty+    arbitrary = insertArcs <$> pure empty <*> arbitrary  -- | @O(n)@ Remove a vertex from a 'DGraph' if present -- | Every 'Arc' incident to this vertex is also removed@@ -65,15 +75,15 @@ -- | @O(log n)@ Insert a directed 'Arc' into a 'DGraph' -- | The involved vertices are inserted if don't exist. If the graph already -- | contains the Arc, its attribute is updated-insertArc :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e-insertArc (Arc fromV toV edgeAttr) g = DGraph+insertArc :: (Hashable v, Eq v) => DGraph v e -> Arc v e -> DGraph v e+insertArc g (Arc fromV toV edgeAttr) = DGraph     $ HM.adjust (insertLink toV edgeAttr) fromV g'     where g' = unDGraph $ insertVertices g [fromV, toV]  -- | @O(m*log n)@ Insert many directed 'Arc's into a 'DGraph' -- | Same rules as 'insertArc' are applied-insertArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e-insertArcs as g = foldl' (flip insertArc) g as+insertArcs :: (Hashable v, Eq v) => DGraph v e -> [Arc v e] -> DGraph v e+insertArcs g as = foldl' insertArc g as  -- | @O(log n)@ Remove the directed 'Arc' from a 'DGraph' if present -- | The involved vertices are left untouched@@ -190,10 +200,17 @@ isInternal :: DGraph v e -> v -> Bool isInternal g v = not $ isSource g v || isSink g v +-- | Get the transpose of a 'DGraph'+-- | The @transpose@ of a directed graph is another directed graph where all of+-- | its arcs are reversed+transpose :: (Hashable v, Eq v) => DGraph v e -> DGraph v e+transpose g = insertArcs empty (fmap reverseArc $ arcs g)+    where reverseArc (Arc fromV toV attr) = Arc toV fromV attr+ -- | Convert a directed 'DGraph' to an undirected 'UGraph' by converting all of -- | its 'Arc's into 'Edge's toUndirected :: (Hashable v, Eq v) => DGraph v e -> UG.UGraph v e-toUndirected g = UG.insertEdges (fmap arcToEdge $ arcs g) empty+toUndirected g = UG.insertEdges empty (fmap arcToEdge $ arcs g)     where arcToEdge (Arc fromV toV attr) = Edge fromV toV attr  -- | Tell if a 'DegreeSequence' is a Directed Graphic

@@ -18,7 +18,7 @@  instance (Arbitrary v, Arbitrary e, Hashable v, Num v, Ord v)  => Arbitrary (UGraph v e) where-    arbitrary = insertEdges <$> arbitrary <*> pure empty+    arbitrary = insertEdges <$> pure empty <*> arbitrary  instance Graph UGraph where     empty = UGraph HM.empty@@ -36,7 +36,7 @@      containsEdgePair = containsEdge'     incidentEdgePairs g v = fmap toPair $ incidentEdges g v-    insertEdgePair g (v1, v2) = insertEdge (Edge v1 v2 ()) g+    insertEdgePair g (v1, v2) = insertEdge g (Edge v1 v2 ())     removeEdgePair = removeEdge'     removeEdgePairAndVertices = removeEdgeAndVertices' @@ -47,7 +47,7 @@      fromAdjacencyMatrix m         | length m /= length (head m) = Nothing-        | otherwise = Just $ insertEdges (foldl' genEdges [] labeledM) empty+        | otherwise = Just $ insertEdges empty (foldl' genEdges [] labeledM)             where                 labeledM :: [(Int, [(Int, Int)])]                 labeledM = zip [1..] $ fmap (zip [1..]) m@@ -70,16 +70,16 @@ -- | @O(log n)@ Insert an undirected 'Edge' into a 'UGraph' -- | The involved vertices are inserted if don't exist. If the graph already -- | contains the Edge, its attribute is updated-insertEdge :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e-insertEdge (Edge v1 v2 edgeAttr) g = UGraph $ link v2 v1 $ link v1 v2 g'+insertEdge :: (Hashable v, Eq v) => UGraph v e -> Edge v e -> UGraph v e+insertEdge g (Edge v1 v2 edgeAttr) = UGraph $ link v2 v1 $ link v1 v2 g'     where         g' = unUGraph $ insertVertices g [v1, v2]         link fromV toV = HM.adjust (insertLink toV edgeAttr) fromV  -- | @O(m*log n)@ Insert many directed 'Edge's into a 'UGraph' -- | Same rules as 'insertEdge' are applied-insertEdges :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e -> UGraph v e-insertEdges es g = foldl' (flip insertEdge) g es+insertEdges :: (Hashable v, Eq v) => UGraph v e -> [Edge v e] -> UGraph v e+insertEdges = foldl' insertEdge  -- | @O(log n)@ Remove the undirected 'Edge' from a 'UGraph' if present -- | The involved vertices are left untouched

@@ -16,8 +16,8 @@             containsVertex g' 1 `shouldBe` False          it "Can tell if an arc exists" $ property $ do-            let g = insertArc (1 --> 2) empty :: DGraph Int ()-            let g' = insertArc (2 --> 1) empty :: DGraph Int ()+            let g = insertArc empty (1 --> 2) :: DGraph Int ()+            let g' = insertArc empty (2 --> 1) :: DGraph Int ()             containsArc g (1 --> 2) `shouldBe` True             containsArc g' (1 --> 2) `shouldBe` False @@ -26,7 +26,7 @@                 ==> order g + 1 == order (insertVertex (g :: DGraph Int ()) v)         it "Increments its size when a new arc is inserted" $ property $             \g arc -> (not $ g `containsArc` arc)-                ==> size g + 1 == size (insertArc arc (g :: DGraph Int ()))+                ==> size g + 1 == size (insertArc (g :: DGraph Int ()) arc)          it "Is id when inserting and removing a new vertex" $ property $             \g v -> (not $ g `containsVertex` v)