JUNG와 거리 -2 이웃 찾기

Question

아주 작은 네트워크 (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 버텍스 만 잡기 위해 새로운 노드 컬렉션을 필터링해야 함을 의미합니다. 노드 집합이 "파란색"이고 다른 집합이 "빨간색"인 이분 그래프가 있습니다. 내가 여기서 일을하고 있니, 조슈아? 도와 줘서 고마워!

안부, 시몬

Answer 1

이가 KNeighborhoodFilter이 무엇이다 : 모든 알고리즘 (A *를 검색 그래프로 realted 찾을 수있는 링크 http://en.wikipedia.org/wiki/Graph_traversal에 http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.html

Answer 2

단지 더블 루프에있는 모든 이웃을 얻기의 당신의 방법은 잘입니다. 당신은 모든 이웃을 얻기 위해 정에 의지하고 있어야합니다. 만약 당신이 모든 이웃을 얻는 정의 방법에 만족하지 않는다면 1) 정을 개선하거나 2) 다른 것을 사용할 수는 있지만 그게 실제로 문제가 아닐 수 있습니다 :

당신은 매우 느린 방법으로 두번 ArrayList를 사용하여 동일한 이웃을 저장하지 않습니다 ArrayList.contains이 무엇

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

하는 것은 특정 항목, 그래서이 더 큰 당신의 twoDistNei 배열이 성장하는 것이이 경우 느리게이 방법을 포함하고 확인하는 모든 항목을 통해 단순히 루프 된다. 이를 선형 시간 알고리즘이라고합니다.이 경우 ArrayList에있는 항목의 양에 선형입니다. 동일한 효과를내는 일정 시간 알고리즘이 있지만 어레이가 얼마나 큰지 상관없이 항상 동일한 시간을 사용하십시오.

나는이 같은 ArrayList 대신 HashSet를 사용하도록 권합니다 :

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에 근거한 인덱스를 사용해 내부 배열을 구축해, 일정한 시간의 평균 성능을 달성합니다.

희망이 도움이됩니다. :)