intersection de deux ensembles de noeuds (Neo4j Cypher de chemin de traversée)

Question

je un graphique de 100000 noeuds connectés les uns aux autres par une relation. D'un point A à un point B, il n'y a qu'un seul chemin possible, aucune boucle n'est possible dans mon modèle.

Je suis à la recherche d'une solution qui indiquera si le chemin d'une liste de noeuds croise le chemin d'une seconde liste de noeuds

Je ne ai pas besoin de connaître les points d'intersection s'il y a une intersection.

Serait-il possible d'avoir une solution sans passer par le graphe entier (arrêt une fois que le premier noeud est trouvé)?

exemple: picture of graph

liste des nœuds 1: nœuds rouges

liste

de noeuds 2: des noeuds bleu

Comme il y a au moins une intersection (noeud noir), la demande doit retourner true .

demande Cypher:

EDIT: Demande Cypher

match path=shortestPath((n1)-[r*]-(n2)) 
where id(n1) = node1 and id(n2) in nodesList1 
with nodes(path) as nodespath1 

match path=shortestPath((n1)-[r*]-(n2)) 
where id(n1) = node2 and id(n2) in nodesList2 
with nodespath1, nodes(path) as nodespath2 

with ANY (n IN nodespath1 WHERE n IN nodespath2) AS conflit 
with ANY (n IN collect(conflit) WHERE n = true) AS conflit 
RETURN conflit; 

Answer 1

Comme il n'y a qu'un seul chemin possible entre une paire de noeuds, je pense que votre graphique est un arbre, et vous pouvez choisir un noeud arbitraire être la racine de cet arbre. Une fois que vous avez fait cela, le travail de pré-traitement linéaire vous permet de répondre aux plus basses requêtes d'ancêtres communs en temps constant, et le chemin entre deux nœuds consiste en un chemin ascendant de l'arbre jusqu'à leur ancêtre commun le plus bas, suivi par un chemin descendant l'arbre. Appelons ce pic - l'ancêtre commun le plus bas des deux extrémités du chemin - l'ancêtre commun le plus bas du chemin. Si un nœud unique N est sur un chemin, l'ancêtre commun le plus bas de ce nœud et l'ancêtre commun le plus bas de ce chemin est l'ancêtre commun le plus bas du chemin, et l'ancêtre commun le plus bas de ce nœud et l'un des Le noeud N se trouve quelque part entre l'ancêtre commun le plus bas du chemin et l'une des extrémités du chemin, il est donc sur le chemin - et vous avez trouvé ceci en O (1) temps.

Si deux chemins se croisent, le chemin avec l'ancêtre commun le plus bas doit avoir cet ancêtre sur l'autre chemin, ou il doit être entièrement sous l'autre chemin - et le paragraphe ci-dessus montre comment travailler dans le temps O (1) si un nœud arbitraire est sur un chemin, nous pouvons donc vérifier les intersections de chemin en cherchant à voir si l'ancêtre commun le plus bas de l'un ou l'autre chemin est sur l'autre chemin.

Answer 2

Pour consolider un ensemble de chemins dans un pool de nœuds, vous pouvez utiliser UNWIND n + Collect (DISTINCT n). Voici comment vous ajusteriez votre exemple de requête.

match path=shortestPath((n1)-[r*]-(n2)) 
where id(n1) = node1 and id(n2) in nodesList1 
UNWIND nodes(path) as nodespath1 
WITH collect(DISTINCT nodespath1) as nodespath1 

match path=shortestPath((n1)-[r*]-(n2)) 
where id(n1) = node2 and id(n2) in nodesList2 
UNWIND nodes(path) as nodespath2 
WITH nodespath1, collect(DISTINCT nodespath2) as nodespath2 

with ANY (n IN nodespath1 WHERE n IN nodespath2) AS conflict 
RETURN conflict; 

Bien sûr, dans votre cas, si les chemins se croisent, puis un chemin existe d'un rouge à un rouge et un bleu. Jusqu'à présent plus simplement

MATCH (a), (b) 
WHERE id(a) in nodesList1 AND id(b) in nodesList2 
// Match a c node in path to an a and a b node 
MATCH (a)-[*]-(c)-[*]-(a2), (b)-[*]-(c)-[*]-(b2) 
WHERE id(a2) in nodesList1 AND id(b2) in nodesList2 
WITH c 
LIMIT 1 
RETURN (COUNT(c) == 1) as conflict