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)
然后我们按如下方式逐一处理队列中的顶点，直到队列变空：
首先，我们从队列中删除一个顶点v，然后找到其唯一未处理的入射边。令这条边表示为e
e的cut_value是e的权重乘以< code>min(cut_size[v], n - cut_size[v]).
让e的另一个端点用u表示。由于 e 现在已被处理，因此 u 上未处理的边数减少了 1，因此我们必须将 deg[u] 减少 1如果 deg[u] 变为 1，我们将 u 放入队列中。我们还将其 cut_size 加一，因为 v 现在是图形部分的一部分，当我们稍后删除 u< 上的最后一条边时，该部分将被分离/em>.
在 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
Elaborating a bit more on yurib's answer, I would do something like this (also posted on the igraph mailing list):
I will use two attributes, one for the vertices and one for the edges. The edge attribute is simple, it will be called cut_value and it is either None or contains the value you are looking for. Initially, all these values are Nones. We will call edges with cut_value=Noneunprocessed and edges where ``cut_value is not None``` processed.
The vertex attribute will be called cut_size, and it will be valid only for vertices for which there exists exactly one unprocessed incident edge. Since you have a tree, you will always have at least one such vertex unless all the edges are processed (where you can terminate the algorithm). Initially, cut_size will be 1 for all the vertices (but remember, they are valid only for vertices with exactly one unprocessed incident edge).
We will also have a list deg that contains the number of unprocessed edges incident on a given node. Initially all the edges are unprocessed, hence this list contains the degrees of the vertices.
So far we have this:
n, m = graph.vcount(), graph.ecount()
cut_values = [None] * m
cut_sizes = [1] * n
deg = graph.degree()
We will always process vertices with exactly one incident unprocessed edge. Initially, we put these in a queue:
from collections import deque
q = deque(v for v, d in enumerate(deg) if d == 1)
Then we process the vertices in the queue one by one as follows, until the queue becomes empty:
First, we remove a vertex v from the queue and find its only incident edge that is unprocessed. Let this edge be denoted by e
The cut_value of e is the weight of e multiplied by min(cut_size[v], n - cut_size[v]).
Let the other endpoint of e be denoted by u. Since e now became processed, the number of unprocessed edges incident on u decreased by one, so we have to decrease deg[u] by 1. If deg[u] became 1, we put u in the queue. We also increase its cut_size by one because v is now part of the part of the graph that will be separated when we later remove the last edge incident on u.
In Python, this should look like the following code (untested):
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
I don't know about your 1st question but i might have an idea about the 2nd. Since we're dealing with a minimal spanning tree, you can use the information you get about one edge to calculate the required property for for the edges adjacent to it (from now on i'll refer to this property as f(e) for an edge e). Lets look at the the edges (A,B) and (B,C). When you calculate f(A,B), lets assume that after removing the edge from the graph you find out that the smaller component is the one on the A side, you know that: f(B,C) = (f(A,B) / weight(A,B) + 1) * weight(B,C) This is true because (B,C) is adjacent to (A,B) and after removing it you will get the "almost" same two components, the only difference is that B moved from the larger component to the smaller one. This way, you can do the full calculation (including removal of the dge and discovery of components and their size) for one edge and then only a short calculation for every other edge connected to it. You will need to take special notice of the case where the smaller component (which grows as we go along the chain of edges) becomes the larger.
Update: After some more thought i realized that if you can find a leaf node in the tree, then you don't need to search for components and their size at all. You start by calculating f(e) for the edge attached to this node. Since its a leaf: f(e) = weight(e) * 1 (1 because it's a leaf node and after removing the edge you get a component with only the leaf and a component which is the rest of the graph.) From here you continue as discussed previously... Excluding the resources and time needed to find a leaf node, the rest of the computations will be done in O(m) (m being the number of edges) and using constant memory.
发布评论
评论（2）
详细阐述 yurib 的回答，我会做这样的事情（也发布在 igraph 邮件列表上）：
我将使用两个属性，一个用于顶点，一个用于边缘。边缘属性很简单，它被称为
cut_value，它要么是None，要么包含您正在查找的值。最初，所有这些值都是None。我们将使用cut_value=None未处理的边和“cut_value is not None”已处理的边来调用边。顶点属性将被称为
cut_size，并且它仅对恰好存在一条未处理的入射边的顶点有效。由于您有一棵树，因此您将始终拥有至少一个这样的顶点，除非所有边都已处理（您可以在其中终止算法）。最初，所有顶点的cut_size将为 1（但请记住，它们仅对具有一个未处理的入射边的顶点有效）。我们还将有一个列表 deg，其中包含给定节点上未处理的边的数量。最初，所有边都未处理，因此该列表包含顶点的度数。
到目前为止，我们已经得到了这一点：
我们将始终处理只有一个事件未处理边的顶点。最初，我们将它们放入队列中：
然后我们按如下方式逐一处理队列中的顶点，直到队列变空：
首先，我们从队列中删除一个顶点v，然后找到其唯一未处理的入射边。令这条边表示为e
e的
cut_value是e的权重乘以< code>min(cut_size[v], n - cut_size[v]).让e的另一个端点用u表示。由于 e 现在已被处理，因此 u 上未处理的边数减少了 1，因此我们必须将
deg[u]减少 1如果deg[u]变为 1，我们将 u 放入队列中。我们还将其cut_size加一，因为 v 现在是图形部分的一部分，当我们稍后删除 u< 上的最后一条边时，该部分将被分离/em>.在 Python 中，这应该类似于以下代码（未经测试）：
Elaborating a bit more on yurib's answer, I would do something like this (also posted on the igraph mailing list):
I will use two attributes, one for the vertices and one for the edges. The edge attribute is simple, it will be called
cut_valueand it is eitherNoneor contains the value you are looking for. Initially, all these values areNones. We will call edges withcut_value=Noneunprocessed and edges where ``cut_value is not None``` processed.The vertex attribute will be called
cut_size, and it will be valid only for vertices for which there exists exactly one unprocessed incident edge. Since you have a tree, you will always have at least one such vertex unless all the edges are processed (where you can terminate the algorithm). Initially,cut_sizewill be 1 for all the vertices (but remember, they are valid only for vertices with exactly one unprocessed incident edge).We will also have a list
degthat contains the number of unprocessed edges incident on a given node. Initially all the edges are unprocessed, hence this list contains the degrees of the vertices.So far we have this:
We will always process vertices with exactly one incident unprocessed edge. Initially, we put these in a queue:
Then we process the vertices in the queue one by one as follows, until the queue becomes empty:
First, we remove a vertex v from the queue and find its only incident edge that is unprocessed. Let this edge be denoted by e
The
cut_valueof e is the weight of e multiplied bymin(cut_size[v], n - cut_size[v]).Let the other endpoint of e be denoted by u. Since e now became processed, the number of unprocessed edges incident on u decreased by one, so we have to decrease
deg[u]by 1. Ifdeg[u]became 1, we put u in the queue. We also increase itscut_sizeby one because v is now part of the part of the graph that will be separated when we later remove the last edge incident on u.In Python, this should look like the following code (untested):
我不知道你的第一个问题，但我可能对第二个问题有一个想法。
由于我们正在处理一棵最小生成树，因此您可以使用获得的有关一条边的信息来计算与其相邻的边所需的属性（从现在开始，我将此属性称为 f(e)）边缘 e)。
让我们看看边缘 (A,B) 和 (B,C)。当您计算
f(A,B)时，假设从图中删除边后，您发现较小的分量是 A 侧的分量，您知道：f(B,C) = (f(A,B) / 权重(A,B) + 1) * 权重(B,C)这是正确的，因为 (B,C) 与 (A,B) 相邻，并且在删除它之后，您将得到“几乎”相同的两个分量，唯一的区别是 B 从较大的分量移动到较小的分量。
这样，您可以对一条边进行完整的计算（包括删除 dge 并发现组件及其大小），然后仅对与其连接的每个其他边进行简短的计算。
您需要特别注意较小的组件（随着我们沿着边缘链移动而增长）变得更大的情况。
更新：
经过更多思考，我意识到，如果您可以在树中找到叶节点，那么您根本不需要搜索组件及其大小。首先计算连接到该节点的边的 f(e)。因为它是一片叶子：
f(e) = Weight(e) * 1（1 因为它是一个叶节点，在删除边后，您将得到一个仅包含叶节点的组件和一个作为图的其余部分的组件。）从这里开始，您可以按照之前的讨论继续...
排除查找叶节点所需的资源和时间，其余计算将在 O(m)（m 是边数）内完成并使用常量内存。
I don't know about your 1st question but i might have an idea about the 2nd.
Since we're dealing with a minimal spanning tree, you can use the information you get about one edge to calculate the required property for for the edges adjacent to it (from now on i'll refer to this property as f(e) for an edge e).
Lets look at the the edges (A,B) and (B,C). When you calculate
f(A,B), lets assume that after removing the edge from the graph you find out that the smaller component is the one on the A side, you know that:f(B,C) = (f(A,B) / weight(A,B) + 1) * weight(B,C)This is true because (B,C) is adjacent to (A,B) and after removing it you will get the "almost" same two components, the only difference is that B moved from the larger component to the smaller one.
This way, you can do the full calculation (including removal of the dge and discovery of components and their size) for one edge and then only a short calculation for every other edge connected to it.
You will need to take special notice of the case where the smaller component (which grows as we go along the chain of edges) becomes the larger.
Update:
After some more thought i realized that if you can find a leaf node in the tree, then you don't need to search for components and their size at all. You start by calculating f(e) for the edge attached to this node. Since its a leaf:
f(e) = weight(e) * 1(1 because it's a leaf node and after removing the edge you get a component with only the leaf and a component which is the rest of the graph.)From here you continue as discussed previously...
Excluding the resources and time needed to find a leaf node, the rest of the computations will be done in O(m) (m being the number of edges) and using constant memory.