1

我目前正在研究一个节点通过概率边连接的图。每条边上的权重定义了边存在的概率。

这是一个示例图，可帮助您入门

(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 做同样的事情，如果可以，我该如何进行编码？

谢谢

4

1 回答 1

1

这当然不是最好的答案。

我不是在 nodes() 上迭代，而是在路径上迭代，并将 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 并没有阻止循环的形成，但我仍然感到惊讶。

于 2018-03-22T13:05:55.590 回答