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_mxv: Bellman-Ford single source shortest paths, returning
19 : // just the shortest path lengths.
20 :
21 : // LAGraph_BF_basic_mxv performs a Bellman-Ford to find out shortest path length
22 : // from given source vertex s in the range of [0, n) on graph with n nodes.
23 : // It works almost the same as LAGraph_BF_basic except that it performs update
24 : // using GrB_mxv instead of GrB_vxm, therefore, it require the input matrix as
25 : // the transpose of adjacency matrix A with size n by n. That is, the input
26 : // sparse matrix has entry AT(i, j) if there is edge from vertex j to vertex i
27 : // with weight w, then AT(i, j) = w. While same as LAGraph_BF_basic, it requires
28 : // AT(i, i) = 0 for all 0 <= i < n.
29 :
30 : // LAGraph_BF_basic_mxv returns GrB_SUCCESS if it succeeds. In this case, there
31 : // are no negative-weight cycles in the graph, and the vector d is returned.
32 : // d(k) is the shortest distance from s to k.
33 :
34 : // If the graph has a negative-weight cycle, GrB_NO_VALUE is returned, and the
35 : // GrB_Vector d (i.e., *pd_output) will be NULL.
36 :
37 : // Otherwise, other errors such as GrB_OUT_OF_MEMORY, GrB_INVALID_OBJECT, and
38 : // so on, can be returned, if these errors are found by the underlying
39 : // GrB_* functions.
40 : //------------------------------------------------------------------------------
41 :
42 : #define LG_FREE_ALL \
43 : { \
44 : GrB_free(&d) ; \
45 : GrB_free(&dtmp) ; \
46 : }
47 :
48 : #include <LAGraph.h>
49 : #include <LAGraphX.h>
50 : #include <LG_internal.h> // from src/utility
51 :
52 :
53 : // Given the transposed of a n-by-n adjacency matrix A and a source vertex s.
54 : // If there is no negative-weight cycle reachable from s, return the distances
55 : // of shortest paths from s as vector d. Otherwise, return d=NULL if there is
56 : // negative-weight cycle.
57 : // pd_output = &d, where d is a GrB_Vector with d(k) as the shortest distance
58 : // from s to k when no negative-weight cycle detected, otherwise, d = NULL.
59 : // AT has zeros on diagonal and weights on corresponding entries of edges
60 : // s is given index for source vertex
61 5 : GrB_Info LAGraph_BF_basic_mxv
62 : (
63 : GrB_Vector *pd_output, //the pointer to the vector of distance
64 : const GrB_Matrix AT, //transposed adjacency matrix for the graph
65 : const GrB_Index s //given index of the source
66 : )
67 : {
68 : GrB_Info info;
69 5 : char *msg = NULL ;
70 : GrB_Index nrows, ncols;
71 : // tmp vector to store distance vector after n loops
72 5 : GrB_Vector d = NULL, dtmp = NULL;
73 :
74 5 : LG_ASSERT (AT != NULL && pd_output != NULL, GrB_NULL_POINTER) ;
75 :
76 5 : *pd_output = NULL;
77 5 : GRB_TRY (GrB_Matrix_nrows (&nrows, AT)) ;
78 5 : GRB_TRY (GrB_Matrix_ncols (&ncols, AT)) ;
79 5 : LG_ASSERT_MSG (nrows == ncols, -1002, "AT must be square") ;
80 5 : GrB_Index n = nrows; // n = # of vertices in graph
81 5 : LG_ASSERT_MSG (s < n, GrB_INVALID_INDEX, "invalid source node") ;
82 :
83 : // Initialize distance vector, change the d[s] to 0
84 5 : GRB_TRY (GrB_Vector_new(&d, GrB_FP64, n));
85 5 : GRB_TRY (GrB_Vector_setElement_FP64(d, 0, s));
86 :
87 : // copy d to dtmp in order to create a same size of vector
88 5 : GRB_TRY (GrB_Vector_dup(&dtmp, d));
89 :
90 5 : int64_t iter = 0; //number of iterations
91 5 : bool same = false; //variable indicating if d == dtmp
92 :
93 : // terminate when no new path is found or more than n-1 loops
94 93 : while (!same && iter < n - 1)
95 : {
96 : // excute semiring on d and AT, and save the result to d
97 88 : GRB_TRY (GrB_mxv(dtmp, GrB_NULL, GrB_NULL, GrB_MIN_PLUS_SEMIRING_FP64,
98 : AT, d, GrB_NULL));
99 :
100 88 : LG_TRY (LAGraph_Vector_IsEqual (&same, dtmp, d, NULL));
101 88 : if (!same)
102 : {
103 85 : GrB_Vector ttmp = dtmp;
104 85 : dtmp = d;
105 85 : d = ttmp;
106 : }
107 88 : iter++;
108 : }
109 :
110 : // check for negative-weight cycle only when there was a new path in the
111 : // last loop, otherwise, there can't be a negative-weight cycle.
112 5 : if (!same)
113 : {
114 : // excute semiring again to check for negative-weight cycle
115 2 : GRB_TRY (GrB_mxv(dtmp, GrB_NULL, GrB_NULL, GrB_MIN_PLUS_SEMIRING_FP64,
116 : AT, d, GrB_NULL));
117 :
118 : // if d != dtmp, then there is a negative-weight cycle in the graph
119 2 : LG_TRY (LAGraph_Vector_IsEqual (&same, dtmp, d, NULL));
120 2 : if (!same)
121 : {
122 : // printf("AT negative-weight cycle found. \n");
123 2 : LG_FREE_ALL;
124 2 : return (GrB_NO_VALUE) ;
125 : }
126 : }
127 :
128 3 : (*pd_output) = d;
129 3 : d = NULL;
130 3 : LG_FREE_ALL;
131 3 : return (GrB_SUCCESS) ;
132 : }
|
