graphene (empty) → 0.1.0.0

raw patch · 5 files changed

+206/−0 lines, 5 filesdep +basedep +bifunctorsdep +containerssetup-changed

Dependencies added: base, bifunctors, containers, hashable, lens-family, lens-family-core, mtl, transformers

Files

LICENSE +21/−0
Setup.hs +2/−0
graphene.cabal +64/−0
src/Graphene.hs +7/−0
src/Graphene/Graph.hs +112/−0

+ LICENSE view

@@ -0,0 +1,21 @@+MIT License (MIT)++Copyright (c) 2014 Benjamin Kovach++Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in+all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN+THE SOFTWARE.

+ Setup.hs view

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

+ graphene.cabal view

@@ -0,0 +1,64 @@+-- Initial graphene.cabal generated by cabal init.  For further +-- documentation, see http://haskell.org/cabal/users-guide/++-- The name of the package.+name:                graphene++-- The package version.  See the Haskell package versioning policy (PVP) +-- for standards guiding when and how versions should be incremented.+-- http://www.haskell.org/haskellwiki/Package_versioning_policy+-- PVP summary:      +-+------- breaking API changes+--                   | | +----- non-breaking API additions+--                   | | | +--- code changes with no API change+version:             0.1.0.0++-- A short (one-line) description of the package.+synopsis:            Graph Library built as a final project for a Graph Theory class++-- A longer description of the package.+-- description:         ++-- URL for the project homepage or repository.+homepage:            https://github.com/5outh/graphene++-- The license under which the package is released.+license: MIT             ++-- The file containing the license text.+license-file:        LICENSE++-- The package author(s).+author:              Benjamin Kovach++-- An email address to which users can send suggestions, bug reports, and +-- patches.+maintainer:          bkovach13@gmail.com++-- A copyright notice.+-- copyright:           ++category:            Data++build-type:          Simple++-- Constraint on the version of Cabal needed to build this package.+cabal-version:       >=1.8++library+  hs-source-dirs: src+  -- Modules exported by the library.+  exposed-modules: Graphene+                 , Graphene.Graph   +  +  -- Modules included in this library but not exported.+  -- other-modules:       +  +  -- Other library packages from which modules are imported.+  build-depends:  base ==4.6.*+                , lens-family ==1.0.0+                , lens-family-core ==1.0.*+                , transformers >=0.2.0 && <0.4+                , mtl == 2.1.*+                , bifunctors == 4.1.*+                , containers >=0.3 && <0.6+                , hashable == 1.1.2.*

+ src/Graphene.hs view

@@ -0,0 +1,7 @@+module Graphene where++import Graphene.Class+import Graphene.Graph+import Graphene.Instances()+import Graphene.Algorithms+import Graphene.IO

+ src/Graphene/Graph.hs view

@@ -0,0 +1,112 @@++{-# LANGUAGE BangPatterns, TemplateHaskell, NoMonomorphismRestriction #-}+module Graphene.Graph(+  Graph(..),+  emptyGraph,+  insertVertex,+  removeVertex,+  removeVertices,+  removeEdge,+  insertEdge,+  insertVertices,+  insertEdges,+  modifyVertex,+  modifyEdge,+  connections,+  neighbors,+  fromLists,+  degree,+  subgraph,+  moveFromTo,+  moveFromThrough,+  module Graphene.Class+) where++import Data.Hashable+import Data.List+import Data.Function+import Data.Maybe(catMaybes)+import Lens.Family2+import Data.Bifunctor+import Graphene.Class+import Graphene.Instances+++-- | Insert a vertex into a graph+insertVertex :: (Eq v) => v -> Graph e v -> Graph e v+insertVertex !v g@(Graph vs es) +  | v `elem` vs = g+  | otherwise   = Graph (v:vs) es++-- | Remove a vertex V from a graph+-- | (Also removes edges connected to V)+removeVertex :: Eq v => v -> Graph e v -> Graph e v+removeVertex !v g = vertices %~ (delete v) +  $ edges %~ (filter (\(_, (v1, v2)) -> not $ any (==v) [v1, v2])) $ g++-- | Remove a list of vertices from a graph+removeVertices :: Eq v => [v] -> Graph e v -> Graph e v+removeVertices vs g = foldl' (flip removeVertex) g vs++-- | Inset an edge into a graph connected to two vertices+insertEdge :: Eq v => e -> (v, v) -> Graph e v -> Graph e v +insertEdge !e !(v, v') (Graph vs es) = +  foldr insertVertex (Graph vs ((e, (v, v')):es)) [v, v']++-- | Remove an edge from a graph+removeEdge :: Eq e => e -> Graph e v -> Graph e v+removeEdge !e = edges %~ (deleteBy ((==) `on` fst) (e, undefined))++-- | Modify a vertex in a graph by an automorphism +-- | If such a vertex doesn't exist, modifyVertex = id+modifyVertex :: Eq v => (v -> v) -> v -> Graph e v -> Graph e v+modifyVertex f !v = second (\w -> if v == w then f v else v)++-- | Modify an edge in a graph by an automorphism+-- | If such an edge doesn't exist, modifyEdge = id+modifyEdge :: Eq e => (e -> e) -> e -> Graph e v -> Graph e v+modifyEdge f !e = first (\e' -> if e == e' then f e' else e')++-- | Insert a list of edges into a graph+insertVertices :: Eq b => [b] -> Graph e b -> Graph e b+insertVertices vs g = foldl' (flip insertVertex) g vs++-- | Insert a list of edges into a graph+insertEdges :: Eq v => [(e, v, v)] -> Graph e v -> Graph e v+insertEdges es g = foldl' (\g (e, v1, v2) -> insertEdge e (v1, v2) g) g es ++-- | find edge connections and vertex neighbors to a vertex+connections :: (Eq v) => v -> Graph e v -> [(e, v)]+connections !v (Graph _ es) = catMaybes $ +  map (\(e, (v1, v2)) -> +        if v == v1 then Just (e, v2) +          else if v == v2 then Just (e, v1) +            else Nothing) es++-- | find all vertices connected to a given vertex+neighbors :: Eq v => v -> Graph e v -> [v]+neighbors !v (Graph _ es) = foldl' f [] es+  where f acc (e, (v1, v2)) = if v == v2 then (v1:acc) else if v == v1 then (v2:acc) else acc++-- | Generate a graph froma list of edges and a list of edge / 2 vertex pairs+fromLists :: (Eq v) => [v] -> [(e, v, v)] -> Graph e v+fromLists vs es = insertEdges es $ insertVertices vs emptyGraph++-- | find the degree of a vertex+degree :: Eq v => v -> Graph e v -> Int+degree !v = length . connections v++-- | subgraph generated by a list of vertices+subgraph :: Eq v => [v] -> Graph e v -> Graph e v+subgraph ws (Graph vs es) = Graph vs' es'+  where vs' = filter (`elem` ws) vs+        es' = filter (\(e, (v1, v2)) -> all (`elem` ws) [v1, v2]) es++-- | move to a adjacent vertex (returns the next vertex if it really is connected)+moveFromTo :: Eq v => v -> v -> Graph e v -> Maybe v+moveFromTo v w g = if w `elem` ns then Just w else Nothing +  where ns = neighbors v g++-- | follow an edge to a new adjancent vertex (returns the new vertex)+moveFromThrough :: (Eq v, Eq e) => v -> e -> Graph e v -> Maybe v+moveFromThrough v e g = lookup e $ connections v g