IntGraph (empty) → 0.1.0.0

raw patch · 8 files changed

+240/−0 lines, 8 filesdep +IntGraphdep +basedep +containers

Dependencies added: IntGraph, base, containers

Files

• ChangeLog.md +3/−0
• IntGraph.cabal +56/−0
• LICENSE +30/−0
• README.md +1/−0
• src/Data/IntGraph.hs +47/−0
• src/Data/IntGraph/Directed.hs +49/−0
• src/Data/IntGraph/Undirected.hs +52/−0
• test/Spec.hs +2/−0

@@ -0,0 +1,3 @@+# Changelog for IntGraph++## Unreleased changes

@@ -0,0 +1,56 @@+-- This file has been generated from package.yaml by hpack version 0.20.0.+--+-- see: https://github.com/sol/hpack+--+-- hash: bf685344ee77315d99fcd243d23b7e410a495e791dfd796f1ce4c76491f45501++name:           IntGraph+version:        0.1.0.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+homepage:       https://github.com/sam-barr/IntGraph#readme+bug-reports:    https://github.com/sam-barr/IntGraph/issues+author:         Sam Barr+maintainer:     sbarr@oberlin.edu+copyright:      2018 Sam Barr+license:        BSD3+license-file:   LICENSE+build-type:     Simple+cabal-version:  >= 1.10++extra-source-files:+    ChangeLog.md+    README.md++source-repository head+  type: git+  location: https://github.com/sam-barr/IntGraph++library+  hs-source-dirs:+      src/+  build-depends:+      base >=4.7 && <5+    , containers+  exposed-modules:+      Data.IntGraph.Directed+      Data.IntGraph.Undirected+  other-modules:+      Data.IntGraph+      Paths_IntGraph+  default-language: Haskell2010++test-suite IntGraph-test+  type: exitcode-stdio-1.0+  main-is: Spec.hs+  hs-source-dirs:+      test+  ghc-options: -threaded -rtsopts -with-rtsopts=-N+  build-depends:+      IntGraph+    , base >=4.7 && <5+    , containers+  other-modules:+      Paths_IntGraph+  default-language: Haskell2010

@@ -0,0 +1,30 @@+Copyright Author name here (c) 2018++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Author name here nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,1 @@+# IntGraph

@@ -0,0 +1,47 @@+-- | Definition of an IntGraph+-- | Make sure to only import one of Directed and Undirected - there function names will conflict++module Data.IntGraph (+  Node,+  NodeSet,+  Edge,+  IntGraph(..),+  empty,+  addNode,+  nodes,+  removeNode)+  where++import qualified Data.IntMap.Strict as I+import           Data.IntMap.Strict    (IntMap)+import qualified Data.Set           as S+import           Data.Set              (Set)++-- | The nodes of the graph are Ints+type Node = Int++-- | A NodeSet is a Set of Nodes+type NodeSet = Set Node++-- | An edge is a pair of nodes+type Edge = (Node, Node)++-- | An IntGraph is a maping of Ints (Nodes) to sets of Nodes (Ints)+newtype IntGraph +  = IG (IntMap NodeSet)++-- | Adds a single node with no neighbors.+-- | If node already in graph, does nothing.+addNode :: Node -> IntGraph -> IntGraph+addNode node (IG graph) = IG $ I.insertWith S.union node S.empty graph++-- | Returns a list of the nodes in the graph+nodes :: IntGraph -> [Node]+nodes (IG graph) = I.keys graph++-- | removes a node and all its incident edges+removeNode :: Node -> IntGraph -> IntGraph+removeNode node (IG graph) = IG $ I.map (S.delete node) $ I.delete node graph++-- | the empty graph+empty = IG I.empty

@@ -0,0 +1,49 @@+-- | Functions for interacting with a graph as a directed graph++module Data.IntGraph.Directed (+  Node,+  NodeSet,+  Edge,+  IntGraph,+  empty,+  addNode,+  nodes,+  removeNode,+  addEdge,+  edges,+  removeEdge,+  fromEdges) +  where++import qualified Data.IntMap as I+import qualified Data.Set    as S++import Data.IntGraph++-- | Add an edge to the graph+-- | If either of the nodes are not already present in the graph,+-- | They are added.+addEdge :: Edge -> IntGraph -> IntGraph+addEdge (u, v) graph = IG $ I.adjust (S.insert v) u g'+  where+    (IG g') = addNode u $ addNode v graph+++-- | Turns a node with its adjecencies to a list of edges+adjacencyToList :: Node -> NodeSet -> [Edge]+adjacencyToList node neighbors = map ((,) node) $ S.elems neighbors+++-- | Returns a list of all edges in the graph+edges :: IntGraph -> [Edge]+edges (IG graph) = I.foldrWithKey f [] graph+  where+    f node neighbors rest = adjacencyToList node neighbors ++ rest++-- | Remove an edge from the graph+removeEdge :: Edge -> IntGraph -> IntGraph+removeEdge (u, v) (IG graph) = IG $ I.adjust (S.delete v) u graph++-- | Turns a list of edges into a graph+fromEdges :: [Edge] -> IntGraph+fromEdges graph = foldr addEdge empty graph

@@ -0,0 +1,52 @@+-- | Functions for interacting with a graph as an undirected graph++module Data.IntGraph.Undirected (+  Node,+  NodeSet,+  Edge,+  IntGraph,+  empty,+  addNode,+  nodes,+  removeNode,+  addEdge,+  edges,+  removeEdge,+  fromEdges)+  where++import qualified Data.IntMap as I+import qualified Data.Set    as S+import           Data.List   (delete)++import           Data.IntGraph+import qualified Data.IntGraph.Directed as D++-- | Add an edge to the graph+-- | If either nodes is not already in the graph, they are added+addEdge :: Edge -> IntGraph -> IntGraph+addEdge (u, v) graph = D.addEdge (u, v) $ D.addEdge (v, u) graph+++-- | Returns a list of all edges in the graph+edges :: IntGraph -> [Edge]+edges = D.edges+++-- Returns a list of all edges in the graph, without duplicate edges+-- i.e if (u,v) is an edge, only one of (u, v) or (v, u) will be in this list+edges' :: IntGraph -> [Edge]+edges' graph = filter' (edges graph)+  where+    filter' []          = []+    filter' ((u, v):xs) = (u, v) : (filter' $ delete (v, u) xs)+++-- | remove an edge from the graph+removeEdge :: Edge -> IntGraph -> IntGraph+removeEdge (u, v) graph = D.removeEdge (u, v) $ D.removeEdge (v, u) graph+++-- | turns a list of edges into a graph+fromEdges :: [Edge] -> IntGraph+fromEdges graph = foldr addEdge empty graph

@@ -0,0 +1,2 @@+main :: IO ()+main = putStrLn "Test suite not yet implemented"