GRASS Programmer's Manual
6.4.3(2013)-r
Main Page
Related Pages
Namespaces
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Properties
Macros
Pages
path.c
Go to the documentation of this file.
1
16
#include <stdio.h>
17
#include <stdlib.h>
18
#include <grass/gis.h>
19
#include <grass/Vect.h>
20
#include <grass/glocale.h>
21
#include <grass/dgl/graph.h>
22
#include <grass/neta.h>
23
39
int
NetA_distance_from_points
(
dglGraph_s
* graph,
struct
ilist *from,
40
int
*dst,
dglInt32_t
** prev)
41
{
42
int
i, nnodes;
43
dglHeap_s
heap;
44
45
nnodes =
dglGet_NodeCount
(graph);
46
dglEdgesetTraverser_s
et;
47
48
for
(i = 1; i <= nnodes; i++) {
49
dst[i] = -1;
50
prev[i] =
NULL
;
51
}
52
53
dglHeapInit
(&heap);
54
55
for
(i = 0; i < from->n_values; i++) {
56
int
v = from->value[i];
57
58
if
(dst[v] == 0)
59
continue
;
/*ingore duplicates */
60
dst[v] = 0;
61
dglHeapData_u
heap_data;
62
63
heap_data.
ul
= v;
64
dglHeapInsertMin
(&heap, 0,
' '
, heap_data);
65
}
66
while
(1) {
67
dglInt32_t
v, dist;
68
dglHeapNode_s
heap_node;
69
dglHeapData_u
heap_data;
70
71
if
(!
dglHeapExtractMin
(&heap, &heap_node))
72
break
;
73
v = heap_node.
value
.
ul
;
74
dist = heap_node.
key
;
75
if
(dst[v] < dist)
76
continue
;
77
78
dglInt32_t
*edge;
79
80
dglEdgeset_T_Initialize
(&et, graph,
81
dglNodeGet_OutEdgeset
(graph,
82
dglGetNode
(graph, v)));
83
for
(edge =
dglEdgeset_T_First
(&et); edge;
84
edge =
dglEdgeset_T_Next
(&et)) {
85
dglInt32_t
*to =
dglEdgeGet_Tail
(graph, edge);
86
dglInt32_t
to_id =
dglNodeGet_Id
(graph, to);
87
dglInt32_t
d =
dglEdgeGet_Cost
(graph, edge);
88
89
if
(dst[to_id] == -1 || dst[to_id] > dist + d) {
90
dst[to_id] = dist + d;
91
prev[to_id] = edge;
92
heap_data.
ul
= to_id;
93
dglHeapInsertMin
(&heap, dist + d,
' '
, heap_data);
94
}
95
}
96
97
dglEdgeset_T_Release
(&et);
98
}
99
100
dglHeapFree
(&heap,
NULL
);
101
102
return
0;
103
}
104
121
int
NetA_find_path
(
dglGraph_s
* graph,
int
from,
int
to,
int
*edges,
122
struct
ilist *list)
123
{
124
dglInt32_t
**prev, *queue;
125
dglEdgesetTraverser_s
et;
126
char
*vis;
127
int
begin, end, cur, nnodes;
128
129
nnodes =
dglGet_NodeCount
(graph);
130
prev = (
dglInt32_t
**) G_calloc(nnodes + 1,
sizeof
(
dglInt32_t
*));
131
queue = (
dglInt32_t
*) G_calloc(nnodes + 1,
sizeof
(
dglInt32_t
));
132
vis = (
char
*)G_calloc(nnodes + 1,
sizeof
(
char
));
133
if
(!prev || !queue || !vis) {
134
G_fatal_error
(_(
"Out of memory"
));
135
return
-1;
136
}
137
Vect_reset_list
(list);
138
139
begin = 0;
140
end = 1;
141
vis[from] =
'y'
;
142
queue[0] = from;
143
prev[from] =
NULL
;
144
while
(begin != end) {
145
dglInt32_t
vertex = queue[begin++];
146
147
if
(vertex == to)
148
break
;
149
dglInt32_t
*edge, *node =
dglGetNode
(graph, vertex);
150
151
dglEdgeset_T_Initialize
(&et, graph,
152
dglNodeGet_OutEdgeset
(graph, node));
153
for
(edge =
dglEdgeset_T_First
(&et); edge;
154
edge =
dglEdgeset_T_Next
(&et)) {
155
dglInt32_t
id
= abs(
dglEdgeGet_Id
(graph, edge));
156
dglInt32_t
to =
157
dglNodeGet_Id
(graph,
dglEdgeGet_Tail
(graph, edge));
158
if
(edges[
id
] && !vis[to]) {
159
vis[to] =
'y'
;
160
prev[to] = edge;
161
queue[end++] = to;
162
}
163
}
164
dglEdgeset_T_Release
(&et);
165
}
166
G_free
(queue);
167
if
(!vis[to]) {
168
G_free
(prev);
169
G_free
(vis);
170
return
-1;
171
}
172
173
cur = to;
174
while
(prev[cur] !=
NULL
) {
175
Vect_list_append
(list, abs(
dglEdgeGet_Id
(graph, prev[cur])));
176
cur =
dglNodeGet_Id
(graph,
dglEdgeGet_Head
(graph, prev[cur]));
177
}
178
179
G_free
(prev);
180
G_free
(vis);
181
return
list->n_values;
182
}
lib
vector
neta
path.c
Generated on Thu Sep 26 2013 09:48:05 for GRASS Programmer's Manual by
1.8.4