代码之家 › 专栏 › 技术社区 › Rohit Pandey

图中的最大完整网格-python代码非常慢

graph performance python

Rohit Pandey · 技术社区 · 6 年前

我有一些用于计算图形中最大完整网格的python代码。图中的每个节点可以有不同的权重(每个节点的权重由一个数组给出)。我想得到最大的加权集团在图中的大小,给定的边缘不存在。我为此编写了一些python代码,其工作方式如下:

我从所有边都存在的完全连接图开始。
如果一条边在一个完全连接的图中被打断,它将把它分成两个完全连接的图(下面的split-full-meshes方法)。
最后,我将所有可能的集团的权重相加,得到最大权重的集团。

代码包含在下面(最大网格计算最大加权集团,而分裂网格是分裂集团的助手)。问题是速度太慢了。我需要能够在一个200万的循环中运行它(所有可能的图都有七个节点),但是运行它需要整整10分钟。我正在寻找有关如何加快速度的建议。

def split_full_meshes(meshes=[[0,1,2],[0,1,3]], broken_edge=[0,1]):
    """
    A full mesh is defined as a series of nodes that
    are all interconnected with each other. When we break an edge,
    any full-mesh that has both nodes corresponding to that edge will be 
    broken up
    into two smaller full-meshes.
    args:
        meshes: A jagged array, each entry is an array of indices of nodes 
            that are full-mesh connected.
        broken_edge: The edge that was not earlier broken but is now going
                 to be broken.
    """
    nu_meshes = []
    for mesh in meshes:
        if broken_edge[0] in mesh and broken_edge[1] in mesh:
            for node in broken_edge:
                nu_meshes.append([i for i in mesh if i!= node])
        else:
            nu_meshes.append(np.copy(mesh))
    return nu_meshes


def maximal_full_mesh(a=np.array([2,2,3,4]), \
    broken_edges=np.array([[0,1],[2,3]])):
    """
    The largest weighted full-mesh available in the graph.
    (set of nodes with perfect interconnectivity with each other).
    args:
        a: The weights of each node in the graph.
        broken_edges: The edges between nodes that are broken.
    """
    meshes = [np.arange(len(a))]
    for ed in broken_edges:
        meshes_tmp = np.copy(meshes)
        meshes = split_full_meshes(meshes_tmp, ed)
    max_mesh = 0
    for mesh in meshes:
        max_mesh = max(max_mesh, sum(a[np.array(mesh)]))
    return max_mesh

1 回复 | 直到 6 年前

Dillon Davis 6 年前

在这里,我以相反的方式解决了这个问题——我生成了从原始完整网格中排除的节点集,以生成每个生成的完整网格。从这里,我可以很容易地使用一些技巧-跳过没有包含在相应的完整网格中的边,使用集差异,并在次优分支超过权重阈值时对其进行修剪。

class FullMesh:
    def __init__(self, pairs, weights):
        self.pairs = pairs
        self.weights = weights
        self.elements = set(range(len(weights)))

        self.skips = {e:set() for e in self.elements}
        for i, (a, b) in enumerate(pairs):
            self.skips[a].add(i)
            self.skips[b].add(i)

    def find_max(self):
        max_score = sum(self.weights)
        val, nums = self.exclude(0, max_score + 1, set(range(len(self.pairs))))
        return max_score - val, sorted(self.elements - set(nums))

    def exclude(self, curr_score, min_score, search):
        if not search or min_score <= curr_score:
            return curr_score, []

        min_nums = []
        for e in self.pairs[next(iter(search))]:
            score, nums = self.exclude(curr_score + self.weights[e], min_score, search - self.skips[e])
            if score < min_score:
                min_score, min_nums = score, nums + [e]
        return min_score, min_nums