haskell - Haskell中的全套子图

Question

我面临着生成任何长度有限的图的全套子图的问题。图表示为有序对的列表，例如：

让 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)]

一种方法是获取其中对有界的所有子序列，但标准函数子序列会生成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)]

我们可以通过以下代码获取所有子图：

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