2

对于一个不那么小的网络（5000 个节点和 25k 个无向边），我想在距离为 2 处找到所有节点的邻居。现在我正在使用：

ArrayList<Node> twoDistNei = new ArrayList<Node>();
Collection<Node> myThreads = g.getNeighbors(u);
for(Node t:myThreads){
    Collection<Node> neighbors = g.getNeighbors(t);
    for(Node uu:neighbors){
       if(!twoDistNei.contains(uu)){
           twoDistNei.add(uu);
        }
    }
}

但它真的很慢，我想知道是否有更有效和快速的方法来完成这个。

编辑：如前所述，我设法使用了 KNeighborhoodFilter，这就是我得出的结论：

KNeighborhoodFilter filter = new KNeighborhoodFilter(u, 2,KNeighborhoodFilter.EdgeType.IN_OUT);
Graph<Node, Edge> transform = filter.transform(zpa);
Collection<Node> vertices = transform.getVertices();
Set<Node> twoDistThreads = new HashSet<Node>();
for (Node v : vertices) {
    if(v.getColor().equals("blue")){
       twoDistThreads.add((Thread)v);         
    }
    System.out.println("thread " + v.getName() + " has color " + v.getColor());
}

现在我看到过滤器只允许转换（）原始网络并用所有选定的节点（加上链接到选定节点的节点......但是为什么呢？）。这意味着我必须过滤新的节点集合以仅捕获我感兴趣的 2-dist 顶点 - 我有一个二分图，其中一组节点是“蓝色”，另一个是“红色”。我在这里做事吗，@Joshua？谢谢您的帮助！

最好的问候，西蒙娜

4

2 回答 2

2

这就是 KNeighborhoodFilter 的用途：http: //jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.html

于 2013-05-12T18:07:30.837 回答
1

您将所有邻居置于双循环中的方法很好。您现在并且应该依靠荣格为您找到所有邻居。如果您对 Jung 获得所有邻居的方法不满意，您可以 1）改进 Jung 或 2）使用其他方法，但我怀疑这实际上是问题所在：

您正在使用一种非常缓慢的方法来确保您不会使用 ArrayList 两次存储同一个邻居：

  if(!twoDistNei.contains(uu)){
       twoDistNei.add(uu);
    }

ArrayList.contains所做的只是遍历所有项目以检查它是否具有特定项目，因此数组越大，twoDistNei包含方法变得越慢。这称为线性时间算法，因此在这种情况下与 ArrayList 中的项目数量呈线性关系。有一些恒定时间算法可以达到同样的效果，但无论你的数组有多大，总是需要同样的时间。

我建议您使用 aHashSet而不是 a ArrayList，如下所示：

HashSet<Node> twoDistNei = new HashSet<Node>();
Collection<Node> myThreads = g.getNeighbors(u);
for(Node t:myThreads){
    twoDistNei.addAll( g.getNeighbors(t) );
}

HashSet 的一个定义属性是它不存储重复的条目，因此您可以简单地使用addAll，一切都会得到照顾。此外，HashSet 使用基于 hashCode 的索引构建一个内部数组，从而平均实现恒定时间性能。

希望这可以帮助！:)

于 2013-05-12T14:14:25.503 回答