패턴

Question

I 지향 그래프에 지정된 패턴에 대응하는 부분, 예를 검색하는 도구/알고리즘을 찾기 위해 시도하고있다 :

A-> B-> C 또는 A 또는 < -> B-> C

내 검색 방향을 제안 해주세요.

나는 패턴 매칭을 의미합니다. 노드와 모서리의 모든 그룹을 찾을 필요가 있습니다. 지정된 패턴과 일치합니다.

Answer 1

Subgraph isomorphism problem이 아닌가요? 그렇다면 Wikipedia 페이지에 알고리즘에 대한 섹션이 있습니다.

Answer 2

가능한 라이브러리는 Python Graph Library입니다.

패턴 일치의 경우 검색중인 패턴을 알고 있으면 그래프를 탐색하고 경로를 비교하기 만하면됩니다. 또는 함수를 사용하여 노드 사이의 경로를 검색하고 패턴이 존재하는지 확인할 수 있습니다 .

Answer 3

그래프 패턴 매칭은 graph rewrite tools 코어의 기능으로 사전 구현되어 있습니다.

예 : GrGen을 사용하면 예제 패턴을 a -> b : B -> c : C로 기록한 다음 호스트 패턴의 특성에 맞게 패턴 매처를 생성합니다 (통계를 취하여 최적화 됨) 그래프에 대한 설명).