GRASS Programmer's Manual  6.4.2(2012)
path.c
Go to the documentation of this file.
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 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines