```python
import numpy as np
import pandas as pd
from scipy.sparse import coo_array, eye
import networkx as nx
import matplotlib.pyplot as plt
import graphblas
from graphblas import Matrix, Vector, Scalar
from graphblas import descriptor
from graphblas import unary, binary, monoid, semiring, op
from graphblas import io as gio
```

## Create and visualize a Matrix


```python
# 23   // The input matrix A must be symmetric.  Self-edges (diagonal entries) are
# 24   // OK, and are ignored.  The values and type of A are ignored; just its
# 25   // pattern is accessed.
row_col = np.array(
    [
        [0, 0, 0, 1, 2, 2, 3, 6, 6, 9, 9],
        [1, 2, 3, 2, 4, 5, 4, 7, 8, 10, 11],
    ]
)
rows, cols = row_col
data = np.full_like(rows, fill_value=1)
```


```python
A = coo_array((data, (rows, cols)), shape=(12, 12)).tolil()
A[cols, rows] = A[rows, cols]  # symmetrize matrix
A = A.tocoo()
```


```python
# Draw A using spring layout which may even reveal the connected components
G = nx.convert_matrix.from_scipy_sparse_array(A)
layout = nx.drawing.layout.spring_layout(G, k=0.6, scale=1, threshold=1e-10)
nx.draw_networkx(G, with_labels=True, node_size=500, font_color="w", pos=layout)
```


```python
A = gio.from_scipy_sparse(A, name="A")
# Size of the sparse matrix is 12x12 with 22 non-zero elements of type INT64
```


```python
A
# 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
```




<div>
<style>
table.gb-info-table {
    border: 1px solid black;
    max-width: 100%;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

td.gb-info-name-cell {
    line-height: 100%;
}

details.gb-arg-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
    margin-left: 10px;
}

summary.gb-arg-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: -10px;
}

details.gb-expr-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

summary.gb-expr-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

blockquote.gb-expr-blockquote {
    margin-top: 5px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: 15px;
}

.gb-scalar {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

/* modify pandas dataframe */
table.dataframe {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}
</style>
<details open class="gb-arg-details"><summary class="gb-arg-summary"><tt>A</tt><div>
<table class="gb-info-table">
  <tr>
    <td rowspan="2" class="gb-info-name-cell"><pre>gb.Matrix</pre></td>
    <td><pre>nvals</pre></td>
    <td><pre>nrows</pre></td>
    <td><pre>ncols</pre></td>
    <td><pre>dtype</pre></td>
    <td><pre>format</pre></td>
  </tr>
  <tr>
    <td>22</td>
    <td>12</td>
    <td>12</td>
    <td>INT64</td>
    <td>bitmapr (iso)</td>
  </tr>
</table>
</div>
</summary><div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>10</th>
      <th>11</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td></td>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>1</th>
      <td>1</td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>2</th>
      <td>1</td>
      <td>1</td>
      <td></td>
      <td></td>
      <td>1</td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>3</th>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>4</th>
      <td></td>
      <td></td>
      <td>1</td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>5</th>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>6</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>7</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>8</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>9</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td>1</td>
    </tr>
    <tr>
      <th>10</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>11</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
    </tr>
  </tbody>
</table>
</div></details></div>




```python
# graphblas.io.draw could do with a few more tunable options to improve pretty display
gio.draw(A)
```

## Connected Components

https://github.com/GraphBLAS/LAGraph/blob/reorg/src/algorithm/LAGraph_ConnectedComponents.c

Sections of the C-code found at the above link are reproduced here in comments and translated into python


```python
# 10    // Code is based on the algorithm described in the following paper
# 11    // Zhang, Azad, Hu. FastSV: FastSV: A Distributed-Memory Connected Component
# 12    // Algorithm with Fast Convergence (SIAM PP20)
# 13
# 14    // A subsequent update to the algorithm is here (which might not be reflected
# 15    // in this code):
# 16    //
# 17    // Yongzhe Zhang, Ariful Azad, Aydin Buluc: Parallel algorithms for finding
# 18    // connected components using linear algebra. J. Parallel Distributed Comput.
# 19    // 144: 14-27 (2020).
```


```python
# 342      GrB_TRY (GrB_Matrix_nrows (&n, S)) ;
# 343      GrB_TRY (GrB_Matrix_nvals (&nnz, S)) ;
n = A.nrows
nnz = A.nvals
```


```python
# 370      // vectors
# 371      GrB_TRY (GrB_Vector_new (&f,      GrB_UINT32, n)) ;
# 372      GrB_TRY (GrB_Vector_new (&gp_new, GrB_UINT32, n)) ;
# 373      GrB_TRY (GrB_Vector_new (&mod,    GrB_BOOL,   n)) ;
dtype = np.uint32
f = Vector(dtype=dtype, size=n, name="parents")  # parent of each vertex
gp_new = Vector(dtype=dtype, size=n, name="grandparents")  # grandparent of each vertex
mod = Vector(dtype=bool, size=n, name="modified?")  # boolean flag for each vertex
f
```




<div>
<style>
table.gb-info-table {
    border: 1px solid black;
    max-width: 100%;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

td.gb-info-name-cell {
    line-height: 100%;
}

details.gb-arg-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
    margin-left: 10px;
}

summary.gb-arg-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: -10px;
}

details.gb-expr-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

summary.gb-expr-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

blockquote.gb-expr-blockquote {
    margin-top: 5px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: 15px;
}

.gb-scalar {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

/* modify pandas dataframe */
table.dataframe {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}
</style>
<details open class="gb-arg-details"><summary class="gb-arg-summary"><tt>parents</tt><div>
<table class="gb-info-table">
  <tr>
    <td rowspan="2" class="gb-info-name-cell"><pre>gb.Vector</pre></td>
    <td><pre>nvals</pre></td>
    <td><pre>size</pre></td>
    <td><pre>dtype</pre></td>
    <td><pre>format</pre></td>
  </tr>
  <tr>
    <td>0</td>
    <td>12</td>
    <td>UINT32</td>
    <td>sparse</td>
  </tr>
</table>
</div>
</summary><div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>10</th>
      <th>11</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th></th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
  </tbody>
</table>
</div></details></div>




```python
mod
```




<div>
<style>
table.gb-info-table {
    border: 1px solid black;
    max-width: 100%;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

td.gb-info-name-cell {
    line-height: 100%;
}

details.gb-arg-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
    margin-left: 10px;
}

summary.gb-arg-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: -10px;
}

details.gb-expr-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

summary.gb-expr-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

blockquote.gb-expr-blockquote {
    margin-top: 5px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: 15px;
}

.gb-scalar {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

/* modify pandas dataframe */
table.dataframe {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}
</style>
<details open class="gb-arg-details"><summary class="gb-arg-summary"><tt>modified?</tt><div>
<table class="gb-info-table">
  <tr>
    <td rowspan="2" class="gb-info-name-cell"><pre>gb.Vector</pre></td>
    <td><pre>nvals</pre></td>
    <td><pre>size</pre></td>
    <td><pre>dtype</pre></td>
    <td><pre>format</pre></td>
  </tr>
  <tr>
    <td>0</td>
    <td>12</td>
    <td>BOOL</td>
    <td>sparse</td>
  </tr>
</table>
</div>
</summary><div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>10</th>
      <th>11</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th></th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
  </tbody>
</table>
</div></details></div>




```python
# 387      GrB_TRY (GrB_Vector_build (f, I, V32, n, GrB_PLUS_UINT32)) ;
# 388      GrB_TRY (GrB_Vector_dup (&gp,   f)) ;
# 389      GrB_TRY (GrB_Vector_dup (&mngp, f)) ;
I = np.arange(n)
V32 = I.astype(dtype)
f.build(I, V32)  # The parent of each vertex is initialized to be the vertex itself
gp = f.dup()  # grandparent of each vertex initialized to parent
mngp = f.dup(name="Minimum grandparent")  # minimum grandparent of each vertex belonging to a star
```


```python
f
# The parent of each vertex is initialized to the vertex itself
```




<div>
<style>
table.gb-info-table {
    border: 1px solid black;
    max-width: 100%;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

td.gb-info-name-cell {
    line-height: 100%;
}

details.gb-arg-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
    margin-left: 10px;
}

summary.gb-arg-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: -10px;
}

details.gb-expr-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

summary.gb-expr-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

blockquote.gb-expr-blockquote {
    margin-top: 5px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: 15px;
}

.gb-scalar {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

/* modify pandas dataframe */
table.dataframe {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}
</style>
<details open class="gb-arg-details"><summary class="gb-arg-summary"><tt>parents</tt><div>
<table class="gb-info-table">
  <tr>
    <td rowspan="2" class="gb-info-name-cell"><pre>gb.Vector</pre></td>
    <td><pre>nvals</pre></td>
    <td><pre>size</pre></td>
    <td><pre>dtype</pre></td>
    <td><pre>format</pre></td>
  </tr>
  <tr>
    <td>12</td>
    <td>12</td>
    <td>UINT32</td>
    <td>full</td>
  </tr>
</table>
</div>
</summary><div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>10</th>
      <th>11</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th></th>
      <td>0</td>
      <td>1</td>
      <td>2</td>
      <td>3</td>
      <td>4</td>
      <td>5</td>
      <td>6</td>
      <td>7</td>
      <td>8</td>
      <td>9</td>
      <td>10</td>
      <td>11</td>
    </tr>
  </tbody>
</table>
</div></details></div>




```python
change = Scalar(dtype=bool, name="changed?")  # flag to terminate FastSV algorithm
```

This uses the ***min_second*** semiring with the *GrB_mxv()* function where *min* returns the minimum of its two inputs and *second* returns its second input.


```python
# 703         // hooking & shortcutting
# 704         GrB_TRY (GrB_mxv (mngp, NULL, GrB_MIN_UINT32,
# 705                           GrB_MIN_SECOND_SEMIRING_UINT32, T, gp, NULL)) ;
mngp(binary.min) << op.min_second(A @ gp)
mngp
```




<div>
<style>
table.gb-info-table {
    border: 1px solid black;
    max-width: 100%;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

td.gb-info-name-cell {
    line-height: 100%;
}

details.gb-arg-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
    margin-left: 10px;
}

summary.gb-arg-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: -10px;
}

details.gb-expr-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

summary.gb-expr-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

blockquote.gb-expr-blockquote {
    margin-top: 5px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: 15px;
}

.gb-scalar {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

/* modify pandas dataframe */
table.dataframe {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}
</style>
<details open class="gb-arg-details"><summary class="gb-arg-summary"><tt>Minimum grandparent</tt><div>
<table class="gb-info-table">
  <tr>
    <td rowspan="2" class="gb-info-name-cell"><pre>gb.Vector</pre></td>
    <td><pre>nvals</pre></td>
    <td><pre>size</pre></td>
    <td><pre>dtype</pre></td>
    <td><pre>format</pre></td>
  </tr>
  <tr>
    <td>12</td>
    <td>12</td>
    <td>UINT32</td>
    <td>full</td>
  </tr>
</table>
</div>
</summary><div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>10</th>
      <th>11</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th></th>
      <td>0</td>
      <td>0</td>
      <td>0</td>
      <td>0</td>
      <td>2</td>
      <td>2</td>
      <td>6</td>
      <td>6</td>
      <td>6</td>
      <td>9</td>
      <td>9</td>
      <td>9</td>
    </tr>
  </tbody>
</table>
</div></details></div>



It is not yet clear to me if the function ***Reduce_assign32*** (described in the C-code) instead of ***GrB_assign*** is really required for the algorithm to work, as it is not referred to in any of the authors' papers.  Nevertheless, I'm choosing ***GrB_assign***, in accordance with authors' papers.  This seems to work anyway for the example graph used here.


```python
# 706        GrB_TRY (Reduce_assign32 (&f, &mngp, V32, n, nthreads, ht_key,
# 707                                  ht_val, &seed, msg)) ;
#
#
# 139   //------------------------------------------------------------------------------
# 140   // Reduce_assign32:  w (index) += s, using MIN as the "+=" accum operator
# 141   //------------------------------------------------------------------------------
# 142
# 143   // mask = NULL, accumulator = GrB_MIN_UINT32, descriptor = NULL.
# 144   // Duplicates are summed with the accumulator, which differs from how
# 145   // GrB_assign works.  GrB_assign states that the presence of duplicates results
# 146   // in undefined behavior.  GrB_assign in SuiteSparse:GraphBLAS follows the
# 147   // MATLAB rule, which discards all but the first of the duplicates.
# 148
# 149   // todo: add this to GraphBLAS as a variant of GrB_assign, either as
# 150   // GxB_assign_accum (or another name), or as a GxB_* descriptor setting.
#       et cetera
#
#
f(binary.min)[V32] << mngp
```


```python
# 708        GrB_TRY (GrB_eWiseAdd (f, NULL, GrB_MIN_UINT32, GrB_MIN_UINT32,
# 709                               mngp, gp, NULL)) ;
f(binary.min) << op.min(mngp | gp)
```


```python
# 710        // calculate grandparent
# 711        // fixme: NULL parameter is SS:GrB extension
# 712        GrB_TRY (GrB_Vector_extractTuples (NULL, V32, &n, f)) ; // fixme
_, V32 = f.to_values()
V32
```




    array([0, 0, 0, 0, 2, 2, 6, 6, 6, 9, 9, 9], dtype=uint32)




```python
I = V32.astype(I.dtype)
```


```python
# 719        GrB_TRY (GrB_extract (gp_new, NULL, NULL, f, I, n, NULL)) ;
gp_new << f[I]
```


```python
# 721        // check termination
# 722        GrB_TRY (GrB_eWiseMult (mod, NULL, NULL, GrB_NE_UINT32, gp_new, gp,
# 723            NULL)) ;
# 724        GrB_TRY (GrB_reduce (&change, NULL, GrB_LOR_MONOID_BOOL, mod, NULL)) ;
mod << gp_new.ewise_mult(gp, binary.ne)
change << mod.reduce(binary.lor)
```


```python
mod
```




<div>
<style>
table.gb-info-table {
    border: 1px solid black;
    max-width: 100%;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

td.gb-info-name-cell {
    line-height: 100%;
}

details.gb-arg-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
    margin-left: 10px;
}

summary.gb-arg-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: -10px;
}

details.gb-expr-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

summary.gb-expr-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

blockquote.gb-expr-blockquote {
    margin-top: 5px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: 15px;
}

.gb-scalar {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

/* modify pandas dataframe */
table.dataframe {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}
</style>
<details open class="gb-arg-details"><summary class="gb-arg-summary"><tt>modified?</tt><div>
<table class="gb-info-table">
  <tr>
    <td rowspan="2" class="gb-info-name-cell"><pre>gb.Vector</pre></td>
    <td><pre>nvals</pre></td>
    <td><pre>size</pre></td>
    <td><pre>dtype</pre></td>
    <td><pre>format</pre></td>
  </tr>
  <tr>
    <td>12</td>
    <td>12</td>
    <td>BOOL</td>
    <td>full</td>
  </tr>
</table>
</div>
</summary><div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>10</th>
      <th>11</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th></th>
      <td>False</td>
      <td>True</td>
      <td>True</td>
      <td>True</td>
      <td>True</td>
      <td>True</td>
      <td>False</td>
      <td>True</td>
      <td>True</td>
      <td>False</td>
      <td>True</td>
      <td>True</td>
    </tr>
  </tbody>
</table>
</div></details></div>




```python
change
```




<div class="gb-scalar"><tt>changed?</tt><div>
<table class="gb-info-table">
  <tr>
    <td rowspan="2" class="gb-info-name-cell"><pre>gb.Scalar</pre></td>
    <td><pre>value</pre></td>
    <td><pre>dtype</pre></td>
  </tr>
  <tr>
    <td>True</td>
    <td>BOOL</td>
  </tr>
</table>
</div>
</div>




```python
change.value
```




    True




```python
# 726        // swap gp and gp_new
# 727        GrB_Vector t = gp ; gp = gp_new ; gp_new = t ;
gp, gp_new = gp_new, gp
```

The algorithm repeats until a new computation is the same as the previous result.

Here is the full python listing updated using changes from authors' paper: Yongzhe Zhang et al., J. Parallel Distributed Comput. 19 144: 14-27 (2020)):


```python
def fastSV(A):
    n = A.nrows
    I = np.arange(n)
    # The parent of each vertex is initialized to be the vertex itself:
    f = Vector.from_values(I, I, name="parents")
    gp = f.dup()  # grandparent of each vertex initialized to parent
    gp_dup = gp.dup()  # duplicate grandparents
    mngp = f.dup()  # minimum grandparent of each star-vertex

    # boolean flag for each vertex
    mod = Vector(dtype=bool, size=n, name="modified?")
    # flag to terminate FastSV algorithm
    change = Scalar.from_value(True, dtype=bool, name="changed?")

    while change:
        # Step 1: Hooking phase
        mngp << op.min_second(A @ gp)
        f(binary.min)[I] << mngp
        f << op.min(f | mngp)
        # Step 2: Shortcutting
        f << op.min(f | gp)
        # Step 3: Calculate grandparents
        _, I = f.to_values()
        gp << f[I]
        # Check termination
        mod << op.ne(gp_dup & gp)
        change << mod.reduce(binary.lor)
        gp_dup << gp

    return f
```


```python
connected_components = fastSV(A)
connected_components
```




<div>
<style>
table.gb-info-table {
    border: 1px solid black;
    max-width: 100%;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

td.gb-info-name-cell {
    line-height: 100%;
}

details.gb-arg-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
    margin-left: 10px;
}

summary.gb-arg-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: -10px;
}

details.gb-expr-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

summary.gb-expr-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

blockquote.gb-expr-blockquote {
    margin-top: 5px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: 15px;
}

.gb-scalar {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

/* modify pandas dataframe */
table.dataframe {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}
</style>
<details open class="gb-arg-details"><summary class="gb-arg-summary"><tt>parents</tt><div>
<table class="gb-info-table">
  <tr>
    <td rowspan="2" class="gb-info-name-cell"><pre>gb.Vector</pre></td>
    <td><pre>nvals</pre></td>
    <td><pre>size</pre></td>
    <td><pre>dtype</pre></td>
    <td><pre>format</pre></td>
  </tr>
  <tr>
    <td>12</td>
    <td>12</td>
    <td>INT64</td>
    <td>full</td>
  </tr>
</table>
</div>
</summary><div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>10</th>
      <th>11</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th></th>
      <td>0</td>
      <td>0</td>
      <td>0</td>
      <td>0</td>
      <td>0</td>
      <td>0</td>
      <td>6</td>
      <td>6</td>
      <td>6</td>
      <td>9</td>
      <td>9</td>
      <td>9</td>
    </tr>
  </tbody>
</table>
</div></details></div>



*connected_components* gives the label of the component to which each vertex belongs.

Compare with the graph drawing to check result:


```python
nx.draw_networkx(G, with_labels=True, node_size=500, font_color="w", pos=layout)
```

Each component has been identified and labeled with the least vertex ID in that component. 

### And that's FastSV in essentially 10 very readable lines of Python, thanks to GraphBLAS

Now let's test the algorithm a bit further by applying a random permutation to the vertex labels of the graph:


```python
p = np.random.permutation(A.shape[0])
```


```python
p
```




    array([ 4, 11, 10,  8,  7,  5,  3,  1,  9,  6,  2,  0])



The permutation $\mathsf{p}$ can be viewed not only as a rearrangement of the vertex labels, but also as a bijection 
$$p: V \rightarrow V $$ 
from the set of vertices $V \subset \mathbb{Z}$ to itself.  So, for example, 
$$p(0) = \mathsf{p[0]}\mbox{,}\;\;p(1) = \mathsf{p[1]}\mbox{, ...} $$

I do not know if GraphBLAS provides primitives for permuting vertex labels.  It might be worthwhile to check.  Here I'll try using graphblas: 

Let's build the above permutation's matrix $\mathbf{P}$ whose components are defined by:
$$P_{i\,j} \equiv \delta_{p(i)\, j},$$
where $\delta_{i\,j} = 1$ when $i=j$, otherwise $\delta_{i\,j} = 0$.  
Note that, 
$$ \sum_{j} j\,P_{i\,j} = \sum_{j} j\,\delta_{p(i)\, j} = p(i). $$
Also, it can be shown that
$$ \sum_{j} P^{\phantom{\mathrm{T}}}_{i\,j}P^{\mathrm{T}}_{j\,k} = \sum_{j} P_{i\,j}P_{k\,j} = \delta_{i\, k},$$
where $\mathrm{T}$ denotes the matrix transpose, and
$$P_{i\,j} = \delta_{p(i)\, j}  \iff P_{i\,p(j)} = \delta_{i\, j}.$$
We will now use the last equation above to build $\mathbf{P}$:


```python
rows, cols = np.arange(p.size), p
data = np.full_like(rows, fill_value=1)
P = Matrix.from_values(rows, cols, data, name="P")
```

Check from the definition, $P_{i\,j} \equiv \delta_{p(i)\, j}$, that the nonzero matrix elements are indeed correctly placed:


```python
P
```




<div>
<style>
table.gb-info-table {
    border: 1px solid black;
    max-width: 100%;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

td.gb-info-name-cell {
    line-height: 100%;
}

details.gb-arg-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
    margin-left: 10px;
}

summary.gb-arg-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: -10px;
}

details.gb-expr-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

summary.gb-expr-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

blockquote.gb-expr-blockquote {
    margin-top: 5px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: 15px;
}

.gb-scalar {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

/* modify pandas dataframe */
table.dataframe {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}
</style>
<details open class="gb-arg-details"><summary class="gb-arg-summary"><tt>P</tt><div>
<table class="gb-info-table">
  <tr>
    <td rowspan="2" class="gb-info-name-cell"><pre>gb.Matrix</pre></td>
    <td><pre>nvals</pre></td>
    <td><pre>nrows</pre></td>
    <td><pre>ncols</pre></td>
    <td><pre>dtype</pre></td>
    <td><pre>format</pre></td>
  </tr>
  <tr>
    <td>12</td>
    <td>12</td>
    <td>12</td>
    <td>INT64</td>
    <td>csr (iso)</td>
  </tr>
</table>
</div>
</summary><div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>10</th>
      <th>11</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>1</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
    </tr>
    <tr>
      <th>2</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
    </tr>
    <tr>
      <th>3</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>4</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>5</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>6</th>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>7</th>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>8</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>9</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>10</th>
      <td></td>
      <td></td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>11</th>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
  </tbody>
</table>
</div></details></div>



Now let us transform the adjacency matrix $\mathbf{A}$, using the permutation matrix $\mathbf{P}$, into 
$$\mathbf{A}' = \mathbf{P}^{\mathrm{T}} \cdot \mathbf{A} \cdot \mathbf{P},$$
which ensures that the graph edges are preserved after permutation, that is,
\begin{equation}
\boxed{A_{i\,j} = A'_{p(i)\,p(j)}}
\end{equation}
for all $i$, $j$.


```python
AA = A.dup(name="AA")
AA << P.T @ A @ P
```

Let's redraw the graph with the new labels and compare with the permutation array and graph-drawing above.


```python
A_sci = gio.to_scipy_sparse(AA, format="csr")
G_perm = nx.convert_matrix.from_scipy_sparse_array(A_sci)
layout_perm = {p[k]: layout[k] for k in layout}
nx.draw_networkx(G_perm, with_labels=True, node_size=500, font_color="w", pos=layout_perm)
```

Now let's re-apply the algorithm:


```python
connected_components_perm = fastSV(AA)
connected_components_perm
```




<div>
<style>
table.gb-info-table {
    border: 1px solid black;
    max-width: 100%;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

td.gb-info-name-cell {
    line-height: 100%;
}

details.gb-arg-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
    margin-left: 10px;
}

summary.gb-arg-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: -10px;
}

details.gb-expr-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

summary.gb-expr-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

blockquote.gb-expr-blockquote {
    margin-top: 5px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: 15px;
}

.gb-scalar {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

/* modify pandas dataframe */
table.dataframe {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}
</style>
<details open class="gb-arg-details"><summary class="gb-arg-summary"><tt>parents</tt><div>
<table class="gb-info-table">
  <tr>
    <td rowspan="2" class="gb-info-name-cell"><pre>gb.Vector</pre></td>
    <td><pre>nvals</pre></td>
    <td><pre>size</pre></td>
    <td><pre>dtype</pre></td>
    <td><pre>format</pre></td>
  </tr>
  <tr>
    <td>12</td>
    <td>12</td>
    <td>INT64</td>
    <td>full</td>
  </tr>
</table>
</div>
</summary><div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>10</th>
      <th>11</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th></th>
      <td>0</td>
      <td>1</td>
      <td>0</td>
      <td>1</td>
      <td>4</td>
      <td>4</td>
      <td>0</td>
      <td>4</td>
      <td>4</td>
      <td>1</td>
      <td>4</td>
      <td>4</td>
    </tr>
  </tbody>
</table>
</div></details></div>



It looks like once again the algorithm worked as expected.  Let's confirm this programmatically by undoing the permutation on the result:


```python
_, components_perm = connected_components_perm.to_values()
```


```python
_, components = connected_components.to_values()
```


```python
def assert_components_equal(components, components_perm, p):
    """
    This function undoes the vertex-label permutation p in
    components_perm and compares the result to the original
    components obtained before the permutation was applied.
    """
    # Undo the permutation in components_perm:
    components_unperm_not_min = components_perm[p]
    # Note that the resulting component-labels are not
    # necessarily the minimum vertex-labels for each
    # component.
    # Extract minimum vertex-label for each component:
    non_min_vertices, min_vertices = np.unique(components_unperm_not_min, return_index=True)
    # create a mapping from the non-minimum to minimum
    # component labels:
    q = p.copy()
    q[non_min_vertices] = min_vertices
    # apply the map:
    components_perm_undone = q[components_unperm_not_min]
    assert np.all(components == components_perm_undone)
```


```python
assert_components_equal(components, components_perm, p)
```

To further test this assertion function, let us apply a second random permutation $p_2$ to the previous permutation:


```python
p2 = np.random.permutation(A.shape[0])
p2
```




    array([ 5,  9,  4,  2, 10,  3,  7,  6,  8, 11,  0,  1])




```python
rows, cols = np.arange(p2.size), p2
data = np.full_like(rows, fill_value=1)
P = Matrix.from_values(rows, cols, data)
```


```python
AAA = A.dup()
AAA << P.T @ AA @ P
```


```python
AAA_sci = gio.to_scipy_sparse(AAA, format="csr")
G_perm2 = nx.convert_matrix.from_scipy_sparse_array(AAA_sci)
layout_perm2 = {p2[k]: layout_perm[k] for k in layout_perm}
nx.draw_networkx(G_perm2, with_labels=True, node_size=500, font_color="w", pos=layout_perm2)
```


```python
connected_components_perm2 = fastSV(AAA)
connected_components_perm2
```




<div>
<style>
table.gb-info-table {
    border: 1px solid black;
    max-width: 100%;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

td.gb-info-name-cell {
    line-height: 100%;
}

details.gb-arg-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
    margin-left: 10px;
}

summary.gb-arg-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: -10px;
}

details.gb-expr-details {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

summary.gb-expr-summary {
    display: list-item;
    outline: none;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}

blockquote.gb-expr-blockquote {
    margin-top: 5px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
    margin-left: 15px;
}

.gb-scalar {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 5px;
}

/* modify pandas dataframe */
table.dataframe {
    margin-top: 0px;
    margin-bottom: 0px;
    padding-top: 0px;
    padding-bottom: 0px;
}
</style>
<details open class="gb-arg-details"><summary class="gb-arg-summary"><tt>parents</tt><div>
<table class="gb-info-table">
  <tr>
    <td rowspan="2" class="gb-info-name-cell"><pre>gb.Vector</pre></td>
    <td><pre>nvals</pre></td>
    <td><pre>size</pre></td>
    <td><pre>dtype</pre></td>
    <td><pre>format</pre></td>
  </tr>
  <tr>
    <td>12</td>
    <td>12</td>
    <td>INT64</td>
    <td>full</td>
  </tr>
</table>
</div>
</summary><div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>10</th>
      <th>11</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th></th>
      <td>0</td>
      <td>0</td>
      <td>2</td>
      <td>0</td>
      <td>4</td>
      <td>4</td>
      <td>0</td>
      <td>4</td>
      <td>0</td>
      <td>2</td>
      <td>0</td>
      <td>2</td>
    </tr>
  </tbody>
</table>
</div></details></div>




```python
_, components_perm2 = connected_components_perm2.to_values()
```


```python
assert_components_equal(components_perm, components_perm2, p2)
```


```python

```

29f8dd7765842baacb1b606b40acfa26d7221ed3
ipynb
Jupyter Notebook
notebooks/Connected Components -- FastSV.ipynb
jim22k/grblas
7c96ddd3cb485f2c98637e7fb96070ff6c48d219
Apache-2.0
2020-01-25T00:16:13.000Z
2020-04-23T04:25:13.000Z
notebooks/Connected Components -- FastSV.ipynb
jim22k/grblas
7c96ddd3cb485f2c98637e7fb96070ff6c48d219
Apache-2.0
2020-03-10T16:28:22.000Z
2020-07-22T02:13:52.000Z
notebooks/Connected Components -- FastSV.ipynb
jim22k/grblas
7c96ddd3cb485f2c98637e7fb96070ff6c48d219
Apache-2.0
2020-03-13T21:39:50.000Z
2020-03-13T21:39:50.000Z
Qwen/Qwen-72B
1. YES
2. YES