GraphAlg

https://github.com/wildarch/graphalg
Admin
GraphAlg is an embeddable language for writing graph algorithms using linear algebra, designed to be...
Tokens:21,331
Snippets:211
Trust Score:6.9
License:MIT
Update:6 months ago
Show doc for...
Tokens:
Raw
### Initialize and Serve Jekyll Project

Source: https://github.com/wildarch/graphalg/blob/main/docs/jekyll.md

Installs project-specific dependencies via Bundler and starts the Jekyll local development server. This should be executed from the root directory of the site.

```bash
bundle install
bundle exec jekyll serve
```

--------------------------------

### Install Jekyll and Ruby Dependencies

Source: https://github.com/wildarch/graphalg/blob/main/docs/jekyll.md

Installs the necessary Ruby development environment and Jekyll gem on an Ubuntu system. It also configures the environment variables to manage gems in the user home directory.

```bash
sudo apt-get install ruby-full build-essential zlib1g-dev
echo '# Install Ruby Gems to ~/gems' >> ~/.bashrc
echo 'export GEM_HOME="$HOME/gems"' >> ~/.bashrc
echo 'export PATH="$HOME/gems/bin:$PATH"' >> ~/.bashrc
source ~/.bashrc
gem install jekyll bundler
```

--------------------------------

### Setup and Run Parser Fuzzing (Bash)

Source: https://github.com/wildarch/graphalg/blob/main/docs/fuzzing.md

This snippet demonstrates how to prepare a corpus directory with parser test files, build the fuzzing target using CMake, and then execute the fuzz-parser tool with custom options for maximum length, job count, and ASCII-only input.

```bash
export CORPUS_DIR=<some path>
mkdir $CORPUS_DIR
cp compiler/test/parse/*.gr $CORPUS_DIR/
cp compiler/test/parse-err/*.gr $CORPUS_DIR/

./compiler/configure.sh
cmake --build ./compiler/build --target fuzz-parser
./compiler/build/tools/fuzz-parser $CORPUS_DIR -max_len=1000 -jobs=8 -only_ascii=1
```

--------------------------------

### Build and Push Docker Images

Source: https://github.com/wildarch/graphalg/blob/main/docker/README.md

Commands to build and push the GraphAlg development and CI Docker images to the GitHub Container Registry. These commands require Docker to be installed and authenticated with the registry.

```bash
docker build -t ghcr.io/wildarch/graphalg docker/
docker push ghcr.io/wildarch/graphalg

docker build -t ghcr.io/wildarch/graphalg-ci docker/ -f docker/ci.Dockerfile
docker push ghcr.io/wildarch/graphalg-ci
```

--------------------------------

### ConstantMatrixOp: Create Constant Matrix

Source: https://github.com/wildarch/graphalg/blob/main/spec/core/relalg.md

Generates a matrix where all elements have a specified constant value. The example shows a matrix with all values set to 42.

```Conceptual
(row, col, val)
(0, 0, 42)
(0, 1, 42)
(0, 2, 42)
...
(1, 0, 42)
(1, 1, 42)
(1, 2, 42)
...
```

--------------------------------

### Get Number of Columns (ncols)

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Retrieves the number of columns from a given matrix 'a'. This is a property accessor for matrix dimensions.

```Go
func ncols(a: Matrix<s, s, int>) -> int {
  return a.ncols;
}
```

--------------------------------

### Test Duplicate Function Definitions

Source: https://github.com/wildarch/graphalg/blob/main/docs/parse-tests.md

Example of testing for duplicate function name errors, ensuring the compiler correctly identifies the original definition and the subsequent conflict.

```graphalg
// expected-note@below{{original definition here}}
func Dup(a: int) -> int { return a; }

// expected-error@below{{duplicate definition of function 'Dup'}}
func Dup(a: int) -> int { return a; }
```

--------------------------------

### GraphAlg Matrix Accumulation

Source: https://github.com/wildarch/graphalg/blob/main/tutorial/index.md

Demonstrates accumulating results by adding two matrices element-wise. The behavior of the `+=` operator depends on the semiring type of the matrix elements. This example uses integer matrices.

```graphalg
func Accumulate(
        a: Matrix<s, s, int>,
        b: Matrix<s, s, int>) -> Matrix<s, s, int> {
    // EXPERIMENT: Try the equivalent statement:
    // a = a (.+) b;
    a += b;
    return a;
}
```

--------------------------------

### Invalid Matrix Multiplication Example

Source: https://github.com/wildarch/graphalg/blob/main/tutorial/index.md

Demonstrates a function that fails dimension validation in GraphAlg. The compiler checks that the number of columns in the left matrix matches the rows in the right matrix.

```graphalg
func InvalidDimensions(
        a: Matrix<s, t, int>,
        b: Matrix<u, t, int>) -> Matrix<s, t, int> {
    return a * b;
}
```

--------------------------------

### Apply Functions in Graphalg

Source: https://context7.com/wildarch/graphalg/llms.txt

Applies a scalar function to each element of a matrix. For binary functions, the second argument is broadcast. The `BFS` example demonstrates applying a custom function `setDepth` within a loop to update node depths.

```graphalg
func square(x: int) -> int {
    return x * x;
}

func ApplyUnary(m: Matrix<s, s, int>) -> Matrix<s, s, int> {
    // Apply unary function to each element
    return apply(square, m);
}

func addConstant(x: int, c: int) -> int {
    return x + c;
}

func ApplyBinary(m: Matrix<s, s, int>) -> Matrix<s, s, int> {
    // Apply binary function: first arg from matrix, second broadcast
    return apply(addConstant, m, int(10));
}

// Set BFS depth based on iteration
func setDepth(found: bool, iter: int) -> int {
    return cast<int>(found) * (iter + int(2));
}

func BFS(graph: Matrix<s, s, bool>, source: Vector<s, bool>) -> Vector<s, int> {
    depth = Vector<int>(graph.nrows);
    depth<source>[:] = int(1);

    frontier = source;
    reach = source;

    for i in graph.nrows {
        step = Vector<bool>(graph.nrows);
        step<!reach> = frontier * graph;

        // Set depth for newly discovered nodes
        depth += apply(setDepth, step, i);

        frontier = step;
        reach += step;
    } until frontier.nvals == int(0);

    return depth;
}
```

--------------------------------

### Project and Basic Configuration (CMake)

Source: https://github.com/wildarch/graphalg/blob/main/compiler/CMakeLists.txt

Initializes the CMake build system, setting the minimum required version, project name, version, description, and primary language (C++).

```cmake
cmake_minimum_required(VERSION 3.15...4.0)

project(
    GraphAlgCompiler
    VERSION 0.1
    DESCRIPTION "Compiler for the GraphAlg language"
    LANGUAGES CXX)
```

--------------------------------

### Get Number of Rows (nrows)

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Retrieves the number of rows from a given matrix 'a'. This is a property accessor for matrix dimensions.

```Go
func nrows(a: Matrix<s, s, int>) -> int {
  return a.nrows;
}
```

--------------------------------

### Configure CMake Project and Fetch Dependencies

Source: https://github.com/wildarch/graphalg/blob/main/playground/cpp/CMakeLists.txt

Initializes the CMake project with versioning and language settings. It uses FetchContent to include the local GraphAlg source directory as a dependency.

```cmake
cmake_minimum_required(VERSION 3.15...4.0)

project(
    GraphAlgPlayground
    VERSION 0.1
    DESCRIPTION "GraphAlg Playground - WASM side"
    LANGUAGES CXX)

include(FetchContent)
FetchContent_Declare(
  GraphAlg
  SOURCE_DIR ../../../compiler
)
FetchContent_MakeAvailable(GraphAlg)
```

--------------------------------

### Get One Value

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Returns the multiplicative identity (one) for a specified integer type. This function invokes the `one` built-in.

```Go
func oneVal() -> int {
  return one(int);
}
```

--------------------------------

### Get Zero Value

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Returns the additive identity (zero) for a specified integer type. This function calls the `zero` built-in.

```Go
func zeroVal() -> int {
  return zero(int);
}
```

--------------------------------

### Compile GraphAlg Source Code

Source: https://context7.com/wildarch/graphalg/llms.txt

Demonstrates the command-line workflow for parsing GraphAlg source into MLIR and optimizing it for specific dimensions.

```bash
graphalg-translate --import-graphalg < input.gr > parsed.mlir
graphalg-opt --graphalg-to-core-pipeline --graphalg-set-dimensions='func=SSSP args=10x10,10x1' parsed.mlir > exec.mlir
```

--------------------------------

### Get Number of Non-Zero Values (nvals)

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Retrieves the count of non-zero elements within a given matrix 'a'. Useful for sparse matrix analysis.

```Go
func nvals(a: Matrix<s, s, int>) -> int {
  return a.nvals;
}
```

--------------------------------

### Matrix and Vector Broadcasting

Source: https://context7.com/wildarch/graphalg/llms.txt

Shows how to fill matrices and vectors with scalar values or uniform distributions, useful for initialization tasks.

```graphalg
func FillMatrix(m: Matrix<s, s, int>, value: int) -> Matrix<s, s, int> {
    m[:, :] = value;
    return m;
}

func FillVector(v: Vector<s, int>, value: int) -> Vector<s, int> {
    v[:] = value;
    return v;
}

func InitializePageRank(graph: Matrix<s, s, bool>) -> Vector<s, real> {
    n = graph.nrows;
    pr = Vector<real>(n);
    pr[:] = real(1.0) / cast<real>(n);
    return pr;
}
```

--------------------------------

### Execute Parser Tests via CLI

Source: https://github.com/wildarch/graphalg/blob/main/docs/parse-tests.md

Provides command-line instructions for building the compiler and running individual parser tests with or without diagnostic verification.

```bash
# Run all tests
cmake --build compiler/build --target check

# Run individual test with diagnostic verification
./compiler/build/tools/graphalg-translate --import-graphalg --verify-diagnostics path/to/test.gr

# Run without verification to see actual errors
./compiler/build/tools/graphalg-translate --import-graphalg path/to/test.gr
```

--------------------------------

### Demonstrate Invalid Variable Scoping

Source: https://github.com/wildarch/graphalg/blob/main/tutorial/index.md

An example of code that fails to compile because it attempts to return a variable defined within a nested loop scope from an outer function scope.

```graphalg
func NotValid() -> int {
    a = int(0);
    for i in int(0):int(10) {
        b = a;
        a = a + int(1);
    }
    return b;
}
```

--------------------------------

### Graph Utility Operations

Source: https://context7.com/wildarch/graphalg/llms.txt

Demonstrates diagonal matrix creation and the pickAny selection function, applied here to a Weakly Connected Components algorithm.

```graphalg
func DiagExample(v: Vector<s, int>) -> Matrix<s, s, int> {
    return diag(v);
}

func PickAnyExample(m: Matrix<s, s, int>) -> Matrix<s, s, int> {
    return pickAny(m);
}

func WCC(graph: Matrix<s, s, bool>) -> Matrix<s, s, bool> {
    id = Vector<bool>(graph.nrows);
    id[:] = bool(true);
    label = diag(id);
    for i in graph.nrows {
        alternatives = label;
        alternatives += graph * label;
        alternatives += graph.T * label;
        label = pickAny(alternatives);
    }
    return label;
}
```

--------------------------------

### ApplyOp: Join and Project Inputs

Source: https://github.com/wildarch/graphalg/blob/main/spec/core/relalg.md

Joins all input tables based on available columns, broadcasting dimensions if necessary. It then creates a projection, keeping only the required output columns and rows.

--------------------------------

### Function Definition with Two Parameters

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Defines a function that accepts two integer parameters and returns an integer. Shows how to declare multiple parameters.

```Go
func OneParam(i:int, j:int) -> int {
  return int(42);
}
```

--------------------------------

### Loop Constructs and Termination

Source: https://context7.com/wildarch/graphalg/llms.txt

Illustrates looping over ranges and dimensions, including early termination using the until clause.

```graphalg
func ForConstant() -> int {
    sum = int(0);
    for i in int(0):int(10) {
        sum = sum + int(1);
    }
    return sum;
}

func ForDimension(graph: Matrix<s, s, bool>) -> int {
    count = int(0);
    for i in graph.nrows {
        count = count + int(1);
    }
    return count;
}

func BFSWithTermination(graph: Matrix<s, s, bool>, source: Vector<s, bool>) -> Vector<s, bool> {
    frontier = source;
    reach = source;
    for i in graph.nrows {
        step = Vector<bool>(graph.nrows);
        step<!reach> = frontier * graph;
        frontier = step;
        reach += step;
    } until frontier.nvals == int(0);
    return reach;
}
```

--------------------------------

### General function syntax template in GraphAlg

Source: https://github.com/wildarch/graphalg/blob/main/tutorial/index.md

This template illustrates the standard structure for creating functions in GraphAlg, including naming conventions, parameter declaration, and return type specification.

```graphalg
func <function name>(<param name>: <param type>, ...) -> <return type> {
    <statement>
    ...
}
```

--------------------------------

### Define a simple increment function in GraphAlg

Source: https://github.com/wildarch/graphalg/blob/main/tutorial/index.md

This snippet demonstrates the basic syntax for defining a function in GraphAlg. It shows how to specify parameter types, return types, and the use of the return statement.

```graphalg
func AddOne(a: int) -> int {
    return a + int(1);
}
```

--------------------------------

### LLVM Dependency Configuration (CMake)

Source: https://github.com/wildarch/graphalg/blob/main/compiler/CMakeLists.txt

Finds the LLVM package using CMake's find_package command, includes LLVM's header directories, processes LLVM definitions, and adds LLVM's CMake modules to the path. It also maps LLVM components to library names.

```cmake
find_package(LLVM REQUIRED CONFIG)
include_directories(${LLVM_INCLUDE_DIRS})
separate_arguments(LLVM_DEFINITIONS_LIST NATIVE_COMMAND ${LLVM_DEFINITIONS})
add_definitions(${LLVM_DEFINITIONS_LIST})
list(APPEND CMAKE_MODULE_PATH "${LLVM_CMAKE_DIR}")
include(TableGen)
include(AddLLVM)

llvm_map_components_to_libnames(llvm_libs support)
```

--------------------------------

### Configure LLVM Lit Test Suite in CMake

Source: https://github.com/wildarch/graphalg/blob/main/compiler/test/CMakeLists.txt

This snippet discovers the 'lit' test runner, allows for custom LLVM tool binary paths, and configures the 'lit' site configuration file. It concludes by registering a custom test suite named 'check' that depends on core graphalg executables.

```cmake
find_program(LIT_PATH NAMES lit)
if (LIT_PATH)
    set (LLVM_EXTERNAL_LIT ${LIT_PATH} CACHE STRING "lit path" FORCE)
endif ()

if(DEFINED GRAPHALG_OVERRIDE_LLVM_TOOLS_BINARY_DIR)
    set(LLVM_TOOLS_BINARY_DIR "${GRAPHALG_OVERRIDE_LLVM_TOOLS_BINARY_DIR}")
endif()

configure_lit_site_cfg(
    ${CMAKE_CURRENT_SOURCE_DIR}/lit.site.cfg.py.in
    ${CMAKE_CURRENT_BINARY_DIR}/lit.site.cfg.py
    MAIN_CONFIG
    ${CMAKE_CURRENT_SOURCE_DIR}/lit.cfg.py
)

add_lit_testsuite(check "Run integration tests"
    ${CMAKE_CURRENT_BINARY_DIR}
    DEPENDS
    graphalg-exec
    graphalg-opt
    graphalg-translate
)
```

--------------------------------

### Function Definition with One Parameter

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Defines a function that accepts a single integer parameter and returns an integer. Demonstrates basic parameter handling.

```Go
func OneParam(i:int) -> int {
  return int(42);
}
```

--------------------------------

### Execute Matrix Transpose and Reverse Traversal

Source: https://context7.com/wildarch/graphalg/llms.txt

Demonstrates the use of the .T operator for matrix transposition and how it is applied to perform reverse graph reachability analysis.

```graphalg
func TransposeExample(graph: Matrix<s, s, bool>) -> Matrix<s, s, bool> {
    return graph.T;
}

func ReverseReachability(graph: Matrix<s, s, bool>, target: Vector<s, bool>) -> Vector<s, bool> {
    reach = target;
    for i in graph.nrows {
        reach += graph.T * reach;
    }
    return reach;
}
```

--------------------------------

### MLIR Dependency Configuration (CMake)

Source: https://github.com/wildarch/graphalg/blob/main/compiler/CMakeLists.txt

Finds the MLIR package, sets its binary directory, and adds MLIR's CMake modules to the path. It also includes a mechanism to override the MLIR TableGen executable path if needed and includes MLIR-specific CMake scripts.

```cmake
find_package(MLIR ${LLVM_PACKAGE_VERSION} REQUIRED CONFIG
    HINTS "${LLVM_INSTALL_PREFIX}/lib/cmake"
)
message(STATUS "Using MLIRConfig.cmake in: ${MLIR_DIR}")
set(MLIR_BINARY_DIR ${CMAKE_BINARY_DIR})
list(APPEND CMAKE_MODULE_PATH "${MLIR_CMAKE_DIR}")

# Using a placeholder to set MLIR_TABLEGEN_EXE because find_package(MLIR)
# overwrites the MLIR_TABLEGEN_EXE flag
if(DEFINED GRAPHALG_OVERRIDE_MLIR_TABLEGEN_PATH)
    set(MLIR_TABLEGEN_EXE "${GRAPHALG_OVERRIDE_MLIR_TABLEGEN_PATH}")
endif()

include(AddMLIR)
```

--------------------------------

### Simulate pickAny in for-MATLANG

Source: https://github.com/wildarch/graphalg/blob/main/spec/core/for-ml.md

This for-MATLANG code snippet shows how to simulate the `pickAny` operation using canonical vectors. It iterates through rows and columns to find a non-zero element in the input matrix `A` and constructs an output matrix `out` representing the selected element.

```for-MATLANG
// Implements out = pickAny(A);
out = zero_matrix_of_type(A)
for v_i: // row per row
    for w_j:
        B = diag(v_i) * A * diag(w_j) // B_ij = A_ij and zero elsewhere
        s = v_i^T * A * w_j // scalar containing B_ij = A_ij
        if s != 0:
            break
    out += B // row i is done
```

--------------------------------

### Define Matrix Operations and Properties in GraphAlg

Source: https://context7.com/wildarch/graphalg/llms.txt

Demonstrates how to declare matrix types with symbolic dimensions and access metadata such as row counts, column counts, and non-zero element counts.

```graphalg
func MatrixOps(graph: Matrix<s, s, bool>) -> Vector<s, int> {
    result = Vector<int>(graph.nrows);
    result[:] = int(1);
    n = graph.nrows;
    m = graph.ncols;
    count = graph.nvals;
    return result;
}
```

--------------------------------

### Plain Assignment Operation

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Demonstrates a simple assignment operation where a variable 'b' is assigned the value of parameter 'a'.

```Go
func Assign(a: int) -> int {
  b = a;
  return b;
}
```

--------------------------------

### Perform Matrix Multiplication and Graph Traversal

Source: https://context7.com/wildarch/graphalg/llms.txt

Illustrates standard matrix multiplication and vector-matrix multiplication, including an implementation of graph reachability using iterative multiplication.

```graphalg
func MatrixMultiply(a: Matrix<r, c, int>, b: Matrix<c, t, int>) -> Matrix<r, t, int> {
    return a * b;
}

func VectorMatrixMultiply(v: Vector<s, int>, m: Matrix<s, s, int>) -> Vector<s, int> {
    return v * m;
}

func Reachability(graph: Matrix<s, s, bool>, source: Vector<s, bool>) -> Vector<s, bool> {
    reach = source;
    for i in graph.nrows {
        reach += reach * graph;
    }
    return reach;
}
```

--------------------------------

### Simulate Canonical Vectors in GraphAlg

Source: https://github.com/wildarch/graphalg/blob/main/spec/core/for-ml.md

This GraphAlg code snippet demonstrates how to simulate canonical vectors using the `pickAny` operation. It initializes a state vector and iteratively selects a canonical vector using `pickAny` within a loop, updating the state.

```GraphAlg
func canonicalVectors(X: Matrix<s, s, bool>) -> Matrix<s, s, bool> {
    // State for the canonical vector
    canon = Vector<bool>(graph.nrows);
    canon[:] = bool(true);

    for i in v.nrows {
        canonical_vector = pickAny(canon.T).T;

        // BEGIN - Inner body of the for-MATLANG loop
        X = ...;
        // END - Inner body of the for-MATLANG loop

        v<canonical_vector>[:] = bool(false);
    }

    return X;
}
```

--------------------------------

### Pick Any Matrix Element

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Selects and returns an arbitrary element from a given matrix. This function uses the `pickAny` built-in.

```Go
func pickAnyVal(a: Matrix<s, s, int>) -> int {
  return pickAny(a);
}
```

--------------------------------

### Utilize Semirings for Graph Algorithms

Source: https://context7.com/wildarch/graphalg/llms.txt

Shows the usage of standard arithmetic semirings (int, real, bool) and the tropical semiring for shortest path calculations, where addition acts as a minimum operator.

```graphalg
func StandardTypes(a: int, b: real, c: bool) -> real {
    x = a + int(1);
    y = b * real(2.5);
    z = c + bool(true);
    return cast<real>(x) + y;
}

func TropicalExample(graph: Matrix<s, s, trop_real>, source: Vector<s, trop_real>) -> Vector<s, trop_real> {
    dist = source;
    for i in graph.nrows {
        dist += dist * graph;
    }
    return dist;
}
```

--------------------------------

### Single-Source Shortest Path (SSSP) Algorithm in GraphAlg

Source: https://github.com/wildarch/graphalg/blob/main/tutorial/index.md

Implements the Single-Source Shortest Path (SSSP) algorithm using a tropical semiring. This algorithm iteratively updates distances from a source node by accumulating edge weights, utilizing the min operator for addition and the sum operator for multiplication to find the shortest paths.

```graphalg
func SSSP(
    graph: Matrix<s, s, trop_real>,
    source: Vector<s, trop_real>) -> Vector<s, trop_real> {
  dist = source;
  for i in graph.nrows {
    dist += dist * graph;
  }
  return dist;
}
```

--------------------------------

### Implement Fibonacci Sequence in GraphAlg

Source: https://github.com/wildarch/graphalg/blob/main/tutorial/index.md

A function demonstrating variable initialization, reassignment, and the use of a for-loop to calculate the n'th Fibonacci number.

```graphalg
func Fibonacci(n: int) -> int {
    a = int(0);
    b = int(1);
    for i in int(0):n {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}
```

--------------------------------

### GraphAlg SSSP Implementation

Source: https://github.com/wildarch/graphalg/blob/main/playground/index.md

This code implements the Single-Source Shortest Path (SSSP) algorithm in GraphAlg. It takes a graph represented as a matrix and a source vertex, then computes the shortest path distances from the source to all other vertices. The algorithm iteratively updates distances by traversing the graph.

```GraphAlg
func SSSP(
    graph: Matrix<s1, s1, trop_real>,
    source: Vector<s1, bool>) -> Vector<s1, trop_real> {
  v = cast<trop_real>(source);
  for i in graph.nrows {
    v += v * graph;
  }
  return v;
}
```

--------------------------------

### Configure WebAssembly Export Options

Source: https://github.com/wildarch/graphalg/blob/main/playground/cpp/CMakeLists.txt

Defines a list of exported functions and runtime methods for WebAssembly compilation. These options are applied to the target executable when the ENABLE_WASM flag is enabled.

```cmake
if(ENABLE_WASM)
    set(PLAYGROUND_EXPORTED_FUNCTIONS
        _ga_new _ga_free _ga_parse _ga_evaluate
    )
    string (REPLACE ";" "," PLAYGROUND_EXPORTED_FUNCTIONS_STR "${PLAYGROUND_EXPORTED_FUNCTIONS}")

    target_link_options(graphalg-playground PRIVATE
        -sEXPORTED_FUNCTIONS=${PLAYGROUND_EXPORTED_FUNCTIONS_STR}
        -sEXPORTED_RUNTIME_METHODS=cwrap,UTF8ToString
        -sMODULARIZE
        -sEXPORT_ES6)
endif()
```

--------------------------------

### Implement Single-Source Shortest Path (SSSP)

Source: https://context7.com/wildarch/graphalg/llms.txt

Computes shortest distances from a source node using the tropical semiring. It utilizes Bellman-Ford style relaxation to update distances iteratively.

```graphalg
func SSSP(graph: Matrix<s, s, trop_real>, source: Vector<s, bool>) -> Vector<s, trop_real> {
	dist = cast<trop_real>(source);
	for i in graph.nrows {
		dist += dist * graph;
	}
	return dist;
}
```

--------------------------------

### Matrix and Vector Constructors

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Constructs new Matrix or Vector instances based on the dimensions of existing objects. These functions utilize property accessors for rows and columns.

```GraphAlg
func matrix(m: Matrix<r, c, int>) -> Matrix<r, c, int> {
  return Matrix<int>(m.nrows, m.ncols);
}
func vector(v: Vector<s, int>) -> Vector<s, int> {
  return Vector<int>(v.nrows);
}
```

--------------------------------

### Perform Type Casting in GraphAlg

Source: https://context7.com/wildarch/graphalg/llms.txt

Demonstrates how to convert between semirings and types using the cast<target_semiring>(expression) syntax. This is essential for converting boolean matrices to integer counts or preparing data for tropical semiring arithmetic.

```graphalg
func CastExamples(a: int, b: bool) -> real {
	x = cast<real>(a);
	y = cast<int>(b);
	z = cast<trop_real>(a);
	return x;
}

func CountEdges(graph: Matrix<s, s, bool>) -> int {
	return reduce(cast<int>(graph));
}
```

--------------------------------

### Integrate LLVM into CMake Project

Source: https://github.com/wildarch/graphalg/blob/main/playground/cpp/CMakeLists.txt

Locates the LLVM package and configures the environment to use LLVM libraries. It maps required components and adds necessary include directories and definitions.

```cmake
find_package(LLVM REQUIRED CONFIG)
include_directories(${LLVM_INCLUDE_DIRS})
separate_arguments(LLVM_DEFINITIONS_LIST NATIVE_COMMAND ${LLVM_DEFINITIONS})
add_definitions(${LLVM_DEFINITIONS_LIST})
list(APPEND CMAKE_MODULE_PATH "${LLVM_CMAKE_DIR}")
include(AddLLVM)

llvm_map_components_to_libnames(llvm_libs support)
```

--------------------------------

### DiagOp to Relational Algebra Projection

Source: https://github.com/wildarch/graphalg/blob/main/spec/core/relalg.md

Translates the DiagOp into a relational algebra projection by adding a column index equal to the row index. If the input is a row vector, a row index equal to the column index is added instead.

```Relational Algebra
projection(
    <expr>,
    {
        row = row,
        col = row,
        val = val,
    }
)
```

--------------------------------

### Test Type Mismatch Errors

Source: https://github.com/wildarch/graphalg/blob/main/docs/parse-tests.md

Demonstrates how to verify type mismatch errors, such as reassigning a variable to a different type or performing invalid accumulation operations.

```graphalg
func Test() -> int {
    // expected-note@below{{previous assigment was here}}
    a = int(42);
    // expected-error@below{{cannot assign value of type real to previously defined variable of type int}}
    a = real(3.14);
    return int(0);
}
```

--------------------------------

### Function Definition with No Parameters

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Defines a function that takes no parameters and returns an integer. This is a basic function structure.

```Go
func NoParams() -> int {
  return int(42);
}
```

--------------------------------

### PickAnyOp: Select Zero Elements per Row

Source: https://github.com/wildarch/graphalg/blob/main/spec/core/relalg.md

Removes zero elements and selects zero (col, val) combinations per row. It uses aggregate functions like min and argmin on grouped data. For boolean matrices, the argmin can be omitted.

```SQL-like
aggregate(
    selection(
        <expr>,
        { val != <zero> }
    ),
    group by { row },
    aggregate {
        min(col),
        argmin(val, col)
    }
)
```

--------------------------------

### AddOp: Semiring Addition Operations

Source: https://github.com/wildarch/graphalg/blob/main/spec/core/relalg.md

Defines the addition operation based on the semiring type. Supports logical OR for i1, signed integer add for i64, floating-point add for f64, and min/max operations for trop types.

```Conceptual
Pick the operation based on the semiring:
- i1: logical OR
- i64: signed integer add
- f64: floating point add
- trop_i64/trop_real: `min`
- trop_max_i64: `max`
```

--------------------------------

### TransposeOp to Relational Algebra Projection

Source: https://github.com/wildarch/graphalg/blob/main/spec/core/relalg.md

Translates the TransposeOp into a relational algebra projection by swapping row and column indices. For vector inputs lacking row or column, it's a no-op.

```Relational Algebra
projection(
    <expr>,
    {
        row = col,
        col = row,
        val = val,
    }
)
```

--------------------------------

### Function with Matrix Parameter Type

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Defines a function that takes a matrix as a parameter. Illustrates the type definition for matrices with specified dimensions and element type.

```Go
func Mat(a: Matrix<s, 1, int>) -> int {
  return int(42);
}
```

--------------------------------

### Arithmetic Expression (Add and Multiply)

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Evaluates an arithmetic expression involving addition and multiplication of three integer parameters: a + b * c.

```Go
func arith(a:int, b:int, c:int) -> int {
  return a + b * c;
}
```

--------------------------------

### Vector-Matrix Multiplication Pattern

Source: https://github.com/wildarch/graphalg/blob/main/tutorial/index.md

Shows the implementation of vector-matrix multiplication. While mathematically requiring transposition, GraphAlg allows the shorthand notation and handles the underlying transpose operations automatically.

```graphalg
func VectorMatrixMul(
        a: Vector<s, int>,
        b: Matrix<s, s, int>) -> Vector<s, int> {
    return (a.T * b).T;
}
```

--------------------------------

### Configure MLIR TableGen Generation

Source: https://github.com/wildarch/graphalg/blob/main/compiler/include/garel/CMakeLists.txt

This CMake script sets up include directories and invokes mlir_tablegen to generate C++ header and source files from TableGen definitions. It handles attribute declarations, definitions, and dialect operations.

```cmake
include_directories(SYSTEM ${MLIR_INCLUDE_DIRS})
include_directories(SYSTEM ${PROJECT_BINARY_DIR}/include)

set(LLVM_TARGET_DEFINITIONS GARelAttr.td)
mlir_tablegen(GARelEnumAttr.h.inc -gen-enum-decls)
mlir_tablegen(GARelEnumAttr.cpp.inc -gen-enum-defs)
mlir_tablegen(GARelAttr.h.inc --gen-attrdef-decls)
mlir_tablegen(GARelAttr.cpp.inc -gen-attrdef-defs)

set(LLVM_TARGET_DEFINITIONS GARelOps.td)
add_mlir_dialect(GARelOps garel)

set(LLVM_TARGET_DEFINITIONS GARelPasses.td)
mlir_tablegen(GARelPasses.h.inc --gen-pass-decls)
add_public_tablegen_target(MLIRGARelPassesIncGen)
```

--------------------------------

### Constant Range For Loop

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Implements a 'for' loop that iterates over a constant range of integers from 0 up to (but not including) 10. The loop body is empty.

```Go
func ForConst() -> int {
  for i in int(0):int(10) {
  }
  return int(42);
}
```

--------------------------------

### Build Options Configuration (CMake)

Source: https://github.com/wildarch/graphalg/blob/main/compiler/CMakeLists.txt

Defines build options for the GraphAlg compiler, allowing users to enable or disable features like Run-Time Type Information (RTTI), fuzzing, and sanitizers. These options control compiler flags and build behavior.

```cmake
option(GRAPHALG_ENABLE_RTTI "Enable run time type information" OFF)

option(GRAPHALG_ENABLE_FUZZER "Enable building fuzzer targets" OFF)
option(GRAPHALG_ENABLE_SANITIZE "Enable sanitizers" OFF)
```

--------------------------------

### Sanitizer and Coverage Options (CMake)

Source: https://github.com/wildarch/graphalg/blob/main/compiler/CMakeLists.txt

Configures compiler and linker options for AddressSanitizer (ASan), UndefinedBehaviorSanitizer (UBSan), and LeakSanitizer (LSan) when the GRAPHALG_ENABLE_SANITIZE option is enabled. It also adds flags for code coverage instrumentation if GRAPHALG_ENABLE_COVERAGE is enabled.

```cmake
if (GRAPHALG_ENABLE_SANITIZE)
    # Why these sanitizers in particular?
    # See https://stackoverflow.com/questions/50364533
    # AddressSanitizer is the only main sanitizer documented to work well with
    # LibFuzzer (https://llvm.org/docs/LibFuzzer.html#id24).
    #
    # -fno-omit-frame-pointer added to get nicer stack traces
    # See https://clang.llvm.org/docs/AddressSanitizer.html#usage
    add_compile_options(-fsanitize=address,undefined,leak -fno-omit-frame-pointer)
    add_link_options(-fsanitize=address,undefined,leak -fno-omit-frame-pointer)
endif ()

if (GRAPHALG_ENABLE_COVERAGE)
    add_compile_options(-fprofile-instr-generate -fcoverage-mapping)
    add_link_options(-fprofile-instr-generate -fcoverage-mapping)
endif ()
```

--------------------------------

### Configure GraphAlgParse Static Library in CMake

Source: https://github.com/wildarch/graphalg/blob/main/compiler/src/graphalg/parse/CMakeLists.txt

This snippet shows how to add source files to a static library target named GraphAlgParse and link it with another library, GraphAlgIR. It's a common pattern in CMake for managing project structure and dependencies.

```cmake
add_library(GraphAlgParse STATIC
    Lexer.cpp
    Parser.cpp
)
target_link_libraries(GraphAlgParse PRIVATE GraphAlgIR)
```

--------------------------------

### POST /compiler/matrix-ops

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Defines the AST structure for matrix and vector operations including constructors and transformations.

```APIDOC
## POST /compiler/matrix-ops

### Description
Maps matrix-related function calls to their AST representations.

### Method
POST

### Endpoint
/compiler/matrix-ops

### Request Body
- **func_def** (string) - Required - The matrix operation function definition.

### Request Example
{
  "func_def": "func diagonal(a: Vector<s, int>) -> Matrix<s, s, int> { return diag(a); }"
}

### Response
#### Success Response (200)
- **ast** (string) - The generated AST representation string.

#### Response Example
{
  "ast": "Program(Func(Ident,Param(Ident,VectorType(Vector,Dim(Ident),Semiring)),MatrixType(Matrix,Dim(Ident),Dim(Ident),Semiring),Block(LBrace,Return(CallExpr(BuiltInFunc,Ident)),RBrace)))"
}
```

--------------------------------

### For Loop with Until Condition

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

A 'for' loop that iterates over the number of rows in matrix 'a' and continues until a specified boolean condition (here, always false) is met. The loop body is empty.

```Go
func forUntil(a: Matrix<s, s, int>) -> Matrix<s, s, int> {
  for i in a.nrows {
  } until bool(false);
  return a;
}
```

--------------------------------

### Matrix Transpose Operation

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Returns the transpose of a given matrix 'a'. This is a common linear algebra operation.

```Go
func Trans(a: Matrix<s, s, int>) -> Matrix<s, s, int> {
  return a.T;
}
```

--------------------------------

### Function with Vector Parameter Type

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Defines a function that takes a vector as a parameter. Shows the type definition for vectors, including their dimension and element type.

```Go
func Vec(a: Vector<s, int>) -> int {
  return int(42);
}
```

--------------------------------

### Emit Error with Type Formatting in C++

Source: https://github.com/wildarch/graphalg/blob/main/docs/parse-tests.md

Demonstrates the correct way to emit an error message in C++ that includes an MLIR type. It highlights the use of `typeToString()` for user-friendly type representation, contrasting it with the incorrect method of directly printing the type, which results in a raw MLIR format. This practice ensures error messages are clear and easy for users to understand.

```cpp
auto diag = mlir::emitError(loc)
            << "parameter has type " << typeToString(funcType.getInput(i));
```

```cpp
auto diag = mlir::emitError(loc)
            << "parameter has type " << funcType.getInput(i);  // Shows raw MLIR type
```

--------------------------------

### Element-wise Operations in Graphalg

Source: https://context7.com/wildarch/graphalg/llms.txt

Performs element-wise operations on matrices using specified operators like addition (.+) and multiplication (.*). Supports custom binary functions for element-wise application. Inputs are matrices of integers, and outputs are matrices of integers.

```graphalg
func ElementWiseOps(
    a: Matrix<s, s, int>,
    b: Matrix<s, s, int>) -> Matrix<s, s, int> {
    // Element-wise addition (union with semiring add)
    sum = a (.+) b;

    // Element-wise multiplication (intersection with semiring mul)
    product = a (.*) b;

    return sum (.+) product;
}

// Element-wise division for PageRank normalization
func NormalizeByDegree(
    values: Vector<s, real>,
    degrees: Vector<s, real>) -> Vector<s, real> {
    // Divide each value by corresponding degree
    return values (./) degrees;
}

// Custom element-wise function
func myAdd(a: int, b: int) -> int {
    return a + b;
}

func CustomElementWise(
    a: Matrix<s, s, int>,
    b: Matrix<s, s, int>) -> Matrix<s, s, int> {
    // Apply custom binary function element-wise
    return a (.myAdd) b;
}
```

--------------------------------

### POST /compiler/arithmetic

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

Defines the AST structure for arithmetic operations like subtraction and division.

```APIDOC
## POST /compiler/arithmetic

### Description
Maps an arithmetic function definition to its AST representation.

### Method
POST

### Endpoint
/compiler/arithmetic

### Request Body
- **func_def** (string) - Required - The function signature and body (e.g., func arith(a:int, b:int, c:int) -> int { return a - b / c; })

### Request Example
{
  "func_def": "func arith(a:int, b:int, c:int) -> int { return a - b / c; }"
}

### Response
#### Success Response (200)
- **ast** (string) - The generated AST representation string.

#### Response Example
{
  "ast": "Program(Func(Ident,Param(Ident,Semiring),Param(Ident,Semiring),Param(Ident,Semiring),Semiring,Block(LBrace,Return(SubExpr(Ident,Minus,DivExpr(Ident,Div,Ident))),RBrace)))"
}
```

--------------------------------

### Subdirectory Inclusion (CMake)

Source: https://github.com/wildarch/graphalg/blob/main/compiler/CMakeLists.txt

Includes subdirectories for different parts of the GraphAlg project, such as MLIR dialects, source code, tests, and tools. This organizes the build process by modularizing different components.

```cmake
# Directories with MLIR dialects
add_subdirectory(include/graphalg)
add_subdirectory(include/garel)

add_subdirectory(src)
add_subdirectory(test)
add_subdirectory(tools)
```

--------------------------------

### GraphAlg PageRank Algorithm Implementation

Source: https://github.com/wildarch/graphalg/blob/main/index.md

This snippet implements the PageRank algorithm using the GraphAlg language. It defines helper functions for damping and calculates PageRank scores iteratively. The input is a graph represented as a matrix, and the output is a vector of PageRank scores.

```graphalg
func withDamping(degree:int, damping:real) -> real {
    return cast<real>(degree) / damping;
}

func PageRank(graph: Matrix<s, s, bool>) -> Vector<s, real> {
    damping = real(0.85);
    iterations = int(10);
    n = graph.nrows;
    teleport = real(0.15) / cast<real>(n);

    d_out = reduceRows(cast<int>(graph));
    d = apply(withDamping, d_out, damping);

    pr = Vector<real>(n);
    pr[:] = real(1.0) / cast<real>(n);

    for i in int(0):iterations {
        w = pr (./) d;
        pr[:] = teleport;
        pr += cast<real>(graph).T * w;
    }

    return pr;
}
```

--------------------------------

### Implement PageRank Algorithm

Source: https://context7.com/wildarch/graphalg/llms.txt

Calculates node importance scores based on link structure. The implementation handles damping factors, sink nodes, and iterative distribution of PageRank scores.

```graphalg
func PageRank(graph: Matrix<s, s, bool>) -> Vector<s, real> {
	damping = real(0.85);
	iterations = int(10);
	n = graph.nrows;
	teleport = (real(1.0) - damping) / cast<real>(n);
	d_out = reduceRows(cast<int>(graph));
	pr = Vector<real>(n);
	pr[:] = real(1.0) / cast<real>(n);
	for i in int(0):iterations {
		pr += cast<real>(graph).T * (pr (./) d_out);
	}
	return pr;
}
```

--------------------------------

### For Loop Iterating Over Matrix Dimensions

Source: https://github.com/wildarch/graphalg/blob/main/codemirror-lang-graphalg/test/cases.txt

A 'for' loop that iterates based on the number of rows in a given matrix 'a'. The loop body is empty.

```Go
func ForDim(a: Matrix<s, s, int>) -> Matrix<s, s, int> {
  for i in a.nrows {
  }
  return a;
}
```

--------------------------------

### Accumulation Operations

Source: https://context7.com/wildarch/graphalg/llms.txt

Utilizes the += operator for semiring-based accumulation, demonstrating both summation and boolean OR operations for graph reachability.

```graphalg
func AccumulateExample(a: Matrix<s, s, int>, b: Matrix<s, s, int>) -> Matrix<s, s, int> {
    a += b;
    return a;
}

func IterativeReachability(graph: Matrix<s, s, bool>, source: Vector<s, bool>) -> Vector<s, bool> {
    reach = source;
    for i in graph.nrows {
        reach += reach * graph;
    }
    return reach;
}
```
Tokens:
Raw