IntGraph 0.1.0.0 → 0.1.1.0

raw patch · 7 files changed

+118/−12 lines, 7 filessetup-changedPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• IntGraph.cabal +4/−2
• Setup.hs +2/−0
• src/Data/IntGraph.hs +36/−6
• src/Data/IntGraph/Directed.hs +6/−2
• src/Data/IntGraph/Directed/Algorithms.hs +32/−0
• src/Data/IntGraph/Undirected.hs +6/−2
• src/Data/IntGraph/Undirected/Algorithms.hs +32/−0

@@ -2,10 +2,10 @@ -- -- see: https://github.com/sol/hpack ----- hash: bf685344ee77315d99fcd243d23b7e410a495e791dfd796f1ce4c76491f45501+-- hash: c91eea0f55615780e544e99395b8d3f7208a7f28ccd97490f760ea25f3b12017  name:           IntGraph-version:        0.1.0.0+version:        0.1.1.0 synopsis:       Dynamically sized graph library description:    Graph implemented as an IntMap to Sets of Ints. Functions for Directed and Undirected graphs are provided. category:       Data structure@@ -35,7 +35,9 @@     , containers   exposed-modules:       Data.IntGraph.Directed+      Data.IntGraph.Directed.Algorithms       Data.IntGraph.Undirected+      Data.IntGraph.Undirected.Algorithms   other-modules:       Data.IntGraph       Paths_IntGraph

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -9,19 +9,26 @@   empty,   addNode,   nodes,-  removeNode)+  removeNode,+  null,+  nullEdges)   where +import Prelude hiding (null)+ import qualified Data.IntMap.Strict as I-import           Data.IntMap.Strict    (IntMap)-import qualified Data.Set           as S-import           Data.Set              (Set)+import           Data.IntMap.Strict (IntMap)+import qualified Data.IntSet        as S+import           Data.IntSet        (IntSet) +import Data.Semigroup+import Data.Monoid+ -- | The nodes of the graph are Ints type Node = Int --- | A NodeSet is a Set of Nodes-type NodeSet = Set Node+-- | A NodeSet is a IntSet of Nodes+type NodeSet = IntSet  -- | An edge is a pair of nodes type Edge = (Node, Node)@@ -45,3 +52,26 @@  -- | the empty graph empty = IG I.empty++-- | Is the graph empty+null :: IntGraph -> Bool+null (IG graph) = I.null graph++-- | Is the edge set empty+nullEdges :: IntGraph -> Bool+nullEdges (IG graph) = I.null $ I.filter (not . S.null) graph++-- | Joins to graphs by unioning the vertex and edge sets+overlay :: IntGraph -> IntGraph -> IntGraph+overlay (IG g1) (IG g2) = IG $ I.unionWith (S.union) g1 g2++instance Eq IntGraph where+  (IG g1) == (IG g2) = g1 == g2++instance Semigroup IntGraph where+  (<>) = overlay++instance Monoid IntGraph where+  mempty = empty++  mappend = overlay

@@ -12,11 +12,15 @@   addEdge,   edges,   removeEdge,-  fromEdges) +  fromEdges,+  null,+  nullEdges)    where +import Prelude hiding (null)+ import qualified Data.IntMap as I-import qualified Data.Set    as S+import qualified Data.IntSet as S  import Data.IntGraph 

@@ -0,0 +1,32 @@+module Data.IntGraph.Directed.Algorithms where++import Prelude hiding (null)++import Control.Applicative ((<|>))+import Data.Maybe (isJust, fromJust)++import Data.IntGraph.Directed+++-- | If there is a vertex cover of size k, returns the vertex cover+-- | Otherwise Nothing+-- | O(n*2^k)+vertexCoverDec :: IntGraph -> Int -> Maybe [Node]+vertexCoverDec graph k+  | nullEdges graph = Just []+  | k == 0 = Nothing+  | otherwise = uCover <|> vCover+  where+    (u, v) = head $ edges graph+    uCover = (u :) <$> vertexCoverDec (removeNode u graph) (k - 1)+    vCover = (v :) <$> vertexCoverDec (removeNode v graph) (k - 1)++-- | vertexCoverDec, but just returns true or false+vertexCoverBool :: IntGraph -> Int -> Bool+vertexCoverBool = (isJust .) . vertexCoverDec++-- | Optimal vertex cover+-- | Not all that efficient, just keeps trying difference values for k+vertexCover :: IntGraph -> [Node]+vertexCover graph = let f k = vertexCoverDec graph k <|> f (k + 1)+                     in fromJust $ f 0

@@ -12,11 +12,15 @@   addEdge,   edges,   removeEdge,-  fromEdges)+  fromEdges,+  null,+  nullEdges)   where +import Prelude hiding (null)+ import qualified Data.IntMap as I-import qualified Data.Set    as S+import qualified Data.IntSet as S import           Data.List   (delete)  import           Data.IntGraph

@@ -0,0 +1,32 @@+module Data.IntGraph.Undirected.Algorithms where++import Prelude hiding (null)++import Control.Applicative ((<|>))+import Data.Maybe (isJust, fromJust)++import Data.IntGraph.Undirected+++-- | If there is a vertex cover of size k, returns the vertex cover+-- | Otherwise Nothing+-- | O(n*2^k)+vertexCoverDec :: IntGraph -> Int -> Maybe [Node]+vertexCoverDec graph k+  | nullEdges graph = Just []+  | k == 0 = Nothing+  | otherwise = uCover <|> vCover+  where+    (u, v) = head $ edges graph+    uCover = (u :) <$> vertexCoverDec (removeNode u graph) (k - 1)+    vCover = (v :) <$> vertexCoverDec (removeNode v graph) (k - 1)++-- | vertexCoverDec, but just returns true or false+vertexCoverBool :: IntGraph -> Int -> Bool+vertexCoverBool = (isJust .) . vertexCoverDec++-- | Optimal vertex cover+-- | Not all that efficient, just keeps trying difference values for k+vertexCover :: IntGraph -> [Node]+vertexCover graph = let f k = vertexCoverDec graph k <|> f (k + 1)+                     in fromJust $ f 0