Extract matrix values (edges) used in a VxM about graphblas HOT 13 CLOSED

from graphblas.

Practically, I have run an s-t max-flow algorithm on a graph and produced the residual graph R, and I am trying to efficiently find the min-cut.

Performing a breadth-first search from the source s in R, I can determine all vertices reachable from the source, the s-set.

A picture of an example graph G. The marked edges are the min-cut edges I want to extract. Those, along with other edges used at full capacity in the max-flow algorithm would not be in R, which is why a breadth-first search starting from the source-vertex on the left would produce s.

In order to find the vertices at the t-side of the cut, I can perform a single VxM operation t<s'> = s * G, where G is the original graph input. What I think I am doing here is using the aquired s as frontier and traversing outward from it into the graph, but ignoring any vertices already present in s by using the mask.

In this last VxM operation, the "traversed edges" are the ones I wan to extract, which is why I asked if there is some way of inspecting which matrix-values are actually used in a VxM operation.

My current method for extracting the min-cut is simply iterating over all the vertex pairs (i,j), i in s, j in t and seeing if there is an edge (i,j) in the graph. Becaue this method has a time complexity of O(n^2), it doesn't quite cut it.

from graphblas.

call the first node on the left A and the last node on the right B.

on the s side, do the multiplication forward twice to find all 2 degrees nodes from A.

then on the t side when you do the multiplication backwards from B (aka by the transpose of the edge matrix), simply mask the output of that multiplication by the edges reached in the 1st operation.

this gives you the intersection, aka t.

from graphblas.

from graphblas.

@DrTimothyAldenDavis i think the point is that they start with the 2 distant nodes, and the assumption there exists one or more 3rd degree mappings between them, and want to extract all nodes that participate in that mapping. (from left to right).

from graphblas.

from graphblas.

Sorry for being unclear. What I want is indeed the (1) alternative you presented here, a list of 6 edges as (i,j,x) triplets.

To use GrB_extract, it seems I need the (i,j) tuples already available in the form of row_indices and col_indices vectors. The problem for me then is constructing these two vectors.

from graphblas.

from graphblas.

from graphblas.

Got it to work. Below I am assuming s contains only the vertices adjacent to the cut, not the somewhat confusing s-set I drew earlier. The process I ended up going for:

1. GrB_extractTuples on s and t
2. GrB_extract on A using the indices from 1., constructing a new matrix C
3. GrB_extractTuples on C
4. Translate the indices in 3. back to indices in the original matrix A by re-using the indices from 1.
   Note: This is just a sequential for-loop over the arrays
5. Construct a new matrix using the values from 3. and the translated indices from 4.

Ideally there could have been a way to use s and t to perform a kind of extract/filter/mask on the orignal matrix while keeping its structure intact, which would have reduced this process to a single step. But, this worked, and saved me a whole lot of time compared to calling GrB_extractElement n^2 times 😅

from graphblas.

from graphblas.

When you say assign is a powerful (and I assume heavy) operation, does that mean other GraphBLAS functions might be faster even if assign is the most "intuitive"?

Specifially, in one part of my program I need to extract the elements in a matrix corresponding to a boolean mask. I can either do this using an um-masked element-wise multiplication or a masked assign.

Similarly when assigning one value to all the exisiting elements in a matrix, I can either perform a masked assign or an un-masked apply (by providing a unary function that always returns the same value).

In these cases, assign seems most intuitive, but I am unsure if it implies the best performance.

from graphblas.

from graphblas.