Как работает Минимальное связующее дерево в neo4j

Question

Я играю с некоторыми алгоритмами теории графов в neo4j. Я пытаюсь найти минимальное связующее дерево (MST) в моей сети. Я синтетически создал сеть из 10 000 человек. У каждого человека есть 12 типов отношений, каждый из которых связывает его с другим 9999, и у каждого отношения свой собственный вес.

Однако проблема, с которой я столкнулся, заключается в том, что в соответствии с определением результаты должны представлять собой дерево, охватывающее ВСЮ сеть. Функция neo4j, однако, возвращает только очень маленький подграф (всего около 12 узлов) всей сети.

Код, который я использую, выглядит следующим образом:

MATCH (a:Name {Name:"Dillon Snow"})
CALL algo.mst(a,"Weight",{stats:true})
YIELD loadMillis, computeMillis, writeMillis, weightSum, weightMin, weightMax, relationshipCount
RETURN loadMillis, computeMillis, writeMillis, weightSum, weightMin, weightMax, relationshipCount

Что я могу изменить, чтобы заставить функцию возвращать mst, распространяющуюся по всей сети

Answer 1

algo.mst.* не был адаптирован к зрелому Neo4j-Graph-Algorithms-CoreAPI в своем текущем выпуске (3.2.5.2/3.3.0.0 @ Dec 2017), что может привести к неожиданным результатам. Но в канале есть запрос на удаление, вы можете ожидать некоторые изменения в следующем выпуске.

Во всяком случае.. Процедура должна добавить новый тип отношения (по умолчанию mst) к вашим узлам. В связанном графе каждый узел также должен быть связан, в то время как отключенный граф приводит к соединениям только между узлами этого конкретного подключенного компонента (из вашего startNode).

Если я правильно вас понял, у вас есть несколько типов отношений и более одного из них между парой узлов? Например, узел A связан с узлом B несколькими отношениями, каждое из которых имеет свой тип и значение свойства. Это проблема. В общем случае Graph-Algorithms-API не поддерживает многократные версии. Каждая пара узлов может иметь только одно соединение в каждом направлении. Хотя вы можете импортировать многократные типы, само ядро-API не имеет представления о базовом типе. Если многоплановые отношения между парой узлов импортируются, как правило, выигрывает последний. Это было упомянуто в документации;)

Чтобы преодолеть это ограничение, вы можете заменить свои типы отношений на какие-то искусственные узлы. При обходе результирующего дерева появление одного из этих узлов будет указывать на исходную связь.