生成所有唯一的有向图,每个节点有 2 个输入
Generate all unique directed graphs with 2 inputs to each node
我正在尝试生成符合规范的所有唯一二合字母:
- 每个节点必须恰好有 2 个输入
- 并允许任意多个输出到图中的其他节点
我目前的解决方案很慢。例如,对于 6 个节点,该算法需要 1.5 天才能到达我认为 的位置,但它可能还要再检查几天。
我对具有 n
个节点的图的算法:
生成 0
的所有 n
长度字符串,其中一个符号是 1
,例如,对于 n=3,[[0,0,1], [0,1,0], [1,0,0]]
.这些可以被认为是单位矩阵中的行。
生成所有可能的 n * n
矩阵,其中每一行都是 step 1. + step 1.
的所有可能组合
这是连接矩阵,其中每个单元格代表从 column-index
到 row-index
的连接
因此,对于 n=3,这些是可能的:
[0,1,0] + [1,0,0] = [1,1,0]
[1,0,0] + [1,0,0] = [2,0,0]
这些表示节点的输入,通过将步骤 1 添加到自身,结果将始终表示 2 个输入。
例如:
A B C
A' [[0,1,1],
B' [0,2,0],
C' [1,1,0]]
因此 B
和 C
分别连接到 A
一次:B -> A', C -> A'
、
并且 B
连接到自身两次:B => B'
- 我只想要唯一的,所以对于生成的每个连接矩阵,如果它与已经看到的图不同构,我只能保留它。
这一步很昂贵。我需要通过同构图的每个排列将图转换为 运行 的 "canonical form",对它们进行排序,并将第一个视为 "canonical form"。
如果有人深入测试其中的任何一个,这里是 n
个节点的独特图表的计数:
2 - 6
3 - 44
4 - 475
5 - 6874
6 - 109,934 (I think, it's not done running yet but I haven't found a new graph in >24 hrs.)
7 - I really wanna know!
可能的优化:
既然我要生成要测试的图表,有没有办法在不测试的情况下将它们排除在外,因为它们与已经看到的图表同构?
有没有更快的图同构算法? 我认为这个与 "Nauty" 相关, 还有其他我在论文中读到的,但我没有实现它们的专业知识(或带宽)还.
这是一个可演示的连接矩阵,可以在 graphonline.ru 处绘制以示乐趣,显示自连接以及到同一节点的 2 个连接:
1, 0, 0, 0, 0, 1,
1, 0, 0, 0, 1, 0,
0, 1, 0, 1, 0, 0,
0, 1, 2, 0, 0, 0,
0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 1, 0,
这里是 haskell 中的代码,如果你想玩的话,但我更关心的是算法是否正确(例如,减少搜索 space),而不是实现:
-- | generate all permutations of length n given symbols from xs
npermutations :: [a] -> Int -> [[a]]
npermutations xs size = mapM (const xs) [1..size]
identity :: Int -> [[Int]]
identity size = scanl
(\xs _ -> take size $ 0 : xs) -- keep shifting right
(1 : (take (size - 1) (repeat 0))) -- initial, [1,0,0,...]
[1 .. size-1] -- correct size
-- | return all possible pairings of [Column]
columnPairs :: [[a]] -> [([a], [a])]
columnPairs xs = (map (\x y -> (x,y)) xs)
<*> xs
-- | remove duplicates
rmdups :: Ord a => [a] -> [a]
rmdups = rmdups' Set.empty where
rmdups' _ [] = []
rmdups' a (b : c) = if Set.member b a
then rmdups' a c
else b : rmdups' (Set.insert b a) c
-- | all possible patterns for inputting 2 things into one node.
-- eg [0,1,1] means cells B, and C project into some node
-- [0,2,0] means cell B projects twice into one node
binaryInputs :: Int -> [[Int]]
binaryInputs size = rmdups $ map -- rmdups because [1,0]+[0,1] is same as flipped
(\(x,y) -> zipWith (+) x y)
(columnPairs $ identity size)
transposeAdjMat :: [[Int]] -> [[Int]]
transposeAdjMat ([]:_) = []
transposeAdjMat m = (map head m) : transposeAdjMat (map tail m)
-- | AdjMap [(name, inbounds)]
data AdjMap a = AdjMap [(a, [a])] deriving (Show, Eq)
addAdjColToMap :: Int -- index
-> [Int] -- inbound
-> AdjMap Int
-> AdjMap Int
addAdjColToMap ix col (AdjMap xs) =
let conns = foldl (\c (cnt, i) -> case cnt of
1 -> i:c
2 -> i:i:c
_ -> c
)
[]
(zip col [0..]) in
AdjMap ((ix, conns) : xs)
adjMatToMap :: [[Int]] -> AdjMap Int
adjMatToMap cols = foldl
(\adjMap@(AdjMap nodes) col -> addAdjColToMap (length nodes) col adjMap)
(AdjMap [])
cols
-- | a graph's canonical form : http://mfukar.github.io/2015/09/30/haskellxiii.html
-- very expensive algo, of course
canon :: (Ord a, Enum a, Show a) => AdjMap a -> String
canon (AdjMap g) = minimum $ map f $ Data.List.permutations [1..(length g)]
where
-- Graph vertices:
vs = map fst g
-- Find, via brute force on all possible orderings (permutations) of vs,
-- a mapping of vs to [1..(length g)] which is minimal.
-- For example, map [1, 5, 6, 7] to [1, 2, 3, 4].
-- Minimal is defined lexicographically, since `f` returns strings:
f p = let n = zip vs p
in (show [(snd x, sort id $ map (\x -> snd $ head $ snd $ break ((==) x . fst) n)
$ snd $ take_edge g x)
| x <- sort snd n])
-- Sort elements of N in ascending order of (map f N):
sort f n = foldr (\x xs -> let (lt, gt) = break ((<) (f x) . f) xs
in lt ++ [x] ++ gt) [] n
-- Get the first entry from the adjacency list G that starts from the given node X
-- (actually, the vertex is the first entry of the pair, hence `(fst x)`):
take_edge g x = head $ dropWhile ((/=) (fst x) . fst) g
-- | all possible matrixes where each node has 2 inputs and arbitrary outs
binaryMatrixes :: Int -> [[[Int]]]
binaryMatrixes size = let columns = binaryInputs size
unfiltered = mapM (const columns) [1..size] in
fst $ foldl'
(\(keep, seen) x -> let can = canon . adjMatToMap $ x in
(if Set.member can seen
then keep
else id $! x : keep
, Set.insert can seen))
([], Set.fromList [])
unfiltered
您可以尝试多种方法。我确实注意到的一件事是,具有多边循环(彩色循环?)有点不寻常,但可能只需要改进现有技术。
过滤另一个程序的输出
这里明显的候选者当然是 nAUTy/traces (http://pallini.di.uniroma1.it/) 或类似的(saucy、bliss 等)。取决于你想如何做到这一点,它可以像 运行 nauty(例如)一样简单并输出到文件,然后在你去的时候读入列表过滤。
对于较大的 n 值,如果您生成的文件很大,这可能会成为一个问题。我不确定你是否开始 运行 out of space before you 运行 out time,但仍然如此。可能更好的方法是边走边生成和测试它们,抛弃候选人。出于您的目的,可能存在用于生成的现有库 - 我找到了 this one,但我不知道它有多好。
使用图不变量
要更有效地列出图表,一个非常简单的第一步是使用 graph invariants. An obvious one would be degree sequence(图表的度数的有序列表)进行过滤。其他包括周期数、周长等。出于您的目的,可能有一些 indegree/outdegree 序列可供您使用。
基本思想是使用不变量作为过滤器来避免昂贵的同构检查。您可以存储已生成图形的(的)不变量列表,并首先根据列表检查新的不变量。结构的规范形式是一种不变量。
实现算法
GI算法丢失,包括nauty和friends使用的算法。但是,它们确实很难! this answer 中的描述是一个很好的概述,但细节决定成败。
另请注意,描述是针对一般图形的,而您有一个特定的图形子类可能更容易生成。那里可能有用于有向图列表(生成)的论文,但我没有检查过。
我正在尝试生成符合规范的所有唯一二合字母:
- 每个节点必须恰好有 2 个输入
- 并允许任意多个输出到图中的其他节点
我目前的解决方案很慢。例如,对于 6 个节点,该算法需要 1.5 天才能到达我认为 的位置,但它可能还要再检查几天。
我对具有 n
个节点的图的算法:
生成
0
的所有n
长度字符串,其中一个符号是1
,例如,对于 n=3,[[0,0,1], [0,1,0], [1,0,0]]
.这些可以被认为是单位矩阵中的行。生成所有可能的
n * n
矩阵,其中每一行都是step 1. + step 1.
的所有可能组合
这是连接矩阵,其中每个单元格代表从 column-index
到 row-index
因此,对于 n=3,这些是可能的:
[0,1,0] + [1,0,0] = [1,1,0]
[1,0,0] + [1,0,0] = [2,0,0]
这些表示节点的输入,通过将步骤 1 添加到自身,结果将始终表示 2 个输入。
例如:
A B C
A' [[0,1,1],
B' [0,2,0],
C' [1,1,0]]
因此 B
和 C
分别连接到 A
一次:B -> A', C -> A'
、
并且 B
连接到自身两次:B => B'
- 我只想要唯一的,所以对于生成的每个连接矩阵,如果它与已经看到的图不同构,我只能保留它。
这一步很昂贵。我需要通过同构图的每个排列将图转换为 运行 的 "canonical form",对它们进行排序,并将第一个视为 "canonical form"。
如果有人深入测试其中的任何一个,这里是 n
个节点的独特图表的计数:
2 - 6
3 - 44
4 - 475
5 - 6874
6 - 109,934 (I think, it's not done running yet but I haven't found a new graph in >24 hrs.)
7 - I really wanna know!
可能的优化:
既然我要生成要测试的图表,有没有办法在不测试的情况下将它们排除在外,因为它们与已经看到的图表同构?
有没有更快的图同构算法?
我认为这个与 "Nauty" 相关,还有其他我在论文中读到的,但我没有实现它们的专业知识(或带宽)还.
这是一个可演示的连接矩阵,可以在 graphonline.ru 处绘制以示乐趣,显示自连接以及到同一节点的 2 个连接:
1, 0, 0, 0, 0, 1,
1, 0, 0, 0, 1, 0,
0, 1, 0, 1, 0, 0,
0, 1, 2, 0, 0, 0,
0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 1, 0,
这里是 haskell 中的代码,如果你想玩的话,但我更关心的是算法是否正确(例如,减少搜索 space),而不是实现:
-- | generate all permutations of length n given symbols from xs
npermutations :: [a] -> Int -> [[a]]
npermutations xs size = mapM (const xs) [1..size]
identity :: Int -> [[Int]]
identity size = scanl
(\xs _ -> take size $ 0 : xs) -- keep shifting right
(1 : (take (size - 1) (repeat 0))) -- initial, [1,0,0,...]
[1 .. size-1] -- correct size
-- | return all possible pairings of [Column]
columnPairs :: [[a]] -> [([a], [a])]
columnPairs xs = (map (\x y -> (x,y)) xs)
<*> xs
-- | remove duplicates
rmdups :: Ord a => [a] -> [a]
rmdups = rmdups' Set.empty where
rmdups' _ [] = []
rmdups' a (b : c) = if Set.member b a
then rmdups' a c
else b : rmdups' (Set.insert b a) c
-- | all possible patterns for inputting 2 things into one node.
-- eg [0,1,1] means cells B, and C project into some node
-- [0,2,0] means cell B projects twice into one node
binaryInputs :: Int -> [[Int]]
binaryInputs size = rmdups $ map -- rmdups because [1,0]+[0,1] is same as flipped
(\(x,y) -> zipWith (+) x y)
(columnPairs $ identity size)
transposeAdjMat :: [[Int]] -> [[Int]]
transposeAdjMat ([]:_) = []
transposeAdjMat m = (map head m) : transposeAdjMat (map tail m)
-- | AdjMap [(name, inbounds)]
data AdjMap a = AdjMap [(a, [a])] deriving (Show, Eq)
addAdjColToMap :: Int -- index
-> [Int] -- inbound
-> AdjMap Int
-> AdjMap Int
addAdjColToMap ix col (AdjMap xs) =
let conns = foldl (\c (cnt, i) -> case cnt of
1 -> i:c
2 -> i:i:c
_ -> c
)
[]
(zip col [0..]) in
AdjMap ((ix, conns) : xs)
adjMatToMap :: [[Int]] -> AdjMap Int
adjMatToMap cols = foldl
(\adjMap@(AdjMap nodes) col -> addAdjColToMap (length nodes) col adjMap)
(AdjMap [])
cols
-- | a graph's canonical form : http://mfukar.github.io/2015/09/30/haskellxiii.html
-- very expensive algo, of course
canon :: (Ord a, Enum a, Show a) => AdjMap a -> String
canon (AdjMap g) = minimum $ map f $ Data.List.permutations [1..(length g)]
where
-- Graph vertices:
vs = map fst g
-- Find, via brute force on all possible orderings (permutations) of vs,
-- a mapping of vs to [1..(length g)] which is minimal.
-- For example, map [1, 5, 6, 7] to [1, 2, 3, 4].
-- Minimal is defined lexicographically, since `f` returns strings:
f p = let n = zip vs p
in (show [(snd x, sort id $ map (\x -> snd $ head $ snd $ break ((==) x . fst) n)
$ snd $ take_edge g x)
| x <- sort snd n])
-- Sort elements of N in ascending order of (map f N):
sort f n = foldr (\x xs -> let (lt, gt) = break ((<) (f x) . f) xs
in lt ++ [x] ++ gt) [] n
-- Get the first entry from the adjacency list G that starts from the given node X
-- (actually, the vertex is the first entry of the pair, hence `(fst x)`):
take_edge g x = head $ dropWhile ((/=) (fst x) . fst) g
-- | all possible matrixes where each node has 2 inputs and arbitrary outs
binaryMatrixes :: Int -> [[[Int]]]
binaryMatrixes size = let columns = binaryInputs size
unfiltered = mapM (const columns) [1..size] in
fst $ foldl'
(\(keep, seen) x -> let can = canon . adjMatToMap $ x in
(if Set.member can seen
then keep
else id $! x : keep
, Set.insert can seen))
([], Set.fromList [])
unfiltered
您可以尝试多种方法。我确实注意到的一件事是,具有多边循环(彩色循环?)有点不寻常,但可能只需要改进现有技术。
过滤另一个程序的输出
这里明显的候选者当然是 nAUTy/traces (http://pallini.di.uniroma1.it/) 或类似的(saucy、bliss 等)。取决于你想如何做到这一点,它可以像 运行 nauty(例如)一样简单并输出到文件,然后在你去的时候读入列表过滤。
对于较大的 n 值,如果您生成的文件很大,这可能会成为一个问题。我不确定你是否开始 运行 out of space before you 运行 out time,但仍然如此。可能更好的方法是边走边生成和测试它们,抛弃候选人。出于您的目的,可能存在用于生成的现有库 - 我找到了 this one,但我不知道它有多好。
使用图不变量
要更有效地列出图表,一个非常简单的第一步是使用 graph invariants. An obvious one would be degree sequence(图表的度数的有序列表)进行过滤。其他包括周期数、周长等。出于您的目的,可能有一些 indegree/outdegree 序列可供您使用。
基本思想是使用不变量作为过滤器来避免昂贵的同构检查。您可以存储已生成图形的(的)不变量列表,并首先根据列表检查新的不变量。结构的规范形式是一种不变量。
实现算法
GI算法丢失,包括nauty和friends使用的算法。但是,它们确实很难! this answer 中的描述是一个很好的概述,但细节决定成败。
另请注意,描述是针对一般图形的,而您有一个特定的图形子类可能更容易生成。那里可能有用于有向图列表(生成)的论文,但我没有检查过。