16.6.1 カスタムPGXアルゴリズムの作成

PGXアルゴリズムは、@GraphAlgorithmを使用して注釈が付けられる単一のクラス定義を含む通常の.javaファイルです。たとえば:

import oracle.pgx.algorithm.annotations.GraphAlgorithm;

@GraphAlgorithm
public class MyAlgorithm {
    ...
}

PGXアルゴリズム・クラスには、エントリ・ポイントとして使用されるパブリック・メソッドが1つだけ含まれている必要があります。クラスには任意の数のprivateメソッドを含めることができます。

たとえば:

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

@GraphAlgorithm
public class MyAlgorithm {
    public int myAlgorithm(PgxGraph g, @Out VertexProperty<Integer> distance) {
        System.out.println("My first PGX Algorithm program!");

        return 42;
    }
}

通常のJavaメソッドと同様に、PGXアルゴリズム・メソッドは、戻り値としてプリミティブ・データ型のみをサポートします(この例では整数)。さらに興味深いのは、頂点プロパティdistanceを出力パラメータとしてマークする@Out注釈です。コール元は、出力パラメータを参照渡しします。このようにして、呼出し側は、アルゴリズムの終了後に変更されたプロパティへの参照を持ちます。

• コレクション
  
• 反復
  
• 削減
  

16.6.1.1 コレクション

コレクションを作成するには、.create()関数をコールします。たとえば、VertexProperty<Integer>は次のように作成されます。

VertexProperty<Integer> distance = VertexProperty.create();

特定の頂点vでプロパティの値を取得するには:

distance.get(v);

同様に、特定の頂点vのプロパティを値eに設定するには、次のようにします。

distance.set(v, e);

コレクションのプロパティを作成することもできます。

VertexProperty<VertexSequence> path = VertexProperty.create();

ただし、PGXアルゴリズムの割当ては常に(参照ではなく)値で行われます。これを明示的にするには、コレクションの割当て時に.clone()をコールする必要があります。

VertexSequence sequence = path.get(v).clone();

値で渡される値のもう1つの結果として、Javaメソッド.equals()ではなく、==演算子を使用して等価性をチェックできるようになりました。たとえば:

PgxVertex v1 = G.getRandomVertex();
PgxVertex v2 = G.getRandomVertex();
System.out.println(v1 == v2);

16.6.1.2 反復

PGXアルゴリズムの最も一般的な操作は、反復(すべての頂点のループ、頂点の近隣のループなど)およびグラフ・トラバーサル(幅優先/深さ優先など)です。すべてのコレクションが、forEachメソッドとforSequentialメソッドを公開します。これらのメソッドにより、コレクションはそれぞれ並列、および順に反復処理できます。

たとえば:

• グラフの頂点を並列して反復処理するには:

  G.getVertices().forEach(v -> {
      ...
  });
  

• グラフの頂点を順に反復処理するには:

  G.getVertices().forSequential(v -> {
      ...
  });
  

• グラフの頂点をrから幅優先順にトラバースするには:

  import oracle.pgx.algorithm.Traversal;
  
  Traversal.inBFS(G, r).forward(n -> {
      ...
  });
  

  forward (またはbackward)ラムダ内部では、currentLevel()をコールすることによってBFS (またはDFS)トラバーサルの現在のレベルにアクセスできます。

16.6.1.3 削減

これらの並列ブロック内では一般に、ラムダ外部に定義された変数をアトミックに更新するか、この変数まで削減します。これらのアトミック型削減は、Scalar<T>: reduceAdd、reduceMul、reduceAndなどでメソッドとして使用できます。たとえば、グラフ内の頂点の数をカウントするには、次のようにします。

public int countVertices() {
    Scalar<Integer> count = Scalar.create(0);

    G.getVertices().forEach(n -> {
        count.reduceAdd(1);
    });

    return count.get();
}

複数の値を原子的に更新する必要がある場合があります。たとえば、最小のプロパティ値と、この最小値にプロパティ値が到達した頂点を検出できます。並列実行による2つの別々の削減文のために、状態の一貫性が失われる場合があります。

この問題を解決するために、ReductionsクラスにはargMin関数とargMax関数が用意されています。argMinの最初の引数は現在の値で、2番目の引数は潜在的な新しい最小値です。また、ArgMinMaxオブジェクトに対してandUpdateコールを連鎖的に実行することにより、他の変数およびこれらの(アトミックな)更新先の値を示すことができます。たとえば:

VertexProperty<Integer> rank = VertexProperty.create();
int minRank = Integer.MAX_VALUE;
PgxVertex minVertex = PgxVertex.NONE;

G.getVertices().forEach(n ->
    argMin(minRank, rank.get(n)).andUpdate(minVertex, n)
);