Кодирование типа случайного блуждания в Neo4j с использованием Traversal Framework

Question

В настоящее время я работаю над графиком, где узлы связаны через вероятностные ребра. Вес на каждом ребре определяет вероятность существования ребра.

Вот пример графика, чтобы вы начали

(A)-[0.5]->(B)
(A)-[0.5]->(C)
(B)-[0.5]->(C)
(B)-[0.3]->(D)
(C)-[1.0]->(E)
(C)-[0.3]->(D)
(E)-[0.3]->(D)

Я хотел бы использовать Neo4j Traversal Framework, чтобы пройти по этому графику, начиная с (A), и вернуть количество узлов, которые были достигнуты, основываясь на вероятности найденных ребер на этом пути.

Важный:

• Каждый достигнутый узел может быть посчитан только один раз. -> Если (A) достигает (B) и (C), тогда (C) не нужно достигать (B). С другой стороны, если (A) не удается достичь (B), но достигает (C), тогда (C) попытается достичь (B).
• То же самое происходит, если (B) достигает (C), (C) не будет пытаться достичь (B) снова.
• Это функция с дискретным шагом по времени, узел будет пытаться достичь соседнего узла только один раз.
• Чтобы проверить существование ребра (пересекаем ли мы его), мы можем сгенерировать случайное число и убедиться, что оно меньше веса ребра.

Я уже закодировал часть описания обхода следующим образом. (Здесь можно начать с нескольких узлов, но это не является необходимым для решения проблемы.)

TraversalDescription traversal = db.traversalDescription()
            .breadthFirst()
            .relationships( Rels.INFLUENCES, Direction.OUTGOING )
            .uniqueness( Uniqueness.NODE_PATH )
            .uniqueness( Uniqueness.RELATIONSHIP_GLOBAL )
            .evaluator(new Evaluator() {

              @Override
              public Evaluation evaluate(Path path) {

                // Get current
                Node curNode = path.endNode();

                // If current node is the start node, it doesn't have previous relationship,
                // Just add it to result and keep traversing
                if (startNodes.contains(curNode)) {
                    return Evaluation.INCLUDE_AND_CONTINUE;
                }
                // Otherwise...
                else {
                  // Get current relationhsip
                  Relationship curRel = path.lastRelationship();

                  // Instantiate random number generator
                  Random rnd = new  Random();

                  // Get a random number (between 0 and 1)
                  double rndNum = rnd.nextDouble();


                  // relationship wc is greater than the random number
                  if (rndNum < (double)curRel.getProperty("wc")) {


                    String info = "";
                    if (curRel != null) {
                        Node prevNode = curRel.getOtherNode(curNode);
                        info += "(" + prevNode.getProperty("name") + ")-[" + curRel.getProperty("wc") + "]->";
                    }
                    info += "(" + curNode.getProperty("name") + ")";
                    info += " :" + rndNum;
                    System.out.println(info);

                    // Keep node and keep traversing
                    return Evaluation.INCLUDE_AND_CONTINUE;
                  } else {

                    // Don't save node in result and stop traversing
                    return Evaluation.EXCLUDE_AND_PRUNE;
                  }
                }
              }
            });

Я отслеживаю количество достигнутых узлов следующим образом:

long score = 0;
for (Node currentNode : traversal.traverse( nodeList ).nodes())
{
    System.out.print(" <" + currentNode.getProperty("name") + "> ");
    score += 1;
}

Проблема с этим кодом заключается в том, что, хотя NODE_PATH определен, могут быть циклы, которые я не хочу.

Поэтому я хотел бы знать:

• Есть ли решение, позволяющее избежать циклов и точно подсчитать количество достигнутых узлов?
• И в идеале, возможно (или лучше) сделать то же самое с помощью PathExpander, и если да, то как я могу заняться кодированием этого?

Спасибо

Answer 1

Это, конечно, не лучший ответ.

Вместо итерации по node () я выполняю итерации по путям и добавляю endNode() к набору, а затем просто получаю размер набора как количество уникальных узлов.

HashSet<String> nodes = new HashSet<>();
for (Path path : traversal.traverse(nodeList))
    {
        Node currNode = path.endNode();
        String val = String.valueOf(currNode.getProperty("name"));
        nodes.add(val);
        System.out.println(path);
        System.out.println("");
    }
    score = nodes.size();

Надеюсь, кто-то может предложить более оптимальное решение.

Я все еще удивлен тем, что NODE_PATH не помешал формированию циклов.