-1

皆さん、Hadoop で実行する必要がある map reduce パラダイムを使用して Python でアルゴリズムを作成する必要があります。

有向グラフ G = (V,E) が与えられた場合、エッジ (v,u) ∈ E は、v が u をフォローしている、または v が u を自分の友人であると宣言したため、u が v に影響を与える可能性があることを意味すると仮定します。 (ただし、必ずしもその逆であるとは限りません)。ここで、ネットワーク G = (V,E) とノード v ∈ V が与えられた場合、v から u までの長さが最大 ​​3 のパスが存在するようなすべてのノード u を見つけたいと考えています。Hadoop のアルゴリズムを設計して実装するそのようなノードをすべて見つけます。入力ファイルが各ノードの隣接リストを与えると仮定します。つまり、それらは v:u1 ,u2 ,u3 の形式です。. . ここで、v はノードで、各 ui はエッジ (v,ui ) に対応します。

map および reduce タスクを実装する方法がわかりません。

4

1 に答える 1

0

https://github.com/Yelp/mrjobをお勧めします

mrjob は、コードをパッケージ化し、ストリーミング API を処理します。map と reduce 関数を書くだけです。複数回マップ削減する必要がある場合は、複数ステップのジョブもサポートします。

あなたが説明した問題については、問題を解決するためにマルチステップのジョブを書くことができると思います。V をパラメーターとしてジョブに渡します。

  • マップ 1 - 各エッジ (a,b) に対して (a, (a,b)) および (b, (a, b) を生成
  • Reduce 1 - a で始まるエッジと a で終わるエッジのリストが表示されます。(a, [(a, c)]) と (a, [(b, a), (a, c)] の両方を生成する

これで、長さ 1 と 2 のすべてのパスができました。別の手順を繰り返して、長さ 1 から 3 のすべてのパスを取得します。最後の reduce では、v で始まらないものはすべて破棄し、すべてのパス (v, ui) を返すことができます。

于 2013-04-06T18:30:30.820 に答える