그래프의 정점에서 가장 먼 점 edu.uci.ics.jung

Question

jung implementation of directed graph에 주어진 정점에서 가장 먼 점 K를 찾고 싶습니다.

나는 BFSDistanceLabeler이 작업을 수행한다고 가정합니다. 그러나, 그것은 K 가장 먼 지점을 반환하는 API를 제공하지 않기 때문에 그래프의 모든 꼭지점을 가로 지르고 getDistance 메소드를 호출하여 수동으로해야 할 것입니다. 아니면 더 좋은 방법이 있습니까?

그러나 더 큰 도전이 있습니다. 그래프가 지시된다는 사실에도 불구하고, 나는 그것을 거리 라벨러에 대한 방향이없는 것으로 취급하고 싶다. 어떻게 든 감독 그래프에서 방향없는 버전으로 빠르게 전환 할 수 있습니까?

왜 그래프를 무향으로 처리해야합니까?

필자는 필연적 인 단계에서 매우 큰 네트워크 (정점의 수백만)를 분석합니다. 모든 단계에서 네트워크의 작은 부분 (수천 개의 정점)이 그래프로로드되고 분석됩니다. 이 분석에는 유향 그래프가 필요하며로드 된 영역의 중앙에 위치해야하는 특정 꼭지점에 대한 결과를 제공합니다.

단계 A에서 단계 B로 이동하면 이전 그래프 전체를 삭제하고 새 그래프를 만들 수 있습니다. 그럼에도 불구하고 이것은 매우 시간 소모적 일 것입니다. 새로운 관심 정점이 이전 정점에 가깝기 때문에 그래프의 큰 부분을 재사용 할 수 있습니다.

그래서 새로운 주요 정점에 가장 가까운 정점 K 개를 제거하고이 정점 주변의 새로운 정점으로 바꿔야합니다.

아래 그림을 그래프로 살펴보고 꼭지점 1이 관심의 꼭지점이라고 말할 수 있습니다. 그래프는 방향성이 있기 때문에 6 번이 가장 멀리 떨어져있다. 그러나 그래프가 방향이없는 것으로 취급되면 꼭짓점 번호 4가 가장 멀리 떨어져서 필요한 것입니다.

Answer 1

모든 정점까지의 거리를 찾는 것보다 주어진 입력 정점에서 모든 먼 정점을 찾기 위해 점근 적으로 빠른 방법이있을려고하고 있지 않다.

getVerticesInOrderVisited()을 호출하고 '꼬리'부터 역순으로 목록을 순회하여 가장 먼 꼭지점을 더 효율적으로 얻을 수 있습니다.이 목록은 루트 (집합)에서 거리가 먼 순서대로 채워 져야합니다. 각각의 거리가 감소하기 시작할 때까지 목록에서 정점을 얻습니다.

(참고 :이 완전히 당신이 "먼"로 고려할 수 있습니다 루트 정점에서 연결이 끊어 질 수 있습니다 정점 선택하지 것이다 getUnvisitedVertices() 그렇게 할 것입니다.) 두 번째 질문에 대답하기 위해

을 * : 본질적으로 당신이하고자하는 것은 지시 된 가장자리를 무향으로 취급하는 것입니다. 정은 이것을 할 수 있습니다. getSuccessors()/getPredecessors()을 사용하는 대신 getNeighbors()을 호출 할 수 있습니다.

유추했듯이 BFSDistanceLabeler은이 작업을 수행하지 않습니다. 가장자리 방향을 존중하고 싶다면 getSuccessors()을 사용합니다.

1. 사용 jung.algorithms.transformation.DirectionTransformer.toUndirected() : 그래서 여기에 몇 가지 옵션입니다.이것은 매우 간단하지만 새로운 (방향성)의 무리를 만드는 작업이 포함됩니다

2. 이 labelDistances()을 무시하고 getNeighbors()와 getSuccessors()을 대체 BFSDistanceLabeler의 서브 클래스를 작성 가장자리. 매우 우아하지는 않지만 꽤 쉽습니다.

3. getSuccessors()을 재정의하는 GraphDecorator 하위 클래스를 만들어 대리자 그래프에 getNeighbors()을 호출합니다. 그런 다음 원본 그래프가 대리자 인 하위 클래스의 인스턴스를 만듭니다. 이것은 가장 우아하고 일반적인 솔루션입니다. (우리는 당신을 위해 이렇게 유틸리티를 제공하는 그리고 어떤 시점에서 유용 할 수 있습니다하며 정 GitHub의 페이지에 문제를 제기 주시기 바랍니다 : https://github.com/jrtom/jung/issues을)이 도움이

희망.

* 나중에 참조 할 수 있도록 관련없는 질문을 별도의 StackOverflow 질문으로 나누십시오. 그것은 그들이 대답하고 찾는데 더 쉽게 만듭니다.