Reachable nodes in a graph

Question

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.

That is not a good data representation to solve that problem in Haskell. — Joseph Sible-Reinstate Monica, Dec 04 '21 at 23:25
@JosephSible-ReinstateMonica Why not? Obviously an adjacency map is popular because it's easier to build, but if you can build a given graph using this representation it seems perfectly possible to run graph algorithms on it. — amalloy, Dec 05 '21 at 00:32
@amalloy I didn't say it was impossible, just that it wasn't good. The main thing I don't like is that it fails "make illegal states unrepresentable" since you could have a graph with two nodes with the same label. To me, this data structure seems like it's meant for a language that has reference equality, which Haskell doesn't*. — Joseph Sible-Reinstate Monica, Dec 05 '21 at 01:36
* yeah yeah `reallyUnsafePtrEquality#`..., but please don't. — Joseph Sible-Reinstate Monica, Dec 05 '21 at 01:37

David Lukas · Accepted Answer · 2021-12-05T12:20:51.717

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

score 1 · Answer 2 · answered Dec 05 '21 at 14:11

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"]

Reachable nodes in a graph

2 Answers2