Graph Algorithms (Green-Marl)

A key benefit of PGX is that you may implement algorithms with no limit. You can easily add your own algorithms using Green-Marl, a domain-specific language designed for graph algorithms. Green-Marl has a C-like syntax. Refer to the Built-in Algorithms section for a number of code example. For a full reference, see the Green-Marl language specification.

'Hello World' Program

To start with, we will compile and run a Green-Marl 'Hello World' program.

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
procedure hello_world() {
  println("Hello World");
}

This program can be found in the examples/gm directory of the distribution.

Creating a Session

Let's begin by creating a session:

cd $PGX_HOME
./bin/pgx-jshell
// starting the shell will create an implicit session

import oracle.pgx.api.*;

...

PgxSession session = Pgx.createSession("my-session");

Compiling the Code

Next, let's compile the 'Hello World' program:

pgx> var p = session.compileProgram("examples/gm/hello_world.gm")
==> Compiled Program hello_world

CompiledProgram p = session.compileProgram("examples/gm/hello_world.gm")

Run 'Hello World'

pgx> p.run()
Hello World
==> {
  "success" : true,
  "canceled" : false,
  "executionTimeMs" : 0,
  "exception" : null
}

AnalysisResult<Void> r = p.run();

Graph Analysis Example

As a more advanced example, we will compile the following algorithm, which computes the maximum degree of a given graph:

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

/*
* Computes the maximum out degree of a graph
*
* Input-Parameters:
* G:    arbitrary graph.
*
* Returns: maximum out degree
*
*/
procedure max_degree(G: graph): int {
  return max(n: G.nodes) { n.degree() };
}

You can find this program in the examples/gm directory of the distribution.

Compiling the Code

Compile our max_degree procedure:

pgx> var p = session.compileProgram("examples/gm/max_degree.gm")
==> Compiled Program max_degree

CompiledProgram p = session.compileProgram("examples/gm/max_degree.gm")

In PGX, every algorithm is uniquely identified by an analysis name, which equals the procedure name of the given Green-Marl program. If an algorithm with the same name already exists for this session, it will be overwritten. Note: Algorithms are session-bound, meaning session A cannot overwrite any algorithm from session B. Likewise, session A cannot execute algorithms compiled by session B.

Loading the Graph Data into Memory

Our procedure uses a graph as an input argument. In order to run our algorithm, we first need to load a graph into memory. In this tutorial, we will load the sample example graph included in the distribution.

pgx> var g = session.readGraphWithProperties("examples/graphs/connections.edge_list.json")

PgxGraph g = session.readGraphWithProperties("examples/graphs/connections.edge_list.json");

Running the Algorithm

Next, let's execute our compiled algorithm with our loaded graph as input:

pgx> p.run(g)
==> {
  "success" : true,
  "canceled" : false,
  "returnValue" : 2,
  "executionTimeMs" : 0,
  "exception" : null
}

AnalysisResult<Integer> r = p.run(g);
System.out.println("max_degree = " + r.getReturnValue());

Congratulations, you have successfully executed a custom Green-Marl algorithm.

Here is the complete Java class:

import oracle.pgx.api.CompiledProgram;
import oracle.pgx.api.Pgx;
import oracle.pgx.api.PgxGraph;
import oracle.pgx.api.PgxSession;
import oracle.pgx.api.internal.AnalysisResult;

public class CompilationExample {

  public static void main(String[] args) throws Exception {
    PgxSession session = Pgx.createSession("my-session");
    CompiledProgram maxDegree = session.compileProgram("examples/gm/max_degree.gm");
    PgxGraph graph = session.readGraphWithProperties("examples/graphs/connections.edge_list.json");
    AnalysisResult<Integer> result = maxDegree.run(graph);
    System.out.println("max_degree = " + result.getReturnValue() + " (took " + result.getExecutionTimeMs() + "ms)");
  }
}

To compile, run

cd $PGX_HOME
mkdir classes
javac -cp lib/embedded/*:lib/common/*:third-party/* -d classes examples/java/CompilationExample.java

To run it on your local machine, do

java -cp lib/embedded/*:lib/common/*:third-party/*:classes:conf CompilationExample

Persist a Compiled Algorithm into a JAR File

If you are using PGX in embedded mode, you can write a compiled algorithm into a .jar file to persist it across PGX instances by using the following APIs:

pgx> import oracle.pgx.compilers.Compilers
pgx> import oracle.pgx.compilers.GmCompilation
pgx> import oracle.pgx.compilers.Language
pgx> var gmComp = Compilers.findCompiler(Language.GM)
==> oracle.pgx.compilers.gm.GmCompiler@388b401d
pgx> var maxDegree = (GmCompilation) gmComp.compile("examples/gm/max_degree.gm", "max_degree")
==> oracle.pgx.compilers.gm.GmCompilationImpl@6573d2f7
pgx> maxDegree.writeAsJar("/tmp/max-degree.jar")

import oracle.pgx.compilers.Compilers;
import oracle.pgx.compilers.GmCompilation;
import oracle.pgx.compilers.Language;
import oracle.pgx.compilers.PgxCompiler;

...

PgxCompiler<GmCompilation> gmComp = Compilers.findCompiler(Language.GM);
GmCompilation maxDegree = gmComp.compile("examples/gm/max_degree.gm", "max_degree");
maxDegree.writeAsJar(tmpFile);

In above example, we store the compilation artifact of the code in examples/gm/max_degree.gm into a .jar file at /tmp/max-degree.jar. We also have to provide an ID for the algorithm, so we can reference it later. In this example we use max_degree as ID.

Load a Compiled Algorithm

The instructions for loading a compiled algorithm depend on whether you run PGX in local mode or remote mode.

Local Mode

If you run PGX in local mode (local shell mode or local Java mode) you need to add the generated .jar file to the PGX classpath. For the local shell mode you can add the .jar to the classpath by setting the CLASSPATH environment variable before starting the shell:

export CLASSPATH=/tmp/max-degree.jar
./bin/pgx-jshell

For local Java mode you need to add the algorithm .jar to the classpath when you run your user application. The instructions on how to do this depend on the way you run your Java application.

Remote Mode

If you run PGX in remote mode you need to add the generated .jar file to the WEB-INF/lib directory inside the .war file. The following shell commands illustrate how this is done:

cd shared-memory/server
mkdir -p WEB-INF/lib
cp /path/to/algorithm.jar WEB-INF/lib
zip -ur pgx-webapp-20.1.1.war WEB-INF/lib

Run a Compiled Algorithm

You can then retrieve the compiled algorithm by looking it up via its ID:

var maxDegree = session.getCompiledProgram("max_degree")

Green-Marl Compiler Notice

This document contains the Green-Marl language features that are part of the official language specification but are currently not supported by our Green-Marl compiler. The sections mentioned below relate to the sections in the language specification.

Foreign Syntax (Section 7.2)

Using foreign syntax statements is disabled in the current version of the compiler.

Collections of Collections (Section 4.6)

The current compiler version does support collections of type collection, but the current version of the PGX engine does not support using these types.

Properties of Collection Type (Section 4.4)

The current compiler version does support properties of collection type, but the current version of the PGX engine does not support using these types.