GRASS Programmer's Manual
6.4.2(2012)
|
00001 00017 #include <stdio.h> 00018 #include <stdlib.h> 00019 #include <grass/gis.h> 00020 #include <grass/Vect.h> 00021 #include <grass/glocale.h> 00022 #include <grass/dgl/graph.h> 00023 00038 int NetA_allpairs(dglGraph_s * graph, dglInt32_t ** dist) 00039 { 00040 int nnodes, i, j, k, indices; 00041 dglEdgesetTraverser_s et; 00042 dglNodeTraverser_s nt; 00043 dglInt32_t *node; 00044 00045 nnodes = dglGet_NodeCount(graph); 00046 dglInt32_t *node_indices; 00047 00048 node_indices = (dglInt32_t *) G_calloc(nnodes, sizeof(dglInt32_t)); 00049 if (!node_indices) { 00050 G_fatal_error(_("Out of memory")); 00051 return -1; 00052 } 00053 G_message(_("Computing all pairs shortest paths...")); 00054 G_percent_reset(); 00055 for (i = 0; i <= nnodes; i++) 00056 for (j = 0; j <= nnodes; j++) 00057 dist[i][j] = -1; 00058 dglNode_T_Initialize(&nt, graph); 00059 indices = 0; 00060 for (node = dglNode_T_First(&nt); node; node = dglNode_T_Next(&nt)) { 00061 dglInt32_t node_id = dglNodeGet_Id(graph, node); 00062 00063 node_indices[indices++] = node_id; 00064 dglInt32_t *edge; 00065 00066 dglEdgeset_T_Initialize(&et, graph, 00067 dglNodeGet_OutEdgeset(graph, node)); 00068 for (edge = dglEdgeset_T_First(&et); edge; 00069 edge = dglEdgeset_T_Next(&et)) 00070 if (dglEdgeGet_Id(graph, edge) < 0) /*ignore backward edges */ 00071 dist[node_id][dglNodeGet_Id 00072 (graph, dglEdgeGet_Tail(graph, edge))] = 00073 dglEdgeGet_Cost(graph, edge); 00074 dglEdgeset_T_Release(&et); 00075 } 00076 dglNode_T_Release(&nt); 00077 for (k = 0; k < indices; k++) { 00078 dglInt32_t k_index = node_indices[k]; 00079 00080 G_percent(k + 1, indices, 1); 00081 for (i = 0; i < indices; i++) { 00082 dglInt32_t i_index = node_indices[i]; 00083 00084 if (dist[i_index][k_index] == -1) 00085 continue; /*no reason to proceed along infinite path */ 00086 for (j = 0; j < indices; j++) { 00087 dglInt32_t j_index = node_indices[j]; 00088 00089 if (dist[k_index][j_index] != -1 && 00090 (dist[i_index][k_index] + dist[k_index][j_index] < 00091 dist[i_index][j_index] || 00092 dist[i_index][j_index] == -1)) { 00093 dist[i_index][j_index] = 00094 dist[i_index][k_index] + dist[k_index][j_index]; 00095 } 00096 } 00097 } 00098 } 00099 00100 G_free(node_indices); 00101 return 0; 00102 }