저는 Py2neo를 사용하고 있습니다.하지만 이것은 아마도 Cypher 쿼리를 작성하여 수행해야하기 때문에 중요하지 않습니다.특정 에지를 제외하는 최단 경로 찾기?
본질적으로 하위 그래프는 전체 그래프의 대부분이지만 제거 된 가장자리의 아주 작은 부분 (백만 분의 1 이하) 인 하위 그래프에서 최단 경로를 찾고 싶습니다.
예를 들어 노드 A, B, C 및 가장자리 (A-> B), (A-> C), (B-> C)가 있다고 가정 해보십시오. 물론 A에서 C까지의 최단 경로는 직접 연결을 통한 경로입니다. 그러나 내가 가장 짧은 경로 인 을 찾지 않으려면이 가장자리를 사용하면 AB C가되어야합니다.
또한 사용자가 다중 사용자 (웹) 환경에서 지정할 수있는 것입니다. 신청. 그래서 나는 데이터베이스 자체를 정말로 바꿀 수 없다. 문제가되지 않는다면 가장자리에 "allow : true/false"속성을 만들고 false로 설정할 수있다. 모든 현재 사용자.
"disallow : sessionID1, sessionID230, sessionID1010"의 변형이있을 것입니다. 즉, 실제로 어떤 응용 프로그램 세션이 가장자리에서 해당 가장자리를 제외 시킬지를 저장하는 것이지만 이상적으로 보이지는 않습니다.
물론 나는 실제로는 neo4j에서 필요에 따라 노드를 가져 와서 neo4j가 검색을 수행하는 대신 대기열에 보관함으로써 Python에서 BFS를 구현할 수 있지만 확실하게 훨씬 더 느려질 것입니다.
의견이 있으십니까? 감사합니다
편집 : 코드를 보려면 요청하십시오.
다음은 현재 색인에서 처음 조회하는 두 노드 사이의 최단 경로를 얻는 방법입니다. 이제 이미지에는 최단 경로 검색에서 무시해야하는 가장자리 목록 (즉, 고유 한 관계)이 있습니다.
from py2neo import neo4j
g = neo4j.GraphDatabaseService()
def shortest_path(a, b):
a = g.get_indexed_node("worddex", "word", a)
b = g.get_indexed_node("worddex", "word", b)
if not a and b: return None
query_string = "START beginning=node(%d), end=node(%d) MATCH p = shortestPath(beginning-[*..100]-end) RETURN p" % (a._id, b._id)
result = neo4j.CypherQuery(g, query_string).execute()
if not len(result): return None
p = result[0].p
ret = []
for node in p.nodes:
ret.append(node["word"])
return ret
편집 2 : 예 콘솔 : http://console.neo4j.org/r/3c1rgn
이 가하지 않는 것을 우리가 짧은 우정 경로를 찾을하려는 경우 가장 짧은 두 사람 사이에 "우정 경로"하지만, 무엇을 쉽게 찾을 수 있습니다 특정 friendshi rel (또는 특정 친목 관계의 세트)을 포함하지만 데이터베이스를 먼저 수정하지 않아도됩니까? 예를 들어, 우리는 밥에서 조까지의 가장 짧은 우정 경로를 찾고 싶습니다. 여기서 순간적으로 밥과 조는 친구가 아니며, 앨리스와 자넷도 아닙니다.
코드를 알려주십시오. –
약간의 질문이 있습니다. 쿼리를 만들고 Neo4 엔진을 사용하여 데이터베이스에서 데이터를 그래프 구조로 가져오고 파이썬을 사용하여 분석하는 것보다 계산을 수행하는 것이 거의 확실합니다. – EdChum
@EdChum 그럴 수있다. 그래서 내 질문에, 그걸로, 어떻게 Neo4j 엔진을 사용하여 내 목표를 달성 할 수 있습니까? – user3391564