什么是枚举父图的所有子图的有效算法。在我的特定情况下,父图是一个分子图,因此它将被连接并且通常包含少于 100 个顶点。
编辑:我只对连接的子图感兴趣。
什么是枚举父图的所有子图的有效算法。在我的特定情况下,父图是一个分子图,因此它将被连接并且通常包含少于 100 个顶点。
编辑:我只对连接的子图感兴趣。
这个问题在这个问题的公认答案中有更好的答案。它避免了@ninjagecko 的答案中标记为“您填写上述函数”的计算复杂步骤。它可以有效地处理有多个环的化合物。
有关完整详细信息,请参阅链接的问题,但这里是摘要。(N(v) 表示顶点 v 的邻居集合。在“选择顶点”步骤中,您可以选择任意顶点。)
GenerateConnectedSubgraphs(verticesNotYetConsidered, subsetSoFar, neighbors):
if subsetSoFar is empty:
let candidates = verticesNotYetConsidered
else
let candidates = verticesNotYetConsidered intersect neighbors
if candidates is empty:
yield subsetSoFar
else:
choose a vertex v from candidates
GenerateConnectedSubgraphs(verticesNotYetConsidered - {v},
subsetSoFar,
neighbors)
GenerateConnectedSubgraphs(verticesNotYetConsidered - {v},
subsetSoFar union {v},
neighbors union N(v))
什么是枚举父图的所有子图的有效算法。在我的特定情况下,父图是一个分子图,因此它将被连接并且通常包含少于 100 个顶点。
与数学子图的比较:
您可以给每个元素一个从 0 到 N 的数字,然后将每个子图枚举为长度为 N 的任何二进制数。您根本不需要扫描图。
如果您真正想要的是具有不同属性(完全连接等)的子图,那么您需要更新您的问题。正如评论员指出的那样,2^100 非常大,因此您绝对不想(如上)枚举数学上正确但物理上无聊的断开子图。假设每秒 10 亿次枚举,您实际上需要至少 40 万亿年才能将它们全部枚举完。
连接子图生成器:
如果您想要某种枚举在某些度量下保留子图的 DAG 属性,例如 (1,2,3)->(2,3)->(2), (1,2,3)->(1 ,2)->(2),你只需要一个算法,它可以生成所有 CONNECTED 子图作为迭代器(产生每个元素)。这可以通过一次递归地删除一个元素(可选地从“边界”)、检查剩余的元素集是否在缓存中(否则添加它)、产生它并递归来完成。如果您的分子非常链状且循环次数很少,则此方法效果很好。例如,如果您的元素是 N 个元素的 5 角星,它只会有大约 (100/5)^5 = 320 万个结果(不到一秒)。但是,如果您开始添加多个环,例如芳香族化合物和其他环,您可能会遇到困难。
例如在python中
class Graph(object):
def __init__(self, vertices):
self.vertices = frozenset(vertices)
# add edge logic here and to methods, etc. etc.
def subgraphs(self):
cache = set()
def helper(graph):
yield graph
for element in graph:
if {{REMOVING ELEMENT WOULD DISCONNECT GRAPH}}:
# you fill in above function; easy if
# there is 0 or 1 ring in molecule
# (keep track if molecule has ring, e.g.
# self.numRings, maybe even more data)
# if you know there are 0 rings the operation
# takes O(1) time
continue
subgraph = Graph(graph.vertices-{element})
if not subgraph in cache:
cache.add(subgraph)
for s in helper(subgraph):
yield s
for graph in helper(self):
yield graph
def __eq__(self, other):
return self.vertices == other.vertices
def __hash__(self):
return hash(self.vertices)
def __iter__(self):
return iter(self.vertices)
def __repr__(self):
return 'Graph(%s)' % repr(set(self.vertices))
示范:
G = Graph({1,2,3,4,5})
for subgraph in G.subgraphs():
print(subgraph)
结果:
Graph({1, 2, 3, 4, 5})
Graph({2, 3, 4, 5})
Graph({3, 4, 5})
Graph({4, 5})
Graph({5})
Graph(set())
Graph({4})
Graph({3, 5})
Graph({3})
Graph({3, 4})
Graph({2, 4, 5})
Graph({2, 5})
Graph({2})
Graph({2, 4})
Graph({2, 3, 5})
Graph({2, 3})
Graph({2, 3, 4})
Graph({1, 3, 4, 5})
Graph({1, 4, 5})
Graph({1, 5})
Graph({1})
Graph({1, 4})
Graph({1, 3, 5})
Graph({1, 3})
Graph({1, 3, 4})
Graph({1, 2, 4, 5})
Graph({1, 2, 5})
Graph({1, 2})
Graph({1, 2, 4})
Graph({1, 2, 3, 5})
Graph({1, 2, 3})
Graph({1, 2, 3, 4})
有一种称为 gspan [1] 的算法已用于计算频繁子图,它也可用于枚举所有子图。你可以在这里找到它的实现 [2]。
想法如下:图由所谓的 DFS 代码表示。DFS 代码对应于图 G 上的深度优先搜索,并且对于每条边 (v_i, v_j) 都有一个形式为 (i, j, l(v_i), l(v_i, v_j), l(v_j)) 的条目),其中顶点下标对应于 DFS 发现顶点的顺序。可以在所有 DFS 代码集上定义总顺序(如 [1] 中所做的那样),因此可以通过计算表示该图的所有 DFS 代码的最小值来获得给定图的规范图标签。这意味着如果两个图具有相同的最小 DFS 代码,它们是同构的。现在,从所有可能的长度为 1 的 DFS 代码(每条边一个)开始,一个图的所有子图可以通过随后一次添加一条边到代码中来枚举,这会产生一个枚举树,其中每个节点对应于一个图。如果仔细进行枚举(即与 DFS 代码上的顺序兼容),则首先遇到最小的 DFS 代码。因此,每当遇到不是最小的 DFS 代码时,可以修剪其对应的子树。详情请参阅 [1]。
[1] https://sites.cs.ucsb.edu/~xyan/papers/gSpan.pdf [2] http://www.nowozin.net/sebastian/gboost/