I need to find the connected components of a graph given its edges.

The graph edges are represented as a list of tuples, and the result needs to be a list of lists of vertices representing the connected components, eg [(1,2), (2,3), (2,6), (5,6) (6,7), (8,9), (9,10)] -> [[1,2,3,5,6,7], [8,9,10]]. There could be any number of connected edges and unconnected graph components in the list. The tuples will always be in ascending order though, if that helps.

I have the signature groupEdges :: [(Int, Int)] -> [[Int]] but I just can't think of how to get from tuples to lists.

I thought of taking one tuple at a time and searching the rest for matching elements, but I don't know how to make this list of sublists.

This question is similar to this question on the CS Stack Exchange, but I don't want to use Data.Graph. I would like to do this without other packages if possible.

-- edit - comments from chepner and ThibautM have given me the first step. I can convert from tuples to lists by calling the function with groupEdges map (\(x,y) -> [x,y]) pairs.

Now I need to take this list of lists and group the connected components eg. [[1,2], [2,3], [2,6], [5,6], [6,7], [8,9], [9,10]] -> [[1,2,3,5,6,7], [8,9,10]]

CodePudding user response：

You mentioned not using packages. The 4 functions I used are relatively easy to implement yourself if you really want. (And I encourage you to either do so or at least lookup their implementation)

Lists are used as set, which is a lot worse in performance than using a dedicated structure e.g. Data.Set. Using a disjoint-set (union-find, merge-find) data structure (referenced in your linked answer) would be even better, but probably not very good as a starting point for understanding

import Data.List (elem, intersect, union, partition)

pairs = [(1,2), (2,3), (2,6), (5,6), (6,7), (8,9), (9,10)]
pairs2 = map (\(x,y) -> [x,y]) pairs

-- add item to list, only if its no already present - using list as set
addItem item list | elem item list = list
                  | otherwise      = item : list

-- used to test whether subgraphs are connected i.e. contain common node
intersects a b = not $ null $ intersect a b

unionAll :: (Eq a) => [[a]] -> [a]
unionAll (x1:x2:xs) = unionAll ((union x1 x2):xs)
unionAll [x] = x
unionAll [] = []

-- find edges that are connected to first edge/subgraph and merge them
groupFirst :: (Eq a) => [[a]] -> [[a]]
groupFirst (x:xs) = (unionAll (x:connected)) : disconnected
    where
-- separate 'xs' edges/subgraphs into those that are connected to 'x' and the rest
      (connected, disconnected) = partition (intersects x) xs
groupFirst [] = []

-- if no more edges/subgraphs can be connected with first edge, continue with remaining (disconnected) edge/subgraph ([5,6] in second iteration)
groupAll :: (Eq a) => [[a]] -> [[a]]
groupAll (x:xs) = y:(groupAll ys)
    where
      (y:ys) = groupFirst (x:xs)
groupAll [] = []

-- after first 'groupAll pairs2' - [[1,2,3,6],[5,6,7],[8,9,10]]

-- repeat this process until no more components can be connected together
groupAllRepeat x = if x /= groupAll x then groupAllRepeat (groupAll x) else x

main = print (groupAllRepeat pairs2)