# GraphIt

A high-performance graph domain specific language

Getting Started

Language Manual

Publications

Mailing List

# The GraphIt Programming Language

This guide introduces GraphIt language features and shows how they can be used in programs.

# Basics

GraphIt is an imperative language with statements, control flow, and high-level operators on sts of vertices ane edges. In this section, we describe some of the language’s basic constructs.

## Functions

Functions can take any number of parameters, including none. Each parameter must be declared with its name followed by its type (separated by a `:`). In the following example, the function `add` takes two parameters named `a` and `b`, both of which are of type `float`, and returns a single result (named `c`) that is also a `float`. The function result is separated from the list of parameters by a `->` and the function declaration is delimited by the `end` keyword.

``````func add(a : float, b : float) -> c : float
c = a + b;
end
``````

Like functions in MATLAB, GraphIt functions can return any number of results, including none. In the next example, the function `minMax` takes two `float` parameters and return two `float` results: the smaller of the two inputs as the first result and the larger of the two inputs as the second result.

``````func minMax(a : float, b : float)
-> (c : float, d : float)
if a < b
c = a;
d = b;
else
c = b;
d = a;
end
end
``````

Note that the list of function results must be surrounded by parentheses if the function returns more than one result. (The parentheses are optional if the function returns just a single result.)

## Variables

Variables are declared in function bodies or in the global scope using the `var` keyword. The following example declares an integer variable named `foo`:

``````var foo : int;
``````

The variable can be initialized with the following syntax.

``````var foo : float = 0.0;
``````

The `const` keyword creates a variable that cannot be modified after initialization. Individual elements of const vectors can still be updated.

Single-line comments start with `%`:

``````h = 0.01;  % h is the time-step size.
``````

Multi-line comments are surrounded by `%{` and `%}`:

``````%{
h is the time-step size.
h is initialized to one millisecond.
%}
h = 0.001;
``````

# Control Flow Statements

GraphIt supports a variety of control flow constructs, including `if` statements, `while` loops, `do`-`while` loops and `for` loops.

## If Statements

In GraphIt, a simple `if` statement looks something like this:

``````if x < 1
print "x is less than 1";
end
``````

An `if` statement can optionally include an `else` clause as well as an any number of `elif` (else-if) clauses:

``````if x < 1
print "x is less than 1";
elif x > 5
print "x is greater than 5";
else
print "x is between 1 and 5";
end
``````

## While Loops

A `while` loop in GraphIt looks like this:

``````while x < 100
x = 2 * x;
end
``````

As with `if` statements, logical operators and comparison operators can be used to construct more complex conditions. Note that if the condition of a `while` loop is false when a GraphIt program first encounters the loop, the loop body will not be executed at all.

## For Loops

GraphIt `for` loops are more like those found in MATLAB, Julia and Python than those available in C. You can use a `for` loop to iterate over the set of all integers between two values, as shown in the following example.

``````for i in 0:10
print i;
end
``````

Note that the lower bound is inclusive while the upper bound is exclusive (like Python), so the above example prints all integers between 0 and 9 but omits 10.

# Elements, Vectors, VertexSets, EdgeSets

Elements, vertexsets, edgesets and vectors form GraphIt’s data model.

## Elements

An element is a type that stores one or more data fields, much like a struct in C/C++. For example, a vertex in a social network representing a person can have a Person Element type. In the future, we plan to support fields in the Element. Currently, fields associated with an Element are expressed as separate Vectors descrived below.

``````element Person
end
``````

## Vectors

Vectors are associated with an element. Essentially they act as fields of the elements. The following code says that `age` is a vector for `Person` Element type. Each Person would have an associated age field, and the field is initialized to 0.

``````const age : vector {Person}(int) = 0;

``````

## Edgesets

Edgesets are have connectivity information. In particular, edge set definitions specify the type of elements from which each edge’s endpoints come. The following declares a set of spring elements that each connect two points from the `edges` set:

``````const edges : edgeset{Follow}(Person,Person);
``````

There is no explicit graph type in GraphIt; rather, graphs are formed implicitly from the edgesets. This is similar to how graphs are often defined in mathematical papers (i.e. as an ordered pair `G = (V,E)`).

## Vertexsets

Vertexsets are sets of vertices of a specific Element Type. `people` is a vertexset made up of endpoint elements of Person Type from the `edges` edgeset.

``````const people : vertexset{Person} = edges.getVertices();

``````

# Set Opeartors

## Edgeset Operators

### from, to and filter

`from` and `to` Filters out edges whose source vertex is in the input set.

``````const people_age_over_40 : vertexset{Person} = ...
const people_age_over_60 : vertexset{Person} = ...

func main()
...
% find edges between people over 40 years old to people over 60 years old
var filtered_edges : edgeset{Friend}(Person, Person} =
friend_edges.from(people_age_over_40).to(people_age_over_60);
end

``````

`filter` simply supplies a boolean function that checks every edge.

### srcFilter and dstFilter

`srcFilter` and `dstFilter` filters out edges where the input boolean filtering function `filter_func` returns true.

``````func filter_func(v : Vertex) -> output : bool
output =  age[v] > 40;
end

func main()
...
filtered_edges = edges.srcFilter(filter_func);
...
end

``````

### apply

This operator applies a function `updateEdge ` to every edge. In one iteration of PageRank,

``````func updateEdge(src : Vertex, dst : Vertex)
new_rank[dst] += contrib[src];
end

func main()
...
edges.apply(updateEdge);
...
end
``````

### applyModified

This operator applies a function (`updateEdge`) to every edge. Returns a vertexset that contains destination vertices whose entry in the vector has been modified in `updateEdge`. The programmer can optionally disable deduplication within modfieid vertices. Deduplication is enabled by default.

``````func updateEdge(src : Vertex, dst : Vertex)
parent[dst] = src;
end

func main()
...
edges.applyModified(updateEdge,parent, true);
...
end

``````

### combining edgeset operators

The various operators can be and often are chained together.

``````frontier = edges.from(frontier).to(toFilter).applyModified(updateEdge,parent, true);

``````

## Vertexset Operators

### filter

The filter operator is similar to the edgeset filter, except for it is applied on a single vertex and not edge.

### apply

The apply operator is similar to the edgeset apply operator, but applied to a vertex.

# Scheduling Language

For now, we refer users to the Section 5 of the arxiv report on how to use the scheduling language.