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