Subgraphs

gistfile1.hs

-- Get all friends of the given one
group :: [(Int,Int)] -> [Int] -> Int -> [Int]
group [] acc x = acc
group l [] x = group l [x] x
group ((x1, x2):tl) acc x =
    case xx of (True, False) -> (group tl (x2 : (group tl (x2 : acc) x)) x2)
               (False, True) -> group tl (x1 : (group tl (x1 : acc) x)) x1
               otherwise -> group tl acc x
    where xx = (isin x1 x2, isin x2 x1)
          isin d p = not (p `elem` acc) && (d == x || d `elem` acc)

subnet :: Int -> [(Int,Int)] -> [[Int]] -- all subnets of the given network
subnet n pairs =
    let fs = [1 .. n] in
    let groupi = reverse . group pairs [] in
    map groupi fs

main = do
    let x = [(1, 3), (3, 5), (1, 4), (6, 7), (5, 2), (6, 1)]
    print x
    print $ subnet 7 x