experimental/algorithm/LAGraph_BF_pure_c_double.c
GrB_Info LAGraph_BF_pure_c_double
(
    double **pd,     // pointer to distance vector d, d(k) = shorstest distance
                     // between s and k if k is reachable from s
    int64_t **ppi,   // pointer to parent index vector pi, pi(k) = parent of
                     // node k in the shortest path tree
    const int64_t s, // given source node index
    const int64_t n, // number of nodes
    const int64_t nz,// number of edges
    const int64_t *I,// row index vector
    const int64_t *J,// column index vector
    const double  *W // weight vector, W(i) = weight of edge (I(i),J(i))
)
{
    int64_t i, j, k;
    double *d = NULL;
    int64_t *pi = NULL;
    if (I == NULL || J == NULL || W == NULL || pd == NULL || ppi == NULL)
    {
        // required argument is missing
        LAGRAPH_ERROR ("required arguments are NULL", GrB_NULL_POINTER) ;
    }

    if (*pd != NULL) {free(*pd);}
    if (*ppi != NULL) {free(*ppi);}
    *pd = NULL; *ppi = NULL;

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

    // allocate d and pi
    d = LAGraph_Malloc(n, sizeof(double));
    pi = LAGraph_Malloc(n, sizeof(int64_t));
    if (d == NULL || pi == NULL)
    {
        // out of memory
         LAGRAPH_ERROR ("out of memory", GrB_OUT_OF_MEMORY) ;
    }

    // initialize d to a vector of INF while set d(s) = 0
    // and pi to a vector of -1
    for (i = 0; i < n; i++)
    {
        d[i] = INFINITY;
        pi[i] = -1;
    }
    d[s] = 0;
    // start the RELAX process and print results after each loop
    bool new_path = true;     //variable indicating if new path is found
    int64_t count = 0;        //number of loops
    // terminate when no new path is found or more than n-1 loops
    while(new_path && count < n-1)
    {
        new_path = false;
        for (k = 0; k < nz; k++)
        {
            i = I[k];
            j = J[k];
            if (d[j] > d[i] + W[k])
            {
                d[j] = d[i] + W[k];
                pi[j] = i;
                new_path = true;
            }
        }
        count++;
    }

    // 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 (new_path)
    {
        // Do another loop of RELAX to check for negative loop,
        // return true if there is negative-weight cycle;
        // otherwise, print the distance vector and return false.
        for (k = 0; k < nz; k++)
        {
            i = I[k];
            j = J[k];
            if (d[j] > d[i] + W[k])
            {
                // printf("A negative-weight cycle exists. \n");
                LAGraph_FREE_ALL;
                return (GrB_NO_VALUE) ;
            }
        }
    }

    *pd = d;
    *ppi = pi;
    return (GrB_SUCCESS) ;
 }
// Given the edges and corresponding weights of a graph in tuple
// form {I, J, W} and a source vertex s. If there is no negative-weight
// cycle reachable from s, returns GrB_SUCCESS and the shortest distance
// d and the shortest path tree pi. Otherwise return NULL pointer for d
// and pi.
Given the edges and corresponding weights of a graph in tuple
form {I, J, W} and a source vertex s. If there is no negative-weight
cycle reachable from s, returns GrB_SUCCESS and the shortest distance
d and the shortest path tree pi. Otherwise return NULL pointer for d
and pi.
Given the edges and corresponding weights of a graph in tuple form { I J W } and a source vertex s . If there is no negative - weight cycle reachable from s returns GrB_SUCCESS and the shortest distance d and the shortest path tree pi . Otherwise return NULL pointer for d and pi .
GrB_Info LAGraph_BF_pure_c_double
(
    double **pd,     
    int64_t **ppi,   
    const int64_t s, 
    const int64_t n, 
    const int64_t nz,
    const int64_t *I,
    const int64_t *J,
    const double  *W 
)
{
    int64_t i, j, k;
    double *d = NULL;
    int64_t *pi = NULL;
    if (I == NULL || J == NULL || W == NULL || pd == NULL || ppi == NULL)
    {
        LAGRAPH_ERROR ("required arguments are NULL", GrB_NULL_POINTER) ;
    }
    if (*pd != NULL) {free(*pd);}
    if (*ppi != NULL) {free(*ppi);}
    *pd = NULL; *ppi = NULL;
    if (s >= n || s < 0)
    {
        LAGRAPH_ERROR ("invalid value for source vertex s", GrB_INVALID_VALUE) ;
    }
    d = LAGraph_Malloc(n, sizeof(double));
    pi = LAGraph_Malloc(n, sizeof(int64_t));
    if (d == NULL || pi == NULL)
    {
         LAGRAPH_ERROR ("out of memory", GrB_OUT_OF_MEMORY) ;
    }
    for (i = 0; i < n; i++)
    {
        d[i] = INFINITY;
        pi[i] = -1;
    }
    d[s] = 0;
    bool new_path = true;     
    int64_t count = 0;        
    while(new_path && count < n-1)
    {
        new_path = false;
        for (k = 0; k < nz; k++)
        {
            i = I[k];
            j = J[k];
            if (d[j] > d[i] + W[k])
            {
                d[j] = d[i] + W[k];
                pi[j] = i;
                new_path = true;
            }
        }
        count++;
    }
    if (new_path)
    {
        for (k = 0; k < nz; k++)
        {
            i = I[k];
            j = J[k];
            if (d[j] > d[i] + W[k])
            {
                LAGraph_FREE_ALL;
                return (GrB_NO_VALUE) ;
            }
        }
    }
    *pd = d;
    *ppi = pi;
    return (GrB_SUCCESS) ;
 }
GrB_Info LAGraph_BF_pure_c_double ( double * * pd , int64_t * * ppi , const int64_t s , const int64_t n , const int64_t nz , const int64_t * I , const int64_t * J , const double * W ) { int64_t i , j , k ; double * d = NULL ; int64_t * pi = NULL ; if ( I == NULL || J == NULL || W == NULL || pd == NULL || ppi == NULL ) { LAGRAPH_ERROR ( " " , GrB_NULL_POINTER ) ; } if ( * pd != NULL ) { free ( * pd ) ; } if ( * ppi != NULL ) { free ( * ppi ) ; } * pd = NULL ; * ppi = NULL ; if ( s >= n || s < 0 ) { LAGRAPH_ERROR ( " " , GrB_INVALID_VALUE ) ; } d = LAGraph_Malloc ( n , sizeof ( double ) ) ; pi = LAGraph_Malloc ( n , sizeof ( int64_t ) ) ; if ( d == NULL || pi == NULL ) { LAGRAPH_ERROR ( " " , GrB_OUT_OF_MEMORY ) ; } for ( i = 0 ; i < n ; i ++ ) { d [ i ] = INFINITY ; pi [ i ] = -1 ; } d [ s ] = 0 ; bool new_path = true ; int64_t count = 0 ; while ( new_path && count < n - 1 ) { new_path = false ; for ( k = 0 ; k < nz ; k ++ ) { i = I [ k ] ; j = J [ k ] ; if ( d [ j ] > d [ i ] + W [ k ] ) { d [ j ] = d [ i ] + W [ k ] ; pi [ j ] = i ; new_path = true ; } } count ++ ; } if ( new_path ) { for ( k = 0 ; k < nz ; k ++ ) { i = I [ k ] ; j = J [ k ] ; if ( d [ j ] > d [ i ] + W [ k ] ) { LAGraph_FREE_ALL ; return ( GrB_NO_VALUE ) ; } } } * pd = d ; * ppi = pi ; return ( GrB_SUCCESS ) ; }
Given the edges and corresponding weights of a graph in tuple
form {I, J, W} and a source vertex s. If there is no negative-weight
cycle reachable from s, returns GrB_SUCCESS and the shortest distance
d and the shortest path tree pi.
Given the edges and corresponding weights of a graph in tuple form { I J W } and a source vertex s . If there is no negative - weight cycle reachable from s returns GrB_SUCCESS and the shortest distance d and the shortest path tree pi .
// pointer to distance vector d, d(k) = shorstest distance // between s and k if k is reachable from s // pointer to parent index vector pi, pi(k) = parent of // node k in the shortest path tree // given source node index // number of nodes // number of edges // row index vector // column index vector // weight vector, W(i) = weight of edge (I(i),J(i)) // required argument is missing // allocate d and pi // out of memory // initialize d to a vector of INF while set d(s) = 0 // and pi to a vector of -1 // start the RELAX process and print results after each loop //variable indicating if new path is found //number of loops // terminate when no new path is found or more than n-1 loops // 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. // Do another loop of RELAX to check for negative loop, // return true if there is negative-weight cycle; // otherwise, print the distance vector and return false. // printf("A negative-weight cycle exists. \n");