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

Neo4j はすぐに使用できるため、独自の再帰 DFS を作成する必要はありません。メソッドを次のように書き直します。

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();
}

最初の 4 行は、純粋な Neo4j API を使用し、必要なノードを取得する遅延イテラブルを取得します。

残りの行は、パフォーマンス上の理由から、個別のトランザクションではなく、1000 のバッチで「探索された」プロパティを書き込みます。brewity の場合、GraphAwareフレームワークが使用されます (免責事項: 私はその作成者です) が、純粋な Neo4j コードを数行追加するだけで十分に記述できます。

10,000 ノード (単一の接続されたコンポーネント) で試しましたが、約 26 秒かかりました。

于 2013-08-08T22:52:45.123 に答える