图形中的最大全网格-python代码非常慢 [英] Maximal full-mesh in a graph - python code is very slow
问题描述
我有一些python代码，用于计算图中的最大全网格.图的每个节点可以具有不同的权重(每个节点的权重由数组给定).考虑到不存在的边缘，我想在图中获得最大的加权clique大小.我为此编写了一些python代码，如下所示:
I have some python code for computing the maximal full-mesh in a graph. Each node of the graph can have a different weight (The weights of each node are given by an array). I want to get the maximal weighted-clique size in the graph, given the edges that are not present. I wrote some python code for this that works as follows:
- 我从存在所有边的全连接图开始.
- 如果一条边在全连接图中断开，则会将其分成两个全连接图(下面的split_full_meshes方法).
- 最后，我将所有可能的群体的权重相加，得出具有最大权重的群体.
下面包含该代码(maximum_full_mesh计算最大加权集团，而split_full_meshes是拆分集团的助手).问题在于它运行缓慢.我需要能够在200万个循环中运行此程序(所有可能的图形都有7个节点)，但是要花整整10分钟才能运行.我正在寻找有关如何使其更快的建议.
The code is included below (maximal_full_mesh calculates the maximal weighted clique while split_full_meshes is a helper for splitting cliques). The problem is that it is painfully slow. I need to be able to run this in a loop of 2 million (all possible graphs with seven nodes), but it takes a full 10 minutes to run. I'm looking for suggestions on how I can make this faster.
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
推荐答案
在这里，我以相反的方式解决了这个问题，我生成了要从原始全网格中排除的节点集，以使每个最终的全网格成为可能.由此，我可以轻松地使用一些技巧-使用集差异跳过相应完整网格中未包含的边缘，并在超出权重阈值时尽早修剪次优分支.
Here I tackle the problem in reverse- I generate the sets of nodes to exclude from the original full-mesh to make each resulting full-mesh. From this, I can easily use a few tricks- skipping over edges that aren't contained in the corresponding full mesh using set differences, and pruning sub optimal branches early as they exceed the weight threshold.
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
这篇关于图形中的最大全网格-python代码非常慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
