用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的鄰居

回答

相關問題