GraphAlg Playground

Compile and execute GraphAlg programs in your browser!

Early Preview

The examples below are highly experimental and may malfunction.

Breadth-First Search

func setDepth(b:bool, iter:int) -> int {
    return cast<int>(b) * (iter + int(2));
}

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

    frontier = source;
    reach = source;

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

        v += apply(setDepth, step, i);

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

    return v;
}

Label Propagation

func isMax(v: int, max: trop_max_int) -> bool {
  return (cast<trop_max_int>(v) == max)
      * (v != zero(int));
}

func CDLP(graph: Matrix<s, s, bool>) -> Matrix<s, s, bool> {
    iterations = int(5);
    id = Vector<bool>(graph.nrows);
    id[:] = bool(true);
    L = diag(id);

    for i in int(0):iterations {
        step_forward = cast<int>(graph) * cast<int>(L);
        step_backward = cast<int>(graph.T) * cast<int>(L);
        step = step_forward (.+) step_backward;

        // Max per row
        max = reduceRows(cast<trop_max_int>(step));

        // Broadcast to all columns
        b = Vector<trop_max_int>(graph.ncols);
        b[:] = one(trop_max_int);
        max_broadcast = max * b.T;

        // Matrix with true at every position where L has max element.
        step_max = step (.isMax) max_broadcast;

        // Keep only one assigned label per vertex.
        // The implementation always picks the one with the lowest id.
        L = pickAny(step_max);
    }

    // Map isolated nodes to their own label.
    connected = reduceRows(graph) (.+) reduceRows(graph.T);
    isolated = Vector<bool>(graph.nrows);
    isolated<!connected>[:] = bool(true);
    L = diag(isolated) (.+) L;

    return L;
}

PageRank

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

func PR(graph: Matrix<s1, s1, bool>) -> Vector<s1, real> {
    damping = real(0.85);
    iterations = int(10);
    n = graph.nrows;
    teleport = (real(1.0) - damping) / cast<real>(n);
    rdiff = real(1.0);

    d_out = reduceRows(cast<int>(graph));

    d = apply(withDamping, d_out, damping);

    connected = reduceRows(graph);
    sinks = Vector<bool>(n);
    sinks<!connected>[:] = bool(true);

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

    for i in int(0):iterations {
        sink_pr = Vector<real>(n);
        sink_pr<sinks> = pr;
        redist = (damping / cast<real>(n)) * reduce(sink_pr);

        w = pr (./) d;

        pr[:] = teleport + redist;
        pr += cast<real>(graph).T * w;
    }

    return pr;
}

Single-Source Shortest Paths

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;
}

Weakly Connected Components

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 {
    // Keep current label
    alternatives = label;
    // Labels reachable with a forward step
    alternatives += graph * label;
    // Labels reachable with a backward step
    alternatives += graph.T * label;

    // Select a new label
    label = pickAny(alternatives);
  }

  return label;
}