GraphAlg Playground

Compile and execute GraphAlg programs in your browser!

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

func PR(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));
  d = apply(withDamping, d_out, damping);

  // NEW: Find sinks
  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 {
    // NEW: compute redist amount per vertex.
    sink_pr = Vector<real>(n);
    sink_pr<sinks> = pr;
    redist = (damping / cast<real>(n)) * reduce(sink_pr);

    w = pr (./) d;

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

  return pr;
}