在networkit（python）中使用forEdges迭代器 [英] Usage of forEdges iterator in networkit (python)

问题描述

我仔细阅读了文档，但是仍然不清楚如何使用G.forEdges（），将其描述为实验性边缘迭代器接口。

假设我想减少图形的密度。我有一个权重排序列表，我想根据它们的权重去除边，直到图分成两个连接的组件。然后，我将选择保持图形连接的最少链接数量。我会做这样的事情：

  cc = components.ConnectedComponents（G）.run（）
而cc。 numberOfComponents（）== 1：
用于weightlist中的weight：
用于（u，v）在G.edges（）中：
如果weight（u，v）== weight： 
 G = G.removeEdge（u，v）
  

顺便说一句， docs 有这个边缘迭代器，它可能会在更多高效的方式。但从文档中，我真的无法理解如何正确使用 forEdges ，并且我无法通过Internet找到一个示例。有任何想法吗？

或者也许是另一种想法去做我想做的事情：因为它是一个巨大的图表（125百万条链接），迭代将永远持续下去，即使我正在NetworKit迭代器接受一个回调函数，所以如果你想遍历边（或节点），你必须定义一个函数，然后将其作为参数传递给迭代器。 此处可以找到更多信息。例如，一个简单的函数可以打印所有边：

 ＃回调函数。 
＃要遍历边，它必须接受4个参数
 def myFunction（u，v，weight，edgeId）：
 print（从{}到{}的边具有权重{}和id {}。format（u，v，weight，edgeId））
 
＃使用带回调函数的迭代器
 G.forEdges（myFunction）
  

现在，如果您想继续删除重量在您的重量表内的边缘，直到图形分成两个连接的组件，您还必须更新连接的组件因为ConnectedComponents不会自动为你做这件事（这也可能是迭代需要永久性的原因之一）。为了有效地做到这一点，你可以使用DynConnectedComponents类（参见下面的示例）。在这种情况下，我认为边迭代器不会对你有太大的帮助，所以我建议你继续使用for循环。

  from networkit import * 
 
＃边缘更新后有效更新连接组件
 cc = components.DynConnectedComponents（G）.run（）
 
＃删除边的权重等于w，直到组件拆分
 def removeEdges（w）：
 for（u，v）in G.edges（）：
如果G.weight（u，v）==权重：
 G.removeEdge（u，v）
＃更新连接的组件
 event = dynamic .GraphEvent（dynamic.GraphEvent.EDGE_REMOVAL，u，v，weight）
 cc.update（event）
 if cc.numberOfComponents（）> 1：
＃组件分割
返回True 
＃组件未分割
返回False 
 
如果cc.numberOfComponents（）== 1：
的重量权重：
如果removeEdges（重量）：
 break 
  

<这应该会加快你的原始代码。但是，它仍然是顺序代码，所以即使您在多核计算机上运行，​​它也只会使用一个内核。

I carefully read the docs, but it still is unclear to me how to use G.forEdges(), described as an "experimental edge iterator interface".

Let's say that I want to decrease the density of my graph. I have a sorted list of weights, and I want to remove edges based on their weight until the graph splits into two connected components. Then I'll select the minimum number of links that keeps the graph connected. I would do something like this:

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)

By the way I know from the docs that there is this edge iterator, which probably does the iteration in a more efficient way. But from the docs I really can't understand how to correctly use this forEdges, and I can't find a single example over the internet. Any ideas?

Or maybe an alternative idea to do what I want to do: since it's a huge graph (125millions links) the iteration will take forever, even if I am working on a cluster.

解决方案

NetworKit iterators accept a callback function so if you want to iterate over edges (or nodes) you have to define a function and then pass it to the iterator as a parameter. You can find more information here. For example a simple function that just prints all edges is:

# 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)

Now if you want to keep removing edges whose weight is inside your weightlist until the graph splits into two connected components you also have to update the connected components of the graph since ConnectedComponents will not do that for you automatically (this may be also one of the reasons why the iteration takes forever). To do this efficiently, you can use the DynConnectedComponents class (see my example below). In this case, I think that the edge iterator will not help you much so I would suggest you to keep using the for loop.

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

This should speed up a bit your original code. However, it is still sequential code so even if you run it on a multi-core machine it will use only one core.

这篇关于在networkit（python）中使用forEdges迭代器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！