How to reverse a graph in haskell?

Question

for an exercise I need to reverse a graph (reverse all edges), but I don't get anywhere. So I need some help.

I am aware you might not want to solve the exercise for me, so that's not what I am asking for. I just need to get some advice...

So to get to it:

data Graph a = G
  { nodes :: [a]
  , successors :: a -> [a] }

reverseGraph :: Eq a => Graph a -> Graph a

A graph has to parameters: a list of nodes and a function that defines the successors. This function has the type: a -> [a]

for example:

graph1 :: Graph Int
graph1 = G [1..6] $ \case   1 -> [2,3]
                            2 -> []
                            3 -> [1,4,6]
                            4 -> [1]
                            5 -> [3,5]
                            6 -> [2,4,5]

the reversed graph would be:

reverseGraph graph1 ~>
    2 -> [1,6]
    3 -> [1,5]
    1 -> [3,4]
    4 -> [3,6]
    6 -> [3]
    5 -> [5,6]

I get that I need to check for each node in the input graph the successors and add for each the input node to the new successor list of the output node.

But i just don't get how to do this in Haskell.

Any help is appreciated!

Here is my solution for anyone who may attempt something similar:

reverseGraph :: Eq a => Graph a -> Graph a
reverseGraph (G nodes sucs) =  (G nodes sucs') where 
    sucs' a = getVert a nodes sucs

--Makes a list of all occurrences of v in the succeccor list.
getVert :: Eq a => a -> [a] -> (a-> [a]) -> [a]
getVert v [] succs = []
getVert v (n:ns) succs = if v `elem` succs n then [n]++getVert v ns succs else getVert v ns succs

If it would be oo-programming i would do it something like that: foreach x in nodes do foreach s in sucs x do if exists s in sucs' add x to sucs' s else add s -> [x] to sucs' but i dont get how to do it in functional programming — Dortmunder
– Dortmunder, Commented Dec 21, 2018 at 12:41
You'll need to actually call the function on each node to find out what the edges really are. This isn't a good representation for a graph whose edges you want to reverse. — chepner
– chepner, Commented Dec 21, 2018 at 13:08
Well, thats what i have. I would also prefer something different. — Dortmunder
– Dortmunder, Commented Dec 21, 2018 at 13:12
I think it's important to mention that the type of reverseGraph, namely the fact that it has only an Eq a constraint, forces you to use a very inefficient implementation. If you had a constraint of Ord a or (Eq a, Hashable a), then you could do considerably better. — dfeuer
– dfeuer, Commented Dec 21, 2018 at 18:44

chi · Accepted Answer · 2018-12-21 13:16:04Z

5

Here's a hint. Let's consider the reverse of G vertices edges. That will be of the form G vertices' edges'.

It's obvious that vertices' = vertices.

What about edges'? Well, for any value v, edges' v must return

"the list of all the w in vertices such that edge w contains v as an element"

You can translate the above English description into Haskell code using a list comprehension. You can use x `elem` list to check whether x is an element of list.

answered Dec 21, 2018 at 13:16

chi

117k4 gold badges143 silver badges230 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Dortmunder Over a year ago

That helped me very much! Thank you!

Collectives™ on Stack Overflow

How to reverse a graph in haskell?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related