Line data Source code
1 : //------------------------------------------------------------------------------
2 : // BF_pure_c.c: Bellman-Ford method, not using GraphBLAS
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_pure_c: Bellman-Ford single source shortest paths, returning
19 : // both the path lengths and the shortest-path tree.
20 :
21 : // LAGraph_BF_pure_c performs the Bellman-Ford algorithm to find out shortest
22 : // path length, parent nodes along the path from given source vertex s in the
23 : // range of [0, n) on graph with n nodes. It is implemented purely using
24 : // conventional method, and is single-threaded. It is used here for checking
25 : // the correctness of the result and comparison with the Bellman Ford
26 : // implemented based on LAGraph. Therefore, it require the graph represented
27 : // as triplet format (I, J, W), which is an edge from vertex I(k) to vertex
28 : // J(k) with weight W(k), and also the number of vertices and number of edges.
29 :
30 : // LAGraph_BF_pure_c returns GrB_SUCCESS, or GrB_NO_VALUE if it detects of
31 : // negative- weight cycle. The vector d(k) and pi(k) (i.e., *pd, and *ppi
32 : // respectively) will be NULL when negative-weight cycle detected. Otherwise,
33 : // the vector d has d(k) as the shortest distance from s to k. pi(k) = p, where
34 : // p is the parent node of k-th node in the shortest path. In particular, pi(s)
35 : // = -1.
36 :
37 : //------------------------------------------------------------------------------
38 :
39 : #define LG_FREE_ALL \
40 : { \
41 : LAGraph_Free ((void**) &d, NULL) ; \
42 : LAGraph_Free ((void**) &pi, NULL) ; \
43 : }
44 :
45 : #include "LG_internal.h"
46 : #include <LAGraphX.h>
47 :
48 : // Given the edges and corresponding weights of a graph in tuple
49 : // form {I, J, W} and a source vertex s. If there is no negative-weight
50 : // cycle reachable from s, returns GrB_SUCCESS and the shortest distance
51 : // d and the shortest path tree pi. Otherwise return NULL pointer for d
52 : // and pi.
53 :
54 3 : GrB_Info LAGraph_BF_pure_c
55 : (
56 : int32_t **pd, // pointer to distance vector d, d(k) = shorstest distance
57 : // between s and k if k is reachable from s
58 : int64_t **ppi, // pointer to parent index vector pi, pi(k) = parent of
59 : // node k in the shortest path tree
60 : const int64_t s, // given source node index
61 : const int64_t n, // number of nodes
62 : const int64_t nz,// number of edges
63 : const int64_t *I,// row index vector
64 : const int64_t *J,// column index vector
65 : const int32_t *W // weight vector, W(i) = weight of edge (I(i),J(i))
66 : )
67 : {
68 3 : char *msg = NULL ;
69 : int64_t i, j, k;
70 3 : int32_t *d = NULL;
71 3 : int64_t *pi = NULL;
72 3 : LG_ASSERT (I != NULL && J != NULL && W != NULL && pd != NULL &&
73 : ppi != NULL, GrB_NULL_POINTER) ;
74 :
75 3 : LAGraph_Free ((void **) pd, NULL) ;
76 3 : LAGraph_Free ((void **) ppi, NULL) ;
77 :
78 3 : LG_ASSERT_MSG (s < n, GrB_INVALID_INDEX, "invalid source node") ;
79 :
80 : // allocate d and pi
81 3 : LAGRAPH_TRY (LAGraph_Malloc((void **) &d, n, sizeof(int32_t), msg));
82 3 : LAGRAPH_TRY (LAGraph_Malloc((void **) &pi, n, sizeof(int64_t), msg));
83 :
84 : // initialize d to a vector of INF while set d(s) = 0
85 : // and pi to a vector of -1
86 51 : for (i = 0; i < n; i++)
87 : {
88 48 : d[i] = INT32_MAX;
89 48 : pi[i] = -1;
90 : }
91 3 : d[s] = 0;
92 :
93 : // start the RELAX process and print results after each loop
94 3 : bool new_path = true; //variable indicating if new path is found
95 3 : int64_t count = 0; //number of loops
96 : // terminate when no new path is found or more than n-1 loops
97 14 : while(new_path && count < n-1)
98 : {
99 11 : new_path = false;
100 431 : for (k = 0; k < nz; k++)
101 : {
102 420 : i = I[k];
103 420 : j = J[k];
104 420 : if (d[i] != INT32_MAX && (d[j] == INT32_MAX || d[j] > d[i] + W[k]))
105 : {
106 83 : d[j] = d[i] + W[k];
107 83 : pi[j] = i;
108 83 : new_path = true;
109 : }
110 : }
111 11 : count++;
112 : }
113 :
114 : // check for negative-weight cycle only when there was a new path in the
115 : // last loop, otherwise, there can't be a negative-weight cycle.
116 3 : if (new_path)
117 : {
118 : // Do another loop of RELAX to check for negative loop,
119 : // return true if there is negative-weight cycle;
120 : // otherwise, print the distance vector and return false.
121 1 : for (k = 0; k < nz; k++)
122 : {
123 1 : i = I[k];
124 1 : j = J[k];
125 1 : if (d[i] != INT32_MAX && (d[j] == INT32_MAX || d[j] > d[i] + W[k]))
126 : {
127 1 : LG_FREE_ALL ;
128 1 : return (GrB_NO_VALUE) ;
129 : }
130 : }
131 : }
132 :
133 2 : *pd = d;
134 2 : *ppi = pi;
135 2 : return (GrB_SUCCESS) ;
136 : }
|
