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