3

我正在尝试使用 neo4j 来实现 SCC 算法来存储图形。

这是我的 DFS 实现：

void dfs(GraphDatabaseService g, Node node, long counter) {

    Transaction tx = g.beginTx();
    node.setProperty("explored", true);
    tx.success();
    tx.finish();
    System.out.println("Exporing node " + node.getProperty("name") + "with depth " + counter);

    Iterator<Relationship> it = node.getRelationships(Direction.OUTGOING, RelTypes.KNOWS).iterator();
    while (it.hasNext()) {
        Node end = it.next().getEndNode();
        if (!(boolean) end.getProperty("explored"))
            dfs(g, end, ++counter);
    }  
}

它抛出 StackOverflowError。嗯，显而易见的原因是递归深度变得太大了。但也许我的代码有问题？

4

1 回答 1

4

无需编写自己的递归 DFS，因为 Neo4j 提供了开箱即用的功能。我会用以下方式重写你的方法：

void dfs(GraphDatabaseService g, Node node) {

    //neo4j provided traversal API
    TraversalDescription traversalDescription = new TraversalDescriptionImpl()
            .depthFirst()
            .relationships(RelTypes.KNOWS, Direction.OUTGOING)
            .uniqueness(Uniqueness.NODE_GLOBAL);

    Iterable<Node> nodesInComponent = traversalDescription.traverse(node).nodes();

    //uses GraphAware to save some lines of code
    new IterableInputBatchTransactionExecutor<>(g, 1000, nodesInComponent, new UnitOfWork<Node>() {
        @Override
        public void execute(GraphDatabaseService database, Node input) {
            System.out.println("Exploring node " + input.getProperty("name"));
            if (!(boolean) input.getProperty("explored", false)) {
                input.setProperty("explored", true);
            }
        }
    }).execute();
}

前四行使用纯 Neo4j API 并检索一个惰性迭代器，为您提供所需的节点。

出于性能原因，其余行以 1000 个批次而不是单独的事务写入“已探索”属性。对于 brewity，使用了GraphAware框架（免责声明：我是它的作者），但它也可以用更多几行纯 Neo4j 代码来编写。

我已经尝试了 10,000 个节点（单个连接的组件），花了大约 26 秒。

于 2013-08-08T22:52:45.123 回答