License	BSD-3-Clause
Safe Haskell	None
Language	Haskell2010

Swarm.Util.Graph

Description

Graph utilities shared by multiple aspects of scenarios

Synopsis

isAcyclicGraph :: [SCC a] -> Bool
findCycle :: Ord key => [(a, key, [key])] -> Maybe [a]
failOnCyclicGraph :: Ord key => Text -> (a -> Text) -> [(a, key, [key])] -> Either Text ()

Documentation

isAcyclicGraph :: [SCC a] -> Bool Source #

findCycle :: Ord key => [(a, key, [key])] -> Maybe [a] Source #

Find a cycle in a directed graph (if any exist) via DFS.

>>> findCycle [("a", 0, [0])]
Just ["a"]
>>> findCycle [("a", 0, [1]), ("b", 1, [])]
Nothing
>>> findCycle [("a", 0, [1]), ("b", 1, [0])]
Just ["a","b"]
>>> findCycle [("a", 0, [1]), ("b", 1, [2]), ("c", 2, [1])]
Just ["b","c"]
>>> findCycle [("a",3,[1]), ("b",1,[0,3]), ("c",2,[1]), ("d",0,[])]
Just ["b","a"]
>>> findCycle [("a",3,[]), ("b",1,[0,3]), ("c",2,[1]), ("d",0,[])]
Nothing
>>> findCycle [("a",3,[1]), ("b",1,[0,3]), ("c",2,[1]), ("d",0,[2])]
Just ["d","c","b"]

failOnCyclicGraph :: Ord key => Text -> (a -> Text) -> [(a, key, [key])] -> Either Text () Source #