← Back to branch summary

~ubuntu-branches/ubuntu/wily/grass/wily

« back to all changes in this revision

Viewing changes to lib/vector/neta/bridge.c

Tags: 7.0.0~rc1+ds1-1~exp1
http://bugs.debian.org/776349
* New upstream release candidate.
* Repack upstream tarball, remove precompiled Python objects.
* Add upstream metadata.
* Update gbp.conf and Vcs-Git URL to use the experimental branch.
* Update watch file for GRASS 7.0.
* Drop build dependencies for Tcl/Tk, add build dependencies:
  python-numpy, libnetcdf-dev, netcdf-bin, libblas-dev, liblapack-dev
* Update Vcs-Browser URL to use cgit instead of gitweb.
* Update paths to use grass70.
* Add configure options: --with-netcdf, --with-blas, --with-lapack,
  remove --with-tcltk-includes.
* Update patches for GRASS 7.
* Update copyright file, changes:
  - Update copyright years
  - Group files by license
  - Remove unused license sections
* Add patches for various typos.
* Fix desktop file with patch instead of d/rules.
* Use minimal dh rules.
* Bump Standards-Version to 3.9.6, no changes.
* Use dpkg-maintscript-helper to replace directories with symlinks.
  (closes: #776349)
* Update my email to use @debian.org address.

Show diffs side-by-side

added added

removed removed

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