Implementing BFS

[samuel-esp]

Hi guys,

I'm trying to implement the BFS-Level algorithm defined in this presentation but I'm facing several problems regarding any pairs semiring and nothing values. I'm quite new to the language as well but this is the implementation i tried

#A is the input matrix, s is the source node, and n is the number of nodes
function bfs_level(A, s, n)
     
    #frontier init
    frontier = GBVector{Bool}(n)
        for i = 1:n
            frontier[i] = false
        end
    
    #init result vector
    distance = GBVector{Int64}(n)
        for i = 1:n
            distance[i] = 0
        end
    
    #putting source node inside the frontier
    frontier[s]= true
    
    print("starting from source node\n\n")
    for level = 1:n
            print(frontier)
            distance[frontier] .= level
            frontier = mul(frontier, A, Semirings.ANY_PAIR, mask=distance, desc=Descriptors.C)
            print(distance)
    end
    end

i tried the algorithm against this input

#0, 1, 1, 1, 0, 0, 0, 
#0, 0, 0, 0, 0, 0, 0, 
#0, 0, 0, 0, 0, 0, 0, 
#0, 0, 0, 0, 0, 1, 0, 
#0, 0, 0, 0, 0, 0, 0, 
#0, 0, 0, 0, 0, 0, 1, 
#0, 0, 0, 0, 1, 0, 0, 

matrix =  GBMatrix([[0, 0, 0, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 1] [0, 0, 0, 1, 0, 0, 0] [0, 0, 0, 0, 0, 1, 0]])
bfs_level(matrix, 1, 7)

the Any_Pairs semirings should return 0, 1, 1, 1, 0, 0, 0 according to the matrix above but i'm getting [nothing, 1, 1, 1, 1, 1, 1]

I think I didn't understand quite well how to implement masking even if I succeded in implementing the Bellman Ford algorithm. Sorry again to bother you for this kind of issues

[rayegun]

No bother at all! Thanks for trying it out, and sorry it's not a smooth experience yet.

I have some ideas, and there's definitely some fixes to make on my end. Give me a day or two and I'll post a working solution that works on the #master branch.

*Note in particular that indexing with GBVectors isn't working correctly right now. But I'll get it fixed!

[samuel-esp]

Thanks for your answer and don't worry! I see it's still in an early phase but definetely keep going because it's interesting to use this library! I'll wait for the fix and I'll try to implement other algorithms in the meanwhile

[samuel-esp]

I actually managed to solve the problem and to implement the algorithm:

1. Converted the input matrix to Bool values (true and false)
2. Used the LOR_LAND semirings instead of ANY_PAIR
3. Finally and most important I deleted the mask and the desc from the mul operation, it seems there is a problem computing the output of a mask in the following operations but should be because of Julia, nothing values can cause problems when used as input to other operations (even in print statements sometimes)

EDIT: not using masks can degrade the performance of the algorithm from what I know but won't cause problems regarding the output of the algorithm

[rayegun]

I probably didn't cover some operation properly, which means it falls back to Julia, and Julia doesn't like nothing values in arrays.

I spent today figuring out some memory issues, but I'll get the original working asap!

[samuel-esp]

Thanks for the update!

PS=I looked at the code and the assign operation is not implemented, is there a work around for this at the moment? I need to compute an assign + mask operation

[rayegun]

assign! should be there. Line 423 of matrix.jl. You should just be able to use setindex! though. *Perhaps assign is only on master, but I think it was implemented very early on.

A[1:5,1:2:10, mask=B] = C should work. Note that uses subassign not assign. So you're mask will be the size of C not the size of A. If you need the mask to be the size of A you have to use assign!.

[samuel-esp]

Hey man thanks for the tip, i think I found another problem on MIN_FIRST semiring to compute parents inside the BFS. unfortunately this time I didn't managed to find a workaround

#A is the input matrix, s is the source node, and n is the number of nodes
function bfs_parents(A, s, n)
     
    index = GBVector{Int64}(n)
        for i = 1:n
            index[i] = i
        end
    print(index)
    
    #wavefront vector -> w[s]=source node insrted in wavefront
    f = GBVector{Int64}(n)
    f[s] = 1

    #parent vector -> p[s]=1 because the source is already visited
    p = GBVector{Int64}(n)
    p[s] = 0
    
    
    print("INIZIO\n\n")
    for i = 1:n-1
            f = mul(f, A, Semirings.MIN_FIRST, mask=p, desc=Descriptors.RSC)
            p = f[:, mask=f]
            f = index[:, mask=f]
            
    end
    
    print(p)
    
end

And my input (which is the same represented in the photo below) (source)

matrix =  GBMatrix([[0, 0, 0, 1, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0] [0, 0, 0, 1, 0, 1, 1] [1, 0, 0, 0, 0, 0, 1] [0, 1, 0, 0, 0, 0, 1] [0, 0, 1, 0, 1, 0, 0] [0, 1, 0, 0, 0, 0, 0]])
bfs_parents(matrix, 1, 7)

The min first operation in the semiring should return [nothing, 1, 0, 1, 0, 0, 0] but instead it returns [nothing, 1, 1, 1, 1, 1, 1]. The computation seems to be made on every row but instead should be done only in the selected rows. I just hope I'm not misunderstanding this operation in some way I can't figure it out right now. Thanks again for your patience

[rayegun]

Why would you want it to be [nothing, 1, 0, 1, 0,0,0]? You want it to be [nothing, 1, nothing, 1, nothing, nothing, nothing], otherwise you've got essentially a dense matrix. Note GraphBLAS sparse matrices treat structural zeros as nothing not 0 since you could have a sparse matrix with materialized 0 values.

matrix = GBMatrix([[0, 0, 0, 1, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0] [0, 0, 0, 1, 0, 1, 1] [1, 0, 0, 0, 0, 0, 1] [0, 1, 0, 0, 0, 0, 1] [0, 0, 1, 0, 1, 0, 0] [0, 1, 0, 0, 0, 0, 0]]) this is probably your biggest problem.

This is a full matrix of mostly zeros, not a sparse one. You can either do:

using SparseArrays
matrix =  GBMatrix(sparse([[0, 0, 0, 1, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0] [0, 0, 0, 1, 0, 1, 1] [1, 0, 0, 0, 0, 0, 1] [0, 1, 0, 0, 0, 0, 1] [0, 0, 1, 0, 1, 0, 0] [0, 1, 0, 0, 0, 0, 0]]))

or

matrix =  GBMatrix([[0, 0, 0, 1, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0] [0, 0, 0, 1, 0, 1, 1] [1, 0, 0, 0, 0, 0, 1] [0, 1, 0, 0, 0, 0, 1] [0, 0, 1, 0, 1, 0, 0] [0, 1, 0, 0, 0, 0, 0]])
select!(SelectOps.NONZERO, matrix, matrix)

Or more idiomatically:

matrix = GBMatrix([4,1,4,6,7,1,7,2,7,3,5,2], [1,2,3,3,3,4,4,5,5,6,6,7], ones(Int64, 7))

which is the cooordinate form.

GraphBLAS treats zeros as actual numbers, which is not what SparseArrays does. I'm making a package that will behave like SparseArrays, but for graph algorithms you don't want this anyway.

I'm going to write a BFS example this weekend, I'm just working on getting the next version out at the same time. So bear with me! :)

[samuel-esp]

Thanks man this tip solved my issue and i think this was the issue I had with the original post as well! I'm gonna try it tomorrow on the original algorithm i posted to check! I thought that 0 was equivalent to nothing and this was my problem! One more thing, citing your answer a couple of days ago regarding the assign command

A[1:5,1:2:10, mask=B] = C

in the single parents bfs implementation i used this command and it worked like a charm

f = index[:, mask=f, desc=Descriptors.S]

basically it was for mapping index values (1, 2, 3, 4, 5 ecc...) to non-nothing f values to f (both index and f are vectors)

Then i tried to implement the multi bfs parents algorithm, to compute more parents istances of different nodes at the same time. When i try to do the same assignment but with 2 matrices i get an error, both F and index are 3*7 matrices in this case with the same purposes of the line before (mapping from index to f non-nothing values)

F = index[:, :, mask=F, desc=Descriptors.S]

example

[1, 2, 3, 4, 5, 6, 7; 1, 2, 3, 4, 5, 6, 7; 1, 2, 3, 4, 5, 6, 7] and [1, nothing 1, nothing, nothing ... ; nothing, 1, nothign ... ; 1, nothing, nothing... ]

result [1, nothing, 3, nothing, nothing ... ; nothing, 2, nothing, 1 ... ; 1, nothing, nothing ...]

MethodError: no method matching getindex(::Transpose{Int64, GBMatrix{Int64}}, ::Colon, ::Colon; mask=[nothing 1 … nothing nothing; nothing nothing … 1 nothing; 1 nothing … nothing nothing], desc=Descriptor(Ptr{SuiteSparseGraphBLAS.libgb.GB_Descriptor_opaque} @0x000000017ddbe398))

[rayegun]

That's a missing method on my part, it looks like index is transposed. I'll add it for the next release!

[samuel-esp]

Thanks again man! I'll try without transposing and see how it goes. I completed about 13/14 algorithms using the library till now and it was smooth, now I'll try to optimize them using the sparse keywords on the input matrices

[rayegun]

@samuel-esp do you mind making a PR to add your algorithms as examples? I can edit them, and figure out where I need to make changes to the API before the next release (hopefully in the next couple days)?

[samuel-esp]

Hey man, I can of course make a PR on your repo but not before September 10 because I'm actually on holiday and didn't bring my laptop with me, I don't know if I can make a PR from mobile but I don't think I can from the app. Actually you can check my examples from my public repo, so if you need to plan some corrections you can already see

[rayegun]

Ok I can still use them to figure out what I'm missing from the API. Then when you're back we can put them in as examples and polish.

Enjoy your holiday!

[samuel-esp]

Hey man, I'm back from holiday and as promised I made the pull request. Feel free to review it on your free time, i could have forgotten some print statements inside the files so remove them just in case