0

たとえば、MongoDB コレクションに関係グラフを作成しました。

{ "user_id": 1, "follower_id": 2 }
{ "user_id": 1, "follower_id": 3 }
{ "user_id": 2, "follower_id": 1 }
{ "user_id": 2, "follower_id": 3 }
{ "user_id": 3, "follower_id": 4 }
{ "user_id": 5, "follower_id": 2 }

これは、次のような有向グラフを表します。

ここに画像の説明を入力

グラフから「葉」を削除する効率的な方法はありますか? この例では、ノード 4 はノード 3 とのリンクが 1 つしかないため、グラフからノード 4 を削除し、ノード 2 のみがリンクしているためノード 5 を削除します。

または、グラフの用語で言うと、次数 > 1 または出次数 > 1 の頂点のみを保持します。

4

1 に答える 1

3

短い答えはノーです。このようなスキーマでやりたいことを効率的に行う方法はありません。たとえば、集約フレームワークを使用してすべてのノードを反復処理し、ノードを個別の操作として削除することもできますが、できることはそれだけだと思います。ノードがgraphコレクション内にあると仮定すると、以下のようなものになる可能性がありますが、効果的ではありません。

db.graph.aggregate(
        {$project: {index: {$const: [0, 1]}, user_id: 1, follower_id: 1}},
        {$unwind: "$index"},
        {$project: {id: {$cond: [{$eq: ["$index", 0 ]}, "$user_id", "$follower_id"]} }},
        {$group: {_id: "$id", count: {$sum: 1}}},
        {$match: {count: {$lte: 1}}}
).result.forEach(function(node) { db.graph.remove({user_id: node._id});})

このような操作を効率的にしたい場合は、よりドキュメントのようなスキーマを使用できます。

{
    user_id: 1,
    follows: [2, 3],
    followed_by: [2]
}
于 2013-11-05T14:34:17.747 に答える