Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGraph_BF_basic: Bellman-Ford method for single source shortest paths
       3             : //------------------------------------------------------------------------------
       4             : 
       5             : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
       6             : // SPDX-License-Identifier: BSD-2-Clause
       7             : //
       8             : // For additional details (including references to third party source code and
       9             : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
      10             : // Contributors.txt for a full list of contributors. Created, in part, with
      11             : // funding and support from the U.S. Government (see Acknowledgments.txt file).
      12             : // DM22-0790
      13             : 
      14             : // Contributed by Jinhao Chen and Timothy A. Davis, Texas A&M University
      15             : 
      16             : //------------------------------------------------------------------------------
      17             : 
      18             : // LAGraph_BF_basic: Bellman-Ford single source shortest paths, returning just
      19             : // the shortest path lengths.
      20             : 
      21             : // LAGraph_BF_basic performs a Bellman-Ford to find out shortest path length
      22             : // from given source vertex s in the range of [0, n) on graph given as matrix A
      23             : // with size n by n. The sparse matrix A has entry A(i, j) if there is edge from
      24             : // vertex i to vertex j with weight w, then A(i, j) = w. Furthermore,
      25             : // LAGraph_BF_basic requires A(i, i) = 0 for all 0 <= i < n.
      26             : 
      27             : // LAGraph_BF_basic returns GrB_SUCCESS regardless of existence of
      28             : // negative-weight cycle. However, the GrB_Vector d(k) (i.e., *pd_output) will
      29             : // be NULL when negative-weight cycle detected. Otherwise, the vector d has
      30             : // d(k) as the shortest distance from s to k.
      31             : 
      32             : //------------------------------------------------------------------------------
      33             : 
      34             : #define LG_FREE_ALL        \
      35             : {                          \
      36             :     GrB_free(&d) ;         \
      37             :     GrB_free(&dtmp) ;      \
      38             : }
      39             : 
      40             : #include "LG_internal.h"
      41             : #include <LAGraphX.h>
      42             : 
      43             : // Given a n-by-n adjacency matrix A and a source vertex s.
      44             : // If there is no negative-weight cycle reachable from s, return the distances
      45             : // of shortest paths from s as vector d. Otherwise, return d=NULL if there is
      46             : // negative-weight cycle.
      47             : // pd_output = &d, where d is a GrB_Vector with d(k) as the shortest distance
      48             : // from s to k when no negative-weight cycle detected, otherwise, d = NULL.
      49             : // A has zeros on diagonal and weights on corresponding entries of edges
      50             : // s is given index for source vertex
      51           5 : GrB_Info LAGraph_BF_basic
      52             : (
      53             :     GrB_Vector *pd_output,      //the pointer to the vector of distance
      54             :     const GrB_Matrix A,         //matrix for the graph
      55             :     const GrB_Index s           //given index of the source
      56             : )
      57             : {
      58             :     GrB_Info info;
      59           5 :     char *msg = NULL ;
      60             :     GrB_Index nrows, ncols;
      61             :     // tmp vector to store distance vector after n (i.e., V) loops
      62           5 :     GrB_Vector d = NULL, dtmp = NULL;
      63             : 
      64           5 :     LG_ASSERT (A != NULL && pd_output != NULL, GrB_NULL_POINTER) ;
      65             : 
      66           5 :     *pd_output = NULL;
      67           5 :     GRB_TRY (GrB_Matrix_nrows (&nrows, A)) ;
      68           5 :     GRB_TRY (GrB_Matrix_ncols (&ncols, A)) ;
      69           5 :     LG_ASSERT_MSG (nrows == ncols, -1002, "A must be square") ;
      70           5 :     GrB_Index n = nrows;           // n = # of vertices in graph
      71           5 :     LG_ASSERT_MSG (s < n, GrB_INVALID_INDEX, "invalid source node") ;
      72             : 
      73             :     // Initialize distance vector, change the d[s] to 0
      74           5 :     GRB_TRY (GrB_Vector_new(&d, GrB_FP64, n));
      75           5 :     GRB_TRY (GrB_Vector_setElement_FP64(d, 0, s));
      76             : 
      77             :     // copy d to dtmp in order to create a same size of vector
      78           5 :     GRB_TRY (GrB_Vector_dup(&dtmp, d));
      79             : 
      80           5 :     int64_t iter = 0;      //number of iterations
      81           5 :     bool same = false;     //variable indicating if d=dtmp
      82             : 
      83             :     // terminate when no new path is found or more than n-1 loops
      84          93 :     while (!same && iter < n - 1)
      85             :     {
      86             : 
      87          88 :         double t = LAGraph_WallClockTime ( ) ;
      88             : 
      89             :         // execute semiring on d and A, and save the result to d
      90          88 :         GRB_TRY (GrB_vxm(dtmp, GrB_NULL, GrB_NULL, GrB_MIN_PLUS_SEMIRING_FP64, d, A,
      91             :             GrB_NULL));
      92          88 :         LG_TRY (LAGraph_Vector_IsEqual (&same, dtmp, d, NULL));
      93          88 :         if (!same)
      94             :         {
      95          85 :             GrB_Vector ttmp = dtmp;
      96          85 :             dtmp = d;
      97          85 :             d = ttmp;
      98             :         }
      99          88 :         iter++;
     100          88 :         t = LAGraph_WallClockTime ( ) - t ;
     101             :         GrB_Index dnz ;
     102          88 :         GRB_TRY (GrB_Vector_nvals (&dnz, d)) ;
     103             : //      printf ("step %3d time %16.4f sec, nvals %.16g\n", iter, t, (double) dnz);
     104          88 :         fflush (stdout) ;
     105             :     }
     106             : 
     107             :     // check for negative-weight cycle only when there was a new path in the
     108             :     // last loop, otherwise, there can't be a negative-weight cycle.
     109           5 :     if (!same)
     110             :     {
     111             :         // execute semiring again to check for negative-weight cycle
     112           2 :         GRB_TRY (GrB_vxm(dtmp, GrB_NULL, GrB_NULL, GrB_MIN_PLUS_SEMIRING_FP64, d, A,
     113             :             GrB_NULL));
     114           2 :         LG_TRY (LAGraph_Vector_IsEqual (&same, dtmp, d, NULL));
     115             : 
     116             :         // if d != dtmp, then there is a negative-weight cycle in the graph
     117           2 :         if (!same)
     118             :         {
     119             :             // printf("A negative-weight cycle found. \n");
     120           2 :             LG_FREE_ALL;
     121           2 :             return (GrB_NO_VALUE) ;
     122             :         }
     123             :     }
     124             : 
     125           3 :     (*pd_output) = d;
     126           3 :     d = NULL;
     127           3 :     LG_FREE_ALL;
     128           3 :     return (GrB_SUCCESS) ;
     129             : }