<jupyter_start><jupyter_text>Create and visualize a Matrix<jupyter_code>data = [
    [3, 0, 3, 5, 6, 0, 6, 1, 6, 2, 4, 1],
    [0, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6],
    [3, 2, 3, 1, 5, 3, 7, 8, 3, 1, 7, 4],
]
rows, cols, weights = data
m = Matrix.from_values(rows, cols, weights)
m
# Size of the sparse matrix is 7x7 with 12 non-zero elements of type INT64
m
# This is an adjacency matrix
# Reading along a row shows the out-nodes of a vertex
# Reading along a column shows the in-nodes of a vertex
gio.draw(m)<jupyter_output><empty_output><jupyter_text>Create and visualize a Vector<jupyter_code>v = Vector.from_values([1], [0], dtype=m.dtype, size=m.nrows)
v<jupyter_output><empty_output><jupyter_text>Single-source Shortest PathThis uses the **_min-plus_** semiring because we want to add the edges, then take the minimum length of available paths.<jupyter_code># Create a vector and initialize a starting vertex (1) with a distance of zero
v = Vector.new(m.dtype, m.nrows)
v[1] << 0
v
m
# v @ m will give us one step in a Breadth-first search
w = v.dup()
w << v.vxm(m, semiring.min_plus)
w
# Look again at m and see that vertex 1 points to vertices 4 and 6 with the weights indicated
gio.draw(m)<jupyter_output><empty_output><jupyter_text>We have the right semiring, but we already lost the initial distance=0 for vertex 1. How do we keep that information around as we step thru the BFS?GraphBLAS has a builtin accumulator available for every operation.Because it's C-based, you pass in the output object and it accumulates its existing values with the result, then returns itself.<jupyter_code>w = v.dup()
w(binary.min) << v.vxm(m, semiring.min_plus)
w
# Now we see that the zero distance for vertex 1 is preserved<jupyter_output><empty_output><jupyter_text>Let's take another step<jupyter_code>w(binary.min) << w.vxm(m, semiring.min_plus)
w
# We see that the path to vertex 4 is now shorter. That's `min` doing its thing.
# Verify the other path distances from vertex 1 with at most two hops
gio.draw(m)<jupyter_output><empty_output><jupyter_text>The algorithm repeats until a new computation is the same as the previous result<jupyter_code>w = v.dup()
while True:
    w_old = w.dup()
    w(binary.min) << w.vxm(m, semiring.min_plus)
    if w.isequal(w_old):
        break
w<jupyter_output><empty_output><jupyter_text>Alternate solution without using an accumulatorIn the min_plus semiring, the "empty" value of a sparse matrix is not actually 0, but +infinity.That way, `min(anything, +inf) = anything`, similar to the normal addition 0 of `add(anything, 0) = anything`.A clever trick sets the diagonal of the matrix to all zeros. This makes it behave like the Identity matrix for the min_plus semiring.Observe:<jupyter_code>m_ident = Matrix.from_values(range(7), range(7), [0] * 7)
m_ident
v.clear()
v.build([1], [0])
v
v << v.vxm(m_ident, semiring.min_plus)
v
# See how it preserved v exactly
# Let's try again
v.clear()
v.build([0, 1, 4], [14, 0, 77])
v << v.vxm(m_ident, semiring.min_plus)
v<jupyter_output><empty_output><jupyter_text>So zeros along the diagonal preserve what you already have in `v` without adding any new path information. That's the behavior we want, so let's update `m` with zeros on the diagonal and repeat SSSP without using accumulators.<jupyter_code>for i in range(m.nrows):
    m[i, i] << 0
m
# Reset v
v.clear()
v[1] << 0
v
# Take one step (notice no accumulator is specified)
v << v.vxm(m, semiring.min_plus)
v
# Repeat until we're converged
while True:
    w = v.dup()
    v << v.vxm(m, semiring.min_plus)
    if v.isequal(w):
        break
v<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10769656699889259, 'fraction_numerical': 0.020764119601328904, 'mean_word_length': 4.6453125, 'pattern_counts': {'":': 0, '<': 55, '<?xml version=': 0, '>': 33, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '229677', 'license': 'Apache-2.0', 'n_tokens_mistral': 1341, 'n_tokens_neox': 1250, 'n_words': 480, 'path': 'notebooks/Intro to GraphBLAS + SSSP example.ipynb', 'repo_name': 'Breadstwin/grblas', 'size': '3612'}