在无向图中查找大小为N的所有子树

Question

给定一个无向图,我想生成所有子图,这些子图是大小为N的树,其中size指的是树中边的数量.

我知道它们中有很多(至少对于具有恒定连通性的图形呈指数多) - 但这很好,因为我相信节点和边缘的数量使得这对于至少小的N值(例如10或更小)来说易于处理).

该算法应该具有内存效率 - 也就是说,它不需要同时在内存中包含所有图形或其中的一些大部分子集,因为即使对于相对较小的图形,这也可能超过可用内存.所以像DFS这样的东西是可取的.

给出起始图graph和所需长度,这是我在伪代码中的想法N:

选择任意节点,root作为起点并调用alltrees(graph, N, root)

alltrees(graph, N, root)
 given that node root has degree M, find all M-tuples with integer, non-negative values whose values sum to N (for example, for 3 children and N=2, you have (0,0,2), (0,2,0), (2,0,0), (0,1,1), (1,0,1), (1,1,0), I think)
 for each tuple (X1, X2, ... XM) above
   create a subgraph "current" initially empty
   for each integer Xi in X1...XM (the current tuple)
    if Xi is nonzero
     add edge i incident on root to the current tree
     add alltrees(graph with root removed, N-1, node adjacent to root along edge i)
   add the current tree to the set of all trees
 return the set of all trees

这只找到包含所选初始根的树,所以现在删除此节点并调用alltrees(删除了根的图形,N,新任意选择的根),并重复直到剩余图形的大小<N(因为没有所需的树)大小将存在).

我也忘记了每个被访问的节点(每个根用于一些alltrees的调用)需要被标记,并且上面考虑的子集应该只是相邻的未标记的子节点.我想我们需要考虑没有未标记的子节点但是深度> 0的情况,这意味着这个"分支"未能达到所需的深度,并且不能形成解集的一部分(所以整个内部循环与那个元组可以被中止).

那么这会有用吗？有什么重大缺陷吗？有没有更简单/已知/规范的方法呢？

上面概述的算法的一个问题是它不满足存储器效率要求,因为递归将在存储器中保存大量树.

Answer 1

这需要一定量的内存,与存储图形所需的内存成比例.它将返回每个具有所需大小的树的子图正好一次.

请记住,我只是在这里打字.可能有错误.但这个想法是你一次一个地走节点,每个节点搜索包含该节点的所有树,但没有先前搜索过的节点.(因为那些已经用尽了.)内部搜索是通过将边缘列出到树中的节点以及决定是否将其包含在树中的每个边缘来递归完成的.(如果它会创建一个循环,或者添加一个耗尽的节点,那么就不能包含该边缘.)如果将它包含在树中,那么使用的节点会增长,并且您有新的可能边缘要添加到搜索中.

为了减少内存使用,剩下要查看的边缘由递归调用的所有级别操作,而不是在每个级别复制该数据的更明显的方法.如果复制了该列表,则总内存使用量将达到树的大小乘以图中边的数量.

def find_all_trees(graph, tree_length):
    exhausted_node = set([])
    used_node = set([])
    used_edge = set([])
    current_edge_groups = []

    def finish_all_trees(remaining_length, edge_group, edge_position):
        while edge_group < len(current_edge_groups):
            edges = current_edge_groups[edge_group]
            while edge_position < len(edges):
                edge = edges[edge_position]
                edge_position += 1
                (node1, node2) = nodes(edge)
                if node1 in exhausted_node or node2 in exhausted_node:
                    continue
                node = node1
                if node1 in used_node:
                    if node2 in used_node:
                        continue
                    else:
                        node = node2
                used_node.add(node)
                used_edge.add(edge)
                edge_groups.append(neighbors(graph, node))
                if 1 == remaining_length:
                    yield build_tree(graph, used_node, used_edge)
                else:
                    for tree in finish_all_trees(remaining_length -1
                                                , edge_group, edge_position):
                        yield tree
                edge_groups.pop()
                used_edge.delete(edge)
                used_node.delete(node)
            edge_position = 0
            edge_group += 1

    for node in all_nodes(graph):
        used_node.add(node)
        edge_groups.append(neighbors(graph, node))
        for tree in finish_all_trees(tree_length, 0, 0):
            yield tree
        edge_groups.pop()
        used_node.delete(node)
        exhausted_node.add(node)

Answer 2

假设你可以破坏原始图表或制作一个可破坏的副本，我想到了一些可以工作但可能完全是悲伤的东西，因为我没有计算它的 O-Ntiness。它可能适用于小子树。

• 分步骤进行，每一步：
• 对图节点进行排序，以便获得按相邻边数 ASC 排序的节点列表
• 处理与第一个节点具有相同边数的所有节点
• 删除那些节点

以 6 个节点的图为例，查找所有大小为 2 的子图（抱歉我完全缺乏艺术表达能力）：

对于更大的图表来说也是如此，但应该分更多的步骤来完成。

假设：

• Z 最分支节点的边数
• M 期望的子树大小
• S 步数
• Ns 步骤中的节点数
• 假设快速排序对节点进行排序

最坏情况：S*(Ns^2 + M Ns Z)

平均情况：S*(NslogNs + M Ns (Z/2))

问题是：无法计算真正的 omicron，因为每个步骤中的节点都会减少，具体取决于图形的情况......

在具有紧密连接的节点的图上用这种方法解决整个问题可能非常耗时，但是它可以并行化，并且您可以执行一两个步骤，删除脱位的节点，提取所有子图，然后选择另一种方法其余的，但是您会从图中删除很多节点，这样就可以减少剩余的运行时间......

不幸的是，这种方法对 GPU 有利，而不是对 CPU 有利，因为每一步都会有很多具有相同边数的节点......并且如果不使用并行化，这种方法可能很糟糕......

也许逆运算会更好地使用CPU，对具有最大边数的节点进行排序和继续...这些在开始时可能会更少，但您将从每个节点提取更多的子图...

另一种可能性是计算图中最少出现的egde计数并从具有它的节点开始，这将减轻提取子图的内存使用和迭代计数......