graph-visit (empty) → 0.1

raw patch · 4 files changed

+97/−0 lines, 4 filesdep +basedep +containersdep +data-lenssetup-changed

Dependencies added: base, containers, data-lens, data-lens-template, mtl

Files

• LICENSE +1/−0
• Setup.hs +2/−0
• graph-visit.cabal +30/−0
• src/Data/Graph/GraphVisit.hs +64/−0

@@ -0,0 +1,1 @@+BSD3

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

@@ -0,0 +1,30 @@+Name:				graph-visit+Version:			0.1+cabal-version:      >= 1.6+License:			BSD3+license-file:		LICENSE+Copyright:			Utrecht University, Department of Information and Computing Sciences, Software Technology group+Build-Type:		    Simple+Author:				Atze Dijkstra+Maintainer:         atze@uu.nl+Homepage:           https://github.com/atzedijkstra/graph-visit+Bug-Reports:        https://github.com/atzedijkstra/graph-visit/issues+Category:			Development+Synopsis:			Graph walk abstraction+Description:        Walk over a graph, abstracting away from the underlying representation, not caring about precise order+source-repository head+  type:        git+  location:    git://github.com/atzedijkstra/graph-visit.git++library+  Build-Depends:+    base >= 4 && < 5,+    data-lens >= 2 && < 3,+    data-lens-template >= 2 && < 3,+    mtl >= 2 && < 3,+    containers >= 0.4 && < 0.5+  Exposed-Modules:		Data.Graph.GraphVisit+  Ghc-Options:		+  HS-Source-Dirs:     	src+  Build-Tools:		+  Extensions:			

@@ -0,0 +1,64 @@+{-# LANGUAGE TemplateHaskell, NoMonomorphismRestriction #-}++------------------------------------------------------------------------------+-- | This module provides a graph visiting abstraction+module Data.Graph.GraphVisit+  ( +    -- * Graph visiting+    graphVisitM+  , graphVisit+  )+  where++------------------------------------------------------------------------------+import qualified Data.Set as Set+import           Control.Monad.State.Strict+import           Data.Lens.Common+import           Data.Lens.Strict+import           Data.Lens.Template+------------------------------------------------------------------------------+------------------------------------------------------------------------------++------------------------------------------------------------------------------+-- | The state employed by visiting+data GraphVisitState node thr = GraphVisitState+  { _gvsVisited		:: Set.Set node		-- ^ visited nodes+  , _gvsYetToVisit	:: Set.Set node		-- ^ to be visited nodes+  , _gvsAccum		:: thr				-- ^ threaded accumulator+  }++makeLens ''GraphVisitState++------------------------------------------------------------------------------+-- | Abstract graph visit, over arbitrary structures, using state holding visited nodes (also acting als start) and an accumulator 'thr'.+-- All is done in strict StateT.+graphVisitM+  :: (Ord node, Monad m)+     => (thr -> graph -> node -> (thr,Set.Set node))      -- ^ fun: visit node, get new thr and nodes to visit next+     -> graph                                               -- ^ graph over which we visit+     -> StateT (GraphVisitState node thr) m ()+graphVisitM visit graph+  = v+  where v = do+          s <- get+          unless (Set.null $ s ^. gvsYetToVisit) $ do+            let (n, unvisited) 		= Set.deleteFindMin $ s ^. gvsYetToVisit+                (thr, newUnvisited) = visit (s ^. gvsAccum) graph n+                newAndOldVisited 	= Set.insert n $ s ^. gvsVisited+            gvsVisited != newAndOldVisited+            gvsYetToVisit != Set.union (newUnvisited `Set.difference` newAndOldVisited) unvisited+            gvsAccum != thr+            v++------------------------------------------------------------------------------+-- | Abstract graph visit, running graphVisitM+graphVisit+  :: (Ord node)+     => (thr -> graph -> node -> (thr,Set.Set node))        -- ^ fun: visit node, get new thr and nodes to visit next+     -> Set.Set node                                        -- ^ root/start+     -> graph                                               -- ^ graph over which we visit+     -> thr                                                 -- ^ the accumulator, threaded as state+     -> (thr,Set.Set node)                                  -- ^ yield accum and visited+graphVisit visit start graph thr+  = (s ^. gvsAccum, s ^. gvsVisited)+  where s = execState (graphVisitM visit graph) (GraphVisitState Set.empty start thr)