forEdges 迭代器在 networkit 中的使用 (python)
Usage of forEdges iterator in networkit (python)
我仔细阅读了文档,但我仍然不清楚如何使用 G.forEdges(),描述为 "experimental edge iterator interface"。
假设我想降低图表的密度。我有一个排序的权重列表,我想根据权重删除边,直到图形分成两个连接的组件。然后我将 select 保持图形连接的最小链接数。我会做这样的事情:
cc = components.ConnectedComponents(G).run()
while cc.numberOfComponents()==1:
for weight in weightlist:
for (u,v) in G.edges():
if G.weight(u,v)==weight:
G=G.removeEdge(u,v)
顺便说一下,我从 docs 那里知道有一个边缘迭代器,它可能以更有效的方式进行迭代。但是从文档中我真的无法理解如何正确使用这个 forEdges
,而且我在互联网上找不到一个例子。有任何想法吗?
或者可能是一个替代想法来做我想做的事情:因为它是一个巨大的图(1.25 亿个链接)迭代将永远持续下去,即使我在集群上工作也是如此。
NetworKit 迭代器接受一个回调函数,所以如果你想迭代边(或节点),你必须定义一个函数,然后将它作为参数传递给迭代器。您可以找到更多信息 here。例如,一个只打印所有边缘的简单函数是:
# Callback function.
# To iterate over edges it must accept 4 parameters
def myFunction(u, v, weight, edgeId):
print("Edge from {} to {} has weight {} and id {}".format(u, v, weight, edgeId))
# Using iterator with callback function
G.forEdges(myFunction)
现在,如果您想继续删除权重在您的权重列表中的边,直到图形分成两个连接的组件,您还必须更新图形的连接组件,因为 ConnectedComponents 不会自动为您执行此操作(这可能这也是迭代需要永远进行的原因之一)。要有效地执行此操作,您可以使用 DynConnectedComponents class(请参阅下面的示例)。在这种情况下,我认为边迭代器对你帮助不大,所以我建议你继续使用 for 循环。
from networkit import *
# Efficiently updates connected components after edge updates
cc = components.DynConnectedComponents(G).run()
# Removes edges with weight equals to w until components split
def removeEdges(w):
for (u, v) in G.edges():
if G.weight(u, v) == weight:
G.removeEdge(u, v)
# Updating connected components
event = dynamic.GraphEvent(dynamic.GraphEvent.EDGE_REMOVAL, u, v, weight)
cc.update(event)
if cc.numberOfComponents() > 1:
# Components did split
return True
# Components did not split
return False
if cc.numberOfComponents() == 1:
for weight in weights:
if removeEdges(weight):
break
这应该会加快您的原始代码速度。但是,它仍然是顺序代码,因此即使您 运行 它在 multi-core 机器上,它也只会使用一个核心。
我仔细阅读了文档,但我仍然不清楚如何使用 G.forEdges(),描述为 "experimental edge iterator interface"。
假设我想降低图表的密度。我有一个排序的权重列表,我想根据权重删除边,直到图形分成两个连接的组件。然后我将 select 保持图形连接的最小链接数。我会做这样的事情:
cc = components.ConnectedComponents(G).run()
while cc.numberOfComponents()==1:
for weight in weightlist:
for (u,v) in G.edges():
if G.weight(u,v)==weight:
G=G.removeEdge(u,v)
顺便说一下,我从 docs 那里知道有一个边缘迭代器,它可能以更有效的方式进行迭代。但是从文档中我真的无法理解如何正确使用这个 forEdges
,而且我在互联网上找不到一个例子。有任何想法吗?
或者可能是一个替代想法来做我想做的事情:因为它是一个巨大的图(1.25 亿个链接)迭代将永远持续下去,即使我在集群上工作也是如此。
NetworKit 迭代器接受一个回调函数,所以如果你想迭代边(或节点),你必须定义一个函数,然后将它作为参数传递给迭代器。您可以找到更多信息 here。例如,一个只打印所有边缘的简单函数是:
# Callback function.
# To iterate over edges it must accept 4 parameters
def myFunction(u, v, weight, edgeId):
print("Edge from {} to {} has weight {} and id {}".format(u, v, weight, edgeId))
# Using iterator with callback function
G.forEdges(myFunction)
现在,如果您想继续删除权重在您的权重列表中的边,直到图形分成两个连接的组件,您还必须更新图形的连接组件,因为 ConnectedComponents 不会自动为您执行此操作(这可能这也是迭代需要永远进行的原因之一)。要有效地执行此操作,您可以使用 DynConnectedComponents class(请参阅下面的示例)。在这种情况下,我认为边迭代器对你帮助不大,所以我建议你继续使用 for 循环。
from networkit import *
# Efficiently updates connected components after edge updates
cc = components.DynConnectedComponents(G).run()
# Removes edges with weight equals to w until components split
def removeEdges(w):
for (u, v) in G.edges():
if G.weight(u, v) == weight:
G.removeEdge(u, v)
# Updating connected components
event = dynamic.GraphEvent(dynamic.GraphEvent.EDGE_REMOVAL, u, v, weight)
cc.update(event)
if cc.numberOfComponents() > 1:
# Components did split
return True
# Components did not split
return False
if cc.numberOfComponents() == 1:
for weight in weights:
if removeEdges(weight):
break
这应该会加快您的原始代码速度。但是,它仍然是顺序代码,因此即使您 运行 它在 multi-core 机器上,它也只会使用一个核心。