bridge.c 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138
  1. /*!
  2. \file vector/neta/bridges.c
  3. \brief Network Analysis library - bridges
  4. Computes number of bridges in the graph.
  5. (C) 2009-2010 by Daniel Bundala, and the GRASS Development Team
  6. This program is free software under the GNU General Public License
  7. (>=v2). Read the file COPYING that comes with GRASS for details.
  8. \author Daniel Bundala (Google Summer of Code 2009)
  9. */
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <grass/gis.h>
  13. #include <grass/vector.h>
  14. #include <grass/glocale.h>
  15. #include <grass/dgl/graph.h>
  16. /*!
  17. \brief Get number of bridges in the graph.
  18. Bridge is an array containing the indices of the bridges.
  19. \param graph input graph
  20. \param[out] bridges_list list of bridges
  21. \return number of bridges
  22. \return -1 on error
  23. */
  24. int NetA_compute_bridges(dglGraph_s * graph, struct ilist *bridge_list)
  25. {
  26. int nnodes;
  27. int bridges = 0;
  28. dglEdgesetTraverser_s *current; /*edge to be processed when the node is visited */
  29. int *tin, *min_tin; /*time in, and smallest tin over all successors. 0 if not yet visited */
  30. dglInt32_t *parent; /*edge from parent to the node */
  31. dglInt32_t **stack; /*stack of nodes */
  32. dglInt32_t **current_edge; /*current edge for each node */
  33. dglNodeTraverser_s nt;
  34. dglInt32_t *current_node;
  35. int stack_size;
  36. int i, time;
  37. nnodes = dglGet_NodeCount(graph);
  38. current =
  39. (dglEdgesetTraverser_s *) G_calloc(nnodes + 1,
  40. sizeof(dglEdgesetTraverser_s));
  41. tin = (int *)G_calloc(nnodes + 1, sizeof(int));
  42. min_tin = (int *)G_calloc(nnodes + 1, sizeof(int));
  43. parent = (dglInt32_t *) G_calloc(nnodes + 1, sizeof(dglInt32_t));
  44. stack = (dglInt32_t **) G_calloc(nnodes + 1, sizeof(dglInt32_t *));
  45. current_edge = (dglInt32_t **) G_calloc(nnodes + 1, sizeof(dglInt32_t *));
  46. if (!tin || !min_tin || !parent || !stack || !current) {
  47. G_fatal_error(_("Out of memory"));
  48. return -1;
  49. }
  50. for (i = 1; i <= nnodes; i++) {
  51. dglEdgeset_T_Initialize(&current[i], graph,
  52. dglNodeGet_OutEdgeset(graph,
  53. dglGetNode(graph, i)));
  54. current_edge[i] = dglEdgeset_T_First(&current[i]);
  55. tin[i] = 0;
  56. }
  57. dglNode_T_Initialize(&nt, graph);
  58. time = 0;
  59. for (current_node = dglNode_T_First(&nt); current_node;
  60. current_node = dglNode_T_Next(&nt)) {
  61. dglInt32_t current_id = dglNodeGet_Id(graph, current_node);
  62. if (tin[current_id] == 0) {
  63. stack[0] = current_node;
  64. stack_size = 1;
  65. parent[current_id] = 0;
  66. while (stack_size) {
  67. dglInt32_t *node = stack[stack_size - 1];
  68. dglInt32_t node_id = dglNodeGet_Id(graph, node);
  69. if (tin[node_id] == 0) /*vertex visited for the first time */
  70. min_tin[node_id] = tin[node_id] = ++time;
  71. else { /*return from the recursion */
  72. dglInt32_t to = dglNodeGet_Id(graph,
  73. dglEdgeGet_Tail(graph,
  74. current_edge
  75. [node_id]));
  76. if (min_tin[to] > tin[node_id]) { /*no path from the subtree above the current node */
  77. Vect_list_append(bridge_list, dglEdgeGet_Id(graph, current_edge[node_id])); /*so it must be a bridge */
  78. bridges++;
  79. }
  80. if (min_tin[to] < min_tin[node_id])
  81. min_tin[node_id] = min_tin[to];
  82. current_edge[node_id] = dglEdgeset_T_Next(&current[node_id]); /*proceed to the next edge */
  83. }
  84. for (; current_edge[node_id]; current_edge[node_id] = dglEdgeset_T_Next(&current[node_id])) { //try next edges
  85. dglInt32_t *to =
  86. dglEdgeGet_Tail(graph, current_edge[node_id]);
  87. dglInt32_t edge_id =
  88. dglEdgeGet_Id(graph, current_edge[node_id]);
  89. if (abs(edge_id) == parent[node_id])
  90. continue; /*skip edge we used to travel to this node */
  91. int to_id = dglNodeGet_Id(graph, to);
  92. if (tin[to_id]) { /*back edge, cannot be a bridge/articualtion point */
  93. if (tin[to_id] < min_tin[node_id])
  94. min_tin[node_id] = tin[to_id];
  95. }
  96. else { /*forward edge */
  97. parent[to_id] = abs(edge_id);
  98. stack[stack_size++] = to;
  99. break;
  100. }
  101. }
  102. if (!current_edge[node_id])
  103. stack_size--; /*current node completely processed */
  104. }
  105. }
  106. }
  107. dglNode_T_Release(&nt);
  108. for (i = 1; i <= nnodes; i++)
  109. dglEdgeset_T_Release(&current[i]);
  110. G_free(current);
  111. G_free(tin);
  112. G_free(min_tin);
  113. G_free(parent);
  114. G_free(stack);
  115. G_free(current_edge);
  116. return bridges;
  117. }