-2

我正在使用igraph（通过 python）进行图形聚类。

我有一棵带有加权边的树（几何图的最小生成树），如果删除了边，我想计算权重乘以两个组件的较小顶点数：

def sep(graph, e):
    h = copy(graph)
    w = h.es[e]['weight']
    h.delete_edges(e)
    return w * min(h.components().sizes())

# 'graph' is the tree I am dealing with
ss = [sep(graph,x) for x in range(len(graph.es))]

我的问题是：

  1. 这是图论中的已知（和命名）属性吗？如果是这样，它是什么？

  2. 如果我对所有边进行计算，我的代码效率非常低，如上所示。如果图变成 50000 条边和顶点，那么内存消耗就会变得巨大。您对优化有什么建议吗？

4

2 回答 2

1

我不知道您的第一个问题，但我可能对第二个问题有所了解。
由于我们正在处理最小生成树，因此您可以使用获得的关于一条边的信息来计算与其相邻的边所需的属性（从现在开始，我将此属性称为 f(e)边 e)。
让我们看看边缘（A，B）和（B，C）。当您计算f(A,B)时，假设从图中删除边后，您发现较小的组件是 A 侧的组件，您知道：
f(B,C) = (f(A,B) / weight(A,B) + 1) * weight(B,C)
这是真的，因为 (B,C) 与 (A,B) 相邻，并且在删除它之后，您将获得“几乎”相同的两个组件，唯一的区别是 B 从较大的组件移动到较小的组件。这样，您可以对一条边进行完整计算（包括删除 dge 和发现组件及其大小），然后只对连接到它的所有其他边进行简短计算。
您需要特别注意较小的组件（随着我们沿着边缘链增长）变得较大的情况。

更新：
经过深思熟虑后，我意识到如果您可以在树中找到叶节点，那么您根本不需要搜索组件及其大小。首先计算连接到该节点的边的 f(e)。因为它是一个叶子：
f(e) = weight(e) * 1（1 因为它是一个叶子节点，在删除边缘之后，您会得到一个只有叶子的组件和一个组件，它是图的其余部分。）
从这里您继续如前所述...
排除资源以及找到叶节点所需的时间，其余的计算将在 O(m) 中完成（m 是边数）并使用常量内存。

于 2011-05-30T11:55:23.973 回答
1

详细说明yurib 的回答，我会做这样的事情（也发布在 igraph 邮件列表上）：

我将使用两个属性，一个用于顶点，一个用于边缘。edge 属性很简单，它会被调用cut_value，它要么是要么None包含您要查找的值。最初，所有这些值都是Nones。我们将调用cut_value=None 未处理的边和 ``cut_value 不是 None```处理的边。

vertex 属性将被调用cut_size，它只对恰好存在一个未处理的入射边的顶点有效。由于您有一棵树，因此您将始终拥有至少一个这样的顶点，除非所有边都已处理（您可以在此处终止算法）。最初，cut_size所有顶点都为 1（但请记住，它们仅对只有一个未处理的入射边的顶点有效）。

我们还将有一个列表deg，其中包含发生在给定节点上的未处理边的数量。最初所有边都未处理，因此该列表包含顶点的度数。

到目前为止，我们有这个：

n, m = graph.vcount(), graph.ecount()
cut_values = [None] * m
cut_sizes = [1] * n
deg = graph.degree()

我们将始终处理具有恰好一个事件未处理边的顶点。最初，我们将这些放在一个队列中：

from collections import deque
q = deque(v for v, d in enumerate(deg) if d == 1)

然后我们对队列中的顶点进行如下处理，直到队列为空：

  1. 首先，我们从队列中删除一个顶点v并找到它唯一未处理的入射边。让这条边用e表示

  2. e的cut_value权重是e乘以。min(cut_size[v], n - cut_size[v])

  3. 让e的另一个端点由u表示。由于e现在已处理，发生在u上的未处理边数减少了 1，因此我们必须减少deg[u]1。如果deg[u]变为 1，我们将u放入队列中。我们还将其cut_size加一，因为v现在是图的一部分，当我们稍后移除u上的最后一个边缘事件时，该部分将被分离。

在 Python 中，这应该类似于以下代码（未经测试）：

weights = graph.es["weight"]
while q:
    # Step 1
    v = q.popleft()
    neis = [e for e in graph.incident(v) if cut_value[e] is None]
    if len(neis) != 1:
        raise ValueError("this should not have happened")
    e = neis[0]

    # Step 2
    cut_values[e] = weights[e] * min(cut_sizes[v], n - cut_sizes[v])

    # Step 3
    endpoints = graph.es[e].tuple
    u = endpoints[1] if endpoints[0] == v else endpoints[0]
    deg[u] -= 1
    if deg[u] == 1:
        q.append(u)
    cut_sizes[u] += 1
于 2011-05-30T13:13:18.567 回答