experimental/algorithm/LAGraph_BF_basic.c
GrB_Info LAGraph_BF_basic
(
    GrB_Vector *pd_output,      //the pointer to the vector of distance
    const GrB_Matrix A,         //matrix for the graph
    const GrB_Index s           //given index of the source
)
{
    GrB_Info info;
    GrB_Index nrows, ncols;
    // tmp vector to store distance vector after n (i.e., V) loops
    GrB_Vector d = NULL, dtmp = NULL;

    if (A == NULL || pd_output == NULL)
    {
        // required argument is missing
        LAGRAPH_ERROR ("required arguments are NULL", GrB_NULL_POINTER) ;
    }

    *pd_output = NULL;
    LAGRAPH_OK (GrB_Matrix_nrows (&nrows, A)) ;
    LAGRAPH_OK (GrB_Matrix_ncols (&ncols, A)) ;
    if (nrows != ncols)
    {
        // A must be square
        LAGRAPH_ERROR ("A must be square", GrB_INVALID_VALUE) ;
    }
    GrB_Index n = nrows;           // n = # of vertices in graph

    if (s >= n || s < 0)
    {
        LAGRAPH_ERROR ("invalid value for source vertex s", GrB_INVALID_VALUE) ;
    }

    // Initialize distance vector, change the d[s] to 0
    LAGRAPH_OK (GrB_Vector_new(&d, GrB_FP64, n));
    LAGRAPH_OK (GrB_Vector_setElement_FP64(d, 0, s));

    // copy d to dtmp in order to create a same size of vector
    LAGRAPH_OK (GrB_Vector_dup(&dtmp, d));

    int64_t iter = 0;      //number of iterations
    bool same = false;     //variable indicating if d=dtmp

    // terminate when no new path is found or more than n-1 loops
    while (!same && iter < n - 1)
    {

        double tic [2] ;
        LAGraph_Tic(tic, NULL);

        // execute semiring on d and A, and save the result to d
        LAGRAPH_OK (GrB_vxm(dtmp, GrB_NULL, GrB_NULL, GrB_MIN_PLUS_SEMIRING_FP64, d, A,
            GrB_NULL));
        LAGRAPH_OK (LAGraph_Vector_IsEqual_type(&same, dtmp, d, GrB_FP64, NULL));
        if (!same)
        {
            GrB_Vector ttmp = dtmp;
            dtmp = d;
            d = ttmp;
        }
        iter++;
        double t;
        LAGraph_Toc (&t, tic, NULL );
        GrB_Index dnz ;
        LAGRAPH_OK (GrB_Vector_nvals (&dnz, d)) ;
//      printf ("step %3d time %16.4f sec, nvals %.16g\n", iter, t, (double) dnz);
        fflush (stdout) ;
    }

    // check for negative-weight cycle only when there was a new path in the
    // last loop, otherwise, there can't be a negative-weight cycle.
    if (!same)
    {
        // execute semiring again to check for negative-weight cycle
        LAGRAPH_OK (GrB_vxm(dtmp, GrB_NULL, GrB_NULL, GrB_MIN_PLUS_SEMIRING_FP64, d, A,
            GrB_NULL));
        LAGRAPH_OK (LAGraph_Vector_IsEqual_type(&same, dtmp, d, GrB_FP64, NULL));

        // if d != dtmp, then there is a negative-weight cycle in the graph
        if (!same)
        {
            // printf("A negative-weight cycle found. \n");
            LAGraph_FREE_ALL;
            return (GrB_SUCCESS) ;  // TODO: should be an error code
        }
    }

    (*pd_output) = d;
    d = NULL;
    LAGraph_FREE_ALL;
    return (GrB_SUCCESS) ;
}
// Given a n-by-n adjacency matrix A and a source vertex s.
// If there is no negative-weight cycle reachable from s, return the distances
// of shortest paths from s as vector d. Otherwise, return d=NULL if there is
// negative-weight cycle.
// pd_output = &d, where d is a GrB_Vector with d(k) as the shortest distance
// from s to k when no negative-weight cycle detected, otherwise, d = NULL.
// A has zeros on diagonal and weights on corresponding entries of edges
// s is given index for source vertex
Given a n-by-n adjacency matrix A and a source vertex s.
If there is no negative-weight cycle reachable from s, return the distances
of shortest paths from s as vector d. Otherwise, return d=NULL if there is
negative-weight cycle.
pd_output = &d, where d is a GrB_Vector with d(k) as the shortest distance
from s to k when no negative-weight cycle detected, otherwise, d = NULL.
A has zeros on diagonal and weights on corresponding entries of edges
s is given index for source vertex
Given a n - by - n adjacency matrix A and a source vertex s . If there is no negative - weight cycle reachable from s return the distances of shortest paths from s as vector d . Otherwise return d = NULL if there is negative - weight cycle . pd_output = &d where d is a GrB_Vector with d ( k ) as the shortest distance from s to k when no negative - weight cycle detected otherwise d = NULL . A has zeros on diagonal and weights on corresponding entries of edges s is given index for source vertex
GrB_Info LAGraph_BF_basic
(
    GrB_Vector *pd_output,      
    const GrB_Matrix A,         
    const GrB_Index s           
)
{
    GrB_Info info;
    GrB_Index nrows, ncols;
    GrB_Vector d = NULL, dtmp = NULL;
    if (A == NULL || pd_output == NULL)
    {
        LAGRAPH_ERROR ("required arguments are NULL", GrB_NULL_POINTER) ;
    }
    *pd_output = NULL;
    LAGRAPH_OK (GrB_Matrix_nrows (&nrows, A)) ;
    LAGRAPH_OK (GrB_Matrix_ncols (&ncols, A)) ;
    if (nrows != ncols)
    {
        LAGRAPH_ERROR ("A must be square", GrB_INVALID_VALUE) ;
    }
    GrB_Index n = nrows;           
    if (s >= n || s < 0)
    {
        LAGRAPH_ERROR ("invalid value for source vertex s", GrB_INVALID_VALUE) ;
    }
    LAGRAPH_OK (GrB_Vector_new(&d, GrB_FP64, n));
    LAGRAPH_OK (GrB_Vector_setElement_FP64(d, 0, s));
    LAGRAPH_OK (GrB_Vector_dup(&dtmp, d));
    int64_t iter = 0;      
    bool same = false;     
    while (!same && iter < n - 1)
    {
        double tic [2] ;
        LAGraph_Tic(tic, NULL);
        LAGRAPH_OK (GrB_vxm(dtmp, GrB_NULL, GrB_NULL, GrB_MIN_PLUS_SEMIRING_FP64, d, A,
            GrB_NULL));
        LAGRAPH_OK (LAGraph_Vector_IsEqual_type(&same, dtmp, d, GrB_FP64, NULL));
        if (!same)
        {
            GrB_Vector ttmp = dtmp;
            dtmp = d;
            d = ttmp;
        }
        iter++;
        double t;
        LAGraph_Toc (&t, tic, NULL );
        GrB_Index dnz ;
        LAGRAPH_OK (GrB_Vector_nvals (&dnz, d)) ;
        fflush (stdout) ;
    }
    if (!same)
    {
        LAGRAPH_OK (GrB_vxm(dtmp, GrB_NULL, GrB_NULL, GrB_MIN_PLUS_SEMIRING_FP64, d, A,
            GrB_NULL));
        LAGRAPH_OK (LAGraph_Vector_IsEqual_type(&same, dtmp, d, GrB_FP64, NULL));
        if (!same)
        {
            LAGraph_FREE_ALL;
            return (GrB_SUCCESS) ;  
        }
    }
    (*pd_output) = d;
    d = NULL;
    LAGraph_FREE_ALL;
    return (GrB_SUCCESS) ;
}
GrB_Info LAGraph_BF_basic ( GrB_Vector * pd_output , const GrB_Matrix A , const GrB_Index s ) { GrB_Info info ; GrB_Index nrows , ncols ; GrB_Vector d = NULL , dtmp = NULL ; if ( A == NULL || pd_output == NULL ) { LAGRAPH_ERROR ( " " , GrB_NULL_POINTER ) ; } * pd_output = NULL ; LAGRAPH_OK ( GrB_Matrix_nrows ( & nrows , A ) ) ; LAGRAPH_OK ( GrB_Matrix_ncols ( & ncols , A ) ) ; if ( nrows != ncols ) { LAGRAPH_ERROR ( " " , GrB_INVALID_VALUE ) ; } GrB_Index n = nrows ; if ( s >= n || s < 0 ) { LAGRAPH_ERROR ( " " , GrB_INVALID_VALUE ) ; } LAGRAPH_OK ( GrB_Vector_new ( & d , GrB_FP64 , n ) ) ; LAGRAPH_OK ( GrB_Vector_setElement_FP64 ( d , 0 , s ) ) ; LAGRAPH_OK ( GrB_Vector_dup ( & dtmp , d ) ) ; int64_t iter = 0 ; bool same = false ; while ( ! same && iter < n - 1 ) { double tic [ 2 ] ; LAGraph_Tic ( tic , NULL ) ; LAGRAPH_OK ( GrB_vxm ( dtmp , GrB_NULL , GrB_NULL , GrB_MIN_PLUS_SEMIRING_FP64 , d , A , GrB_NULL ) ) ; LAGRAPH_OK ( LAGraph_Vector_IsEqual_type ( & same , dtmp , d , GrB_FP64 , NULL ) ) ; if ( ! same ) { GrB_Vector ttmp = dtmp ; dtmp = d ; d = ttmp ; } iter ++ ; double t ; LAGraph_Toc ( & t , tic , NULL ) ; GrB_Index dnz ; LAGRAPH_OK ( GrB_Vector_nvals ( & dnz , d ) ) ; fflush ( stdout ) ; } if ( ! same ) { LAGRAPH_OK ( GrB_vxm ( dtmp , GrB_NULL , GrB_NULL , GrB_MIN_PLUS_SEMIRING_FP64 , d , A , GrB_NULL ) ) ; LAGRAPH_OK ( LAGraph_Vector_IsEqual_type ( & same , dtmp , d , GrB_FP64 , NULL ) ) ; if ( ! same ) { LAGraph_FREE_ALL ; return ( GrB_SUCCESS ) ; } } ( * pd_output ) = d ; d = NULL ; LAGraph_FREE_ALL ; return ( GrB_SUCCESS ) ; }
Given a n-by-n adjacency matrix A and a source vertex s.
If there is no negative-weight cycle reachable from s, return the distances
of shortest paths from s as vector d. Otherwise, return d=NULL if there is
negative-weight cycle.
Given a n - by - n adjacency matrix A and a source vertex s . If there is no negative - weight cycle reachable from s return the distances of shortest paths from s as vector d . Otherwise return d = NULL if there is negative - weight cycle .
//the pointer to the vector of distance //matrix for the graph //given index of the source // tmp vector to store distance vector after n (i.e., V) loops // required argument is missing // A must be square // n = # of vertices in graph // Initialize distance vector, change the d[s] to 0 // copy d to dtmp in order to create a same size of vector //number of iterations //variable indicating if d=dtmp // terminate when no new path is found or more than n-1 loops // execute semiring on d and A, and save the result to d //      printf ("step %3d time %16.4f sec, nvals %.16g\n", iter, t, (double) dnz); // check for negative-weight cycle only when there was a new path in the // last loop, otherwise, there can't be a negative-weight cycle. // execute semiring again to check for negative-weight cycle // if d != dtmp, then there is a negative-weight cycle in the graph // printf("A negative-weight cycle found. \n"); // TODO: should be an error code