방향성 그래프를 저장/액세스하는 가장 좋은 방법

StackOverflow https://stackoverflow.com/questions/191897

문제

흐름 경로(기본적으로 방향성 그래프)를 결정하기 위해 네트워크로 표현하고 싶은 약 3500개의 홍수 통제 시설이 있습니다.저는 현재 SqlServer와 CTE를 사용하여 모든 노드와 해당 업스트림 구성 요소를 재귀적으로 검사하고 있으며 업스트림 경로가 많이 분기되지 않는 한 이는 작동합니다.그러나 일부 쿼리는 경로에서 물리적으로 훨씬 더 멀지 않은 경우에도 다른 쿼리보다 기하급수적으로 더 오래 걸립니다(예:2개 또는 3개의 세그먼트 "다운스트림") 추가된 업스트림 복잡성으로 인해;어떤 경우에는 쿼리를 종료하기 전에 10분 이상 기다리기도 했습니다.저는 간단한 2열 테이블을 사용하고 있습니다. 한 열은 시설 자체이고 다른 열은 첫 번째 열에 나열된 시설의 업스트림 시설입니다.

작업 속도를 높이기 위해 현재 기능을 사용하여 색인을 추가하려고 시도했지만 아무런 차이가 없었습니다.그리고 그래프에서 가능한 연결의 경우 모든 노드는 여러 개의 업스트림 연결을 가질 수 있으며 여러 "다운스트림" 노드에서 연결될 수 있습니다.

데이터에 주기가 있을 가능성이 있지만 이를 확인할 수 있는 좋은 방법을 아직 찾지 못했습니다(CTE 쿼리가 최대 재귀 횟수 적중을 보고한 경우 제외).그건 고치기 쉬웠어요).

그래서 제 질문은 '내가 이 정보를 잘못 저장하고 있는 걸까요?'입니다.업스트림 지점을 쿼리하는 데 CTE 외에 더 좋은 방법이 있습니까?

도움이 되었습니까?

해결책

나는 홍수 통제 시설에 대해 아무것도 모른다. 그러나 나는 첫 번째 시설을 차지할 것입니다. 임시 테이블과 타운 루프를 사용하여 경로를 생성하십시오.

-- Pseudo Code
TempTable (LastNode, CurrentNode, N)



@intn int set @intn = 1을 선언합니다



유혹 가능한 (LastNode, CurrentNode, N)에 삽입 - 스트림이없는 항목이없는 목록에 첫 번째 항목을 삽입하십시오 ...이 초기 조건을 호출하십시오. LastNode, CurrentNode, @Intn은 노드가 상류가없는 테이블에서 @intn



@Intn <= 3500 시작 Set @Intn = @Intn + 1 유혹에 삽입 (lastNode, currentNode, n) LastNode, CurrentNode, @Intn은 마지막으로 삽입하여 (n = @intn-1에서 temptable에서 currentNode를 선택하십시오. )



IF @@ROWCOUNT = 0
     BREAK




끝

우리가 모든 노드가 한 아이를 가리킨다고 가정하면. 그러면 3500 개 이상의 반복이 필요하지 않아야합니다. 여러 노드에 동일한 업스트림 공급자가 있으면 더 적은 시간이 걸립니다. 그러나 더 중요한 것은 이렇게 할 수 있습니다 ...

LastNode, CurrentNode, N을 선택하여 N에서 유혹 가능한 순서에서 N을 선택하십시오.

그리고이를 통해 제공자에게 루프 나 다른 문제가 있는지 확인할 수 있습니다. 우연히 3500 행은 그다지 많지 않기 때문에 각 공급자가 다른 업스트림 제공 업체를 가리키는 최악의 경우에도 그렇게 오래 걸리지 않아야합니다.

다른 팁

그래프를 저장하는 가장 좋은 방법은 물론 기본 그래프 DB를 사용하는 것입니다 :-)

보세요 neo4j. Java로 구현되었으며 파이썬과 루비 바인딩도 있습니다.

NEO4J를 사용하여 그래프로 표시되는 도메인 모델의 간단한 예제와 함께 두 개의 위키 페이지를 작성했습니다. 집회 그리고 역할. 더 많은 예제가 있습니다 도메인 모델링 갤러리 페이지.

전통적으로 그래프는 행렬 또는 벡터로 표시됩니다. 매트릭스는 더 많은 공간을 차지하지만 처리하기가 더 쉽습니다 (경우 3500x3500 항목). 벡터는 공간이 줄어 듭니다 (3500 개의 항목, 각각 연결 대상 목록이 있습니다).

그것이 당신을 도와 주나요?

데이터 구조가 정상이라고 생각하지만 (SQL Server의 경우) CTE가 쿼리에 가장 효율적인 솔루션이 아닐 수도 있습니다. 임시 테이블을 대기열로 사용하여 그래프를 통과하는 저장된 절차를 시도 할 수 있습니다. 대신 더 효율적이어야합니다.

임시 테이블은 그래프의 사이클을 제거하는 데 사용될 수 있지만

예(아마도).데이터 세트가 비교적 작은 것처럼 들리면 그래프를 인접 행렬 또는 인접 목록으로 메모리에 로드하고 그래프를 직접 쿼리할 수 있습니다. 프로그래밍을 가정합니다.

온디스크 포맷의 경우, 점 다른 사람들 사이에서 상당히 휴대 가능하고 인기가 있습니다.또한 다음과 같은 플랫 파일 형식으로 가장자리 목록을 저장하는 것이 매우 일반적입니다.

vertex1 vertex2 {edge_label1}+

파일의 첫 번째 줄에는 그래프의 정점 수가 포함되고 그 뒤의 모든 줄은 가장자리를 설명합니다.가장자리의 방향이 지정되거나 지정되지 않는지 여부는 구현자에게 달려 있습니다.명시적인 방향성 가장자리를 원하는 경우 다음과 같은 방향성 가장자리를 사용하여 설명하십시오.

vertex1 vertex2
vertex2 vertex1

SQL Server 데이터베이스에 설명 된 것과 같은 저장 경험 :

나는 거리 매트릭스를 저장하면서 지점에서 지점 B로 이동하는 데 얼마나 걸립니까? 순진한 표현을했고 열 A, B, 거리, 시간이있는 거리가 부르는 테이블에 직접 저장했습니다.

이것은 간단한 Retreival에서 매우 느립니다. 전체 매트릭스를 텍스트로 저장하는 것이 훨씬 낫다는 것을 알았습니다. 그런 다음 계산하기 전에 메모리로 리 레드를 다시 작성하고 메모리에 행렬 스트루 텍스트를 만들고 작업하여 작업하십시오.

코드를 제공 할 수는 있지만 C#입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top