Блог

Главная - Вопросы по программированию - Найти все возможные пути между двумя узлами на графике, используя базу данных graph

Найти все возможные пути между двумя узлами на графике, используя базу данных graph

#mysql #graph #neo4j #spark-graphx

#mysql #График #neo4j #spark-graphx

Вопрос:

У меня есть коллекция узлов, которые составляют DAG (ориентированный ациклический граф) без гарантированных циклов. Я хочу сохранить узлы в базе данных и заставить базу данных выполнить поиск, который покажет мне все пути между двумя узлами.

Например, вы можете подумать, что у меня есть история git сложного проекта.

Каждый узел может быть описан с помощью объекта JSON, который имеет:

   {'id':'id',
   'outbound':['id1','id2','id3']}
  }

Итак, если бы у меня были эти узлы в базе данных:

   {'id':'id0',
   'outbound':['id1','id2']}
  }

  {'id':'id1',
   'outbound':['id2','id3','id4','id5,'id6']}
  }

  {'id':'id2',
   'outbound':['id2','id3'}
  }

И если бы я хотел знать все пути, соединяющие id0 и id3 , я бы хотел получить три списка:

    id0 -> id1 -> id3
   id0 -> id2 -> id3
   id0 -> id1 -> id2 -> id3

Сегодня у меня тысячи таких узлов, завтра у меня будут десятки тысяч. Однако в базе данных много баз данных, а типичная база данных DAG имеет только 5-10 узлов, поэтому эта проблема решаема.

Я считаю, что нет способа сделать это эффективно MySQL (прямо сейчас все объекты хранятся в таблице в столбце JSON), однако я считаю, что это можно эффективно сделать в базе данных graph, такой как Neo4j.

Я просмотрел документацию Neo4J по алгоритмам поиска путей и, возможно, я в замешательстве, но примеры на самом деле не похожи на рабочие примеры. Я нашел пример MySQL, который использует хранимые процедуры, и похоже, что он не очень хорошо распараллеливается. Я даже не уверен, что делает Amazon Neptune; Я думаю, что он использует Spark GraphX.

Я как бы не понимаю, с чего начать.

Комментарии:

1. Как вы думаете, почему найденные вами примеры на самом деле не выглядят как рабочие? Пожалуйста, поделитесь тем, что вы пробовали, потому что ваш случай кажется очень графичным.

Ответ №1:

Это вполне выполнимо с Neo4j.

Импорт данных json

 [
  {"id":"id0",
   "outbound":["id1","id2"]
  },
  {"id":"id1",
   "outbound":["id2","id3","id4","id5","id6"]
  },
  {"id":"id2",
   "outbound":["id2","id3"]
  }
]
  
 CALL apoc.load.json("graph.json") 
YIELD value
MERGE (n:Node {id: value.id})
WITH n, value.outbound AS outbound
UNWIND outbound AS o
MERGE (n2:Node {id: o}) 
MERGE (n)-[:Edge]->(n2)

введите описание изображения здесь

По-видимому, предоставленные вами данные не являются ациклическими…

Получение всех путей между двумя узлами

Поскольку вы упоминаете не кратчайшие пути, а все пути, конкретного алгоритма не требуется:

 MATCH p=(:Node {id: "id0"})-[:Edge*]->(:Node {id: "id3"}) RETURN nodes(p)
  
 "[{""id"":id0},{""id"":id1},{""id"":id3}]"
"[{""id"":id0},{""id"":id2},{""id"":id3}]"
"[{""id"":id0},{""id"":id1},{""id"":id2},{""id"":id3}]"
"[{""id"":id0},{""id"":id2},{""id"":id2},{""id"":id3}]"
"[{""id"":id0},{""id"":id1},{""id"":id2},{""id"":id2},{""id"":id3}]"

Сравнение с MySQL

Посмотрите, насколько быстрее на самом деле является графическая база данных

Ответ №2:

Алгоритмы поиска путей в библиотеке Graph Data Science предназначены для поиска кратчайших взвешенных путей и используют алгоритмы, аналогичные Дейкстре, для их поиска. В вашем случае кажется, что вы имеете дело с направленным невзвешенным графом, и вы могли бы использовать встроенную allShortestPath процедуру cypher:

Примером может быть:

 MATCH (n1:Node{id:"A"}),(n2:Node{id:"B"})
MATCH path=allShortestPaths((n1)-[*..10]->(n2))
RETURN [n in nodes(path) | n.id] as outbound_nodes_id

Всегда полезно проверить Cypher refcard, чтобы увидеть, что доступно с Cypher в Neo4j