GRASS Programmer's Manual
6.4.2(2012)
|
00001 00016 #include <stdio.h> 00017 #include <stdlib.h> 00018 #include <grass/gis.h> 00019 #include <grass/Vect.h> 00020 #include <grass/glocale.h> 00021 #include <grass/dgl/graph.h> 00022 #include <grass/neta.h> 00023 00039 int NetA_distance_from_points(dglGraph_s * graph, struct ilist *from, 00040 int *dst, dglInt32_t ** prev) 00041 { 00042 int i, nnodes; 00043 dglHeap_s heap; 00044 00045 nnodes = dglGet_NodeCount(graph); 00046 dglEdgesetTraverser_s et; 00047 00048 for (i = 1; i <= nnodes; i++) { 00049 dst[i] = -1; 00050 prev[i] = NULL; 00051 } 00052 00053 dglHeapInit(&heap); 00054 00055 for (i = 0; i < from->n_values; i++) { 00056 int v = from->value[i]; 00057 00058 if (dst[v] == 0) 00059 continue; /*ingore duplicates */ 00060 dst[v] = 0; 00061 dglHeapData_u heap_data; 00062 00063 heap_data.ul = v; 00064 dglHeapInsertMin(&heap, 0, ' ', heap_data); 00065 } 00066 while (1) { 00067 dglInt32_t v, dist; 00068 dglHeapNode_s heap_node; 00069 dglHeapData_u heap_data; 00070 00071 if (!dglHeapExtractMin(&heap, &heap_node)) 00072 break; 00073 v = heap_node.value.ul; 00074 dist = heap_node.key; 00075 if (dst[v] < dist) 00076 continue; 00077 00078 dglInt32_t *edge; 00079 00080 dglEdgeset_T_Initialize(&et, graph, 00081 dglNodeGet_OutEdgeset(graph, 00082 dglGetNode(graph, v))); 00083 for (edge = dglEdgeset_T_First(&et); edge; 00084 edge = dglEdgeset_T_Next(&et)) { 00085 dglInt32_t *to = dglEdgeGet_Tail(graph, edge); 00086 dglInt32_t to_id = dglNodeGet_Id(graph, to); 00087 dglInt32_t d = dglEdgeGet_Cost(graph, edge); 00088 00089 if (dst[to_id] == -1 || dst[to_id] > dist + d) { 00090 dst[to_id] = dist + d; 00091 prev[to_id] = edge; 00092 heap_data.ul = to_id; 00093 dglHeapInsertMin(&heap, dist + d, ' ', heap_data); 00094 } 00095 } 00096 00097 dglEdgeset_T_Release(&et); 00098 } 00099 00100 dglHeapFree(&heap, NULL); 00101 00102 return 0; 00103 } 00104 00121 int NetA_find_path(dglGraph_s * graph, int from, int to, int *edges, 00122 struct ilist *list) 00123 { 00124 dglInt32_t **prev, *queue; 00125 dglEdgesetTraverser_s et; 00126 char *vis; 00127 int begin, end, cur, nnodes; 00128 00129 nnodes = dglGet_NodeCount(graph); 00130 prev = (dglInt32_t **) G_calloc(nnodes + 1, sizeof(dglInt32_t *)); 00131 queue = (dglInt32_t *) G_calloc(nnodes + 1, sizeof(dglInt32_t)); 00132 vis = (char *)G_calloc(nnodes + 1, sizeof(char)); 00133 if (!prev || !queue || !vis) { 00134 G_fatal_error(_("Out of memory")); 00135 return -1; 00136 } 00137 Vect_reset_list(list); 00138 00139 begin = 0; 00140 end = 1; 00141 vis[from] = 'y'; 00142 queue[0] = from; 00143 prev[from] = NULL; 00144 while (begin != end) { 00145 dglInt32_t vertex = queue[begin++]; 00146 00147 if (vertex == to) 00148 break; 00149 dglInt32_t *edge, *node = dglGetNode(graph, vertex); 00150 00151 dglEdgeset_T_Initialize(&et, graph, 00152 dglNodeGet_OutEdgeset(graph, node)); 00153 for (edge = dglEdgeset_T_First(&et); edge; 00154 edge = dglEdgeset_T_Next(&et)) { 00155 dglInt32_t id = abs(dglEdgeGet_Id(graph, edge)); 00156 dglInt32_t to = 00157 dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, edge)); 00158 if (edges[id] && !vis[to]) { 00159 vis[to] = 'y'; 00160 prev[to] = edge; 00161 queue[end++] = to; 00162 } 00163 } 00164 dglEdgeset_T_Release(&et); 00165 } 00166 G_free(queue); 00167 if (!vis[to]) { 00168 G_free(prev); 00169 G_free(vis); 00170 return -1; 00171 } 00172 00173 cur = to; 00174 while (prev[cur] != NULL) { 00175 Vect_list_append(list, abs(dglEdgeGet_Id(graph, prev[cur]))); 00176 cur = dglNodeGet_Id(graph, dglEdgeGet_Head(graph, prev[cur])); 00177 } 00178 00179 G_free(prev); 00180 G_free(vis); 00181 return list->n_values; 00182 }