用JUNG找到距离为2的邻居

我想找到距离为2的所有节点的邻居，以获得不太小的网络（5000个节点和25k个无向边）。现在我正在使用：用JUNG找到距离为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？感谢您的帮助！

最好的问候，西蒙娜

来源

2013-05-12 user299791

此链接http://en.wikipedia.org/wiki/Graph_traversal上，你可以找到所有的算法realted以图搜索（A *，breadfirst，dikistra等等） – qwr 2013-05-12 13:44:03

这是KNeighborhoodFilter是什么： http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.html

来源

2013-05-12 18:07:30

非常感谢指针！ – user299791 2013-05-13 08:48:59

你碰巧有一个指向这个工作原理的代码示例吗？ – user299791 2013-05-13 09:21:39

http://logic.cse.unt.edu/tarau/teaching/GraphTheory/jung/src/jung2/jung-algorithms/src/test/java/edu/uci/ics/jung/algorithms/filters/impl/TestKNeighborhoodFilter的.java – 2013-05-15 22:55:39

你刚开所有的邻居在双循环方法就好了。你是，应该依靠荣格为你获得所有的邻居。如果你不满意荣格所有邻居的方法，你可以1）改善荣格或2）使用别的东西，但我怀疑这实际上是问题：

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

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

ArrayList.contains做什么是简单地遍历所有条目，以检查它是否有一个特定的项目，所以你大阵twoDistNei增长较慢的contains方法变。这被称为线性时间算法，因此在这种情况下，与ArrayList中的项目数量成线性关系。有恒定的时间算法可以达到同样的效果，但无论数组的大小如何，总是需要相同的时间。

我会建议你使用HashSet代替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-12 14:14:25

非常感谢你，我接受了@Joshua的回复，但感谢你教我关于HashSet！ – user299791 2013-05-13 08:48:35

用JUNG找到距离为2的邻居

回答

相关问题