Reachable nodes in a graph-CodePudding

I want to check from which nodes a node is reachable.

So I want to give a graph and node and return a list of all nodes where I can reach the graph from. (I know there is Data.Graph, but I want to try to understand it from scratch, and don't use it on purpose.

To build up the graph I got the following Data.

data Node = Node String [Node]

The String is just a representation of a name the node has.

Which is the representaion of the graph.

node1 = Node "node1" [node2,node3]
node2 = Node "node2" [node3]
node3 = Node "node3" [node4,node5]
node4 = Node "node4" [node1,node2]
node5 = Node "node5" [node4]

Also I got the (directly) reaching Nodes in:

canReachNext (Node x y) = y

Now my basic idea was this:

listForReachables:: Node n => n -> [n]
listForReachables x
    | contains[x] (canReachNext x) == False = listForReachables (head(canReachNext (x)))
    | contains [x] (canReachNext x)== True = [x]
    | otherwise = []

This ends in an endless Loop if I run

listForReachables node1

I get the reason why it ends in a loop. Because in this example the head will always have an other list.

My problem and where I am stuck is, that im used to the OOP and in this case it feels like I need a list to remember which nodes I've checked, and which nodes I still have to check.

CodePudding user response：

In Haskell, it is common for one function with the desired type to call another one with many parameters. You can use these to capture the intermediate state.

In this case, I added a list of nodes already visited. The first parameter is a list of nodes to explore. When the program encounters a node that has already passed, it discards it and continues with other nodes from the first parameter.

Your exit condition can't occur because the Bool has only the True and the False values. These no longer need to be compared.

I had a problem that the standard classes Show and Eq hung when applied to node1, so I made an incomplete contains and name for myself.

If you have a problem with cycling, be sure to check that show node1 and contains are fine. Alternatively, make a non-cyclic test chart.

node6 = Node "node6" [node7]
node7 = Node "node7" []

Code:

data Node = Node String [Node]

node1 = Node "node1" [node2,node3]
node2 = Node "node2" [node3]
node3 = Node "node3" [node4,node5]
node4 = Node "node4" [node1,node2]
node5 = Node "node5" [node4]

canReachNext :: Node -> [Node]
canReachNext (Node x y) = y

name :: Node -> String
name (Node x y) = x

contains :: [Node] -> [Node] -> Bool
contains (x:xs) ys = any ((\(Node a b) -> \(Node c d) ->  a == c) x) ys

listForReachables :: Node -> [Node]
listForReachables x = listForReachables' (x:[]) []

listForReachables' :: [Node] -> [Node] -> [Node]
listForReachables' (x:xs) ys
    | contains [x] ys  = listForReachables' xs ys
    | otherwise = listForReachables' (xs    canReachNext x) (x:ys)
listForReachables' [] ys = ys

Test:

map name $ listForReachables node1

Output:

["node5","node4","node3","node2","node1"]

Note 1.: There is convention to name a helper function "go".

listForReachables :: Node -> [Node]
listForReachables x = go (x:[]) [] where
 go (x:xs) ys
    | contains [x] ys  = go xs ys
    | otherwise = go (xs    canReachNext x) (x:ys)
 go [] ys = ys

CodePudding user response：

it feels like I need a list to remember which nodes I've checked, and which nodes I still have to check.

I agree. So let's use one!

listForReachables :: Node -> [String] -> ([String], [Node])
listForReachables node@(Node src tgts) visited
    | src `elem` visited = (visited, [])
    | otherwise = loopOver tgts (src:visited)
    where
    loopOver [] visited = (visited, [node])
    loopOver (tgt:tgts) visited = let
        (visited', reachables) = listForReachables tgt visited'
        (visited'', reachables') = loopOver tgts visited'
        in (visited'', reachables    reachables')

Actually, an experienced Haskeller would notice this pattern:

(visited', reachables) = listForReachables tgt visited'
(visited'', reachables') = loopOver tgts visited'

and realize that this was exactly the implementation of (>>=) for the State [String] monad. So they would probably change the implementation this way:

listForReachables :: Node -> State [String] [Node]
listForReachables node@(Node src tgts) = do
    done <- gets (src `elem`)
    if done then pure [] else do
        modify (src:)
        reachables <- mapM listForReachables tgts
        pure (node : concat reachables)

Pretty compact! Let's try it:

> name (Node nm _) = nm
> map name (evalState (listForReachables node1) [])
["node1","node2","node3","node4","node5"]