Полный набор подграфов в Haskell

Question

Я столкнулся с проблемой генерации полного набора подграфов любого графика с ограниченной длиной. Графики представлены в виде списков упорядоченных пар, например:

0 = 0 (0)), (3,5), (4,6), (5,6), (7,8), (8,10), (8,9), (10,12), (10,11) , (11,13), (12,14), (13,15), (14,15)]

Один из способов становится все подпоследовательности, в котором пары ограничены, но стандартные функции подпоследовательности генерирует 2^n, при этом больше этих вариантов не ограничены, поэтому представляют собой несвязанные подграфы.

Answer 1

Я нашел способ, пусть мы имеем граф

let g = [(1,2),(1,7),(1,3),(2,9),(2,4),(3,5),(4,6),(5,6), (7,8),(8,10),(8,9),(10,12),(10,11),(11,13),(12,14),(13,15),(14,15)] 

Мы можем получить все subgraps этим кодом:

subgraphs g = nub $ subgraphs' g 

subgraphs' [] = [[]] 
subgraphs' (x:xz) = subgraphs xz ++ map (contact x) (subgraphs xz) 

contact (i,j) [] = [(i,j)] 
contact (i,j) set = if ([i] ++ [j]) `intersect` ((\(f,g) -> f ++ g) $ unzip set) /= [] then ([(i,j)] ++ set) else set 

Попробуй:

*Main> length $ subgraphs g 
164