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
Vlib/graph.c
Go to the documentation of this file.
1
22
#include <stdlib.h>
23
#include <string.h>
24
#include <grass/gis.h>
25
#include <grass/dbmi.h>
26
#include <grass/Vect.h>
27
#include <grass/glocale.h>
28
29
static
int
From_node;
/* from node set in SP and used by clipper for first arc */
30
31
static
int
clipper(
dglGraph_s
* pgraph,
32
dglSPClipInput_s
* pargIn,
33
dglSPClipOutput_s
* pargOut,
void
*pvarg)
34
{
/* caller's pointer */
35
dglInt32_t
cost;
36
dglInt32_t
from;
37
38
G_debug
(3,
"Net: clipper()"
);
39
40
from =
dglNodeGet_Id
(pgraph, pargIn->
pnNodeFrom
);
41
42
G_debug
(3,
" Edge = %d NodeFrom = %d NodeTo = %d edge cost = %d"
,
43
(
int
)
dglEdgeGet_Id
(pgraph, pargIn->
pnEdge
),
44
(
int
)from, (
int
)
dglNodeGet_Id
(pgraph, pargIn->
pnNodeTo
),
45
(
int
)pargOut->
nEdgeCost
);
46
47
if
(from != From_node) {
/* do not clip first */
48
if
(
dglGet_NodeAttrSize
(pgraph) > 0) {
49
memcpy(&cost,
dglNodeGet_Attr
(pgraph, pargIn->
pnNodeFrom
),
50
sizeof
(cost));
51
if
(cost == -1) {
/* closed, cannot go from this node except it is 'from' node */
52
G_debug
(3,
" closed node"
);
53
return
1;
54
}
55
else
{
56
G_debug
(3,
" EdgeCost += %d (node)"
, (
int
)cost);
57
pargOut->
nEdgeCost
+= cost;
58
}
59
}
60
}
61
else
{
62
G_debug
(3,
" don't clip first node"
);
63
}
64
65
return
0;
66
}
67
76
void
Vect_graph_init
(GRAPH * graph,
int
nodes_costs)
77
{
78
dglInt32_t
opaqueset[16] =
79
{ 360000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
80
81
G_debug
(3,
"Vect_graph_init()"
);
82
83
if
(nodes_costs)
84
dglInitialize
(graph, (
dglByte_t
) 1,
sizeof
(
dglInt32_t
),
85
(
dglInt32_t
) 0, opaqueset);
86
else
87
dglInitialize
(graph, (
dglByte_t
) 1, (
dglInt32_t
) 0, (
dglInt32_t
) 0,
88
opaqueset);
89
}
90
102
void
Vect_graph_build
(GRAPH * graph)
103
{
104
int
ret;
105
106
G_debug
(3,
"Vect_graph_build()"
);
107
108
ret =
dglFlatten
(graph);
109
if
(ret < 0)
110
G_fatal_error
(_(
"GngFlatten error"
));
111
}
112
128
void
129
Vect_graph_add_edge
(GRAPH * graph,
int
from,
int
to,
double
costs,
int
id
)
130
{
131
int
ret;
132
dglInt32_t
dglcosts;
133
134
G_debug
(3,
"Vect_add_edge() from = %d to = %d, costs = %f, id = %d"
, from,
135
to, costs,
id
);
136
137
dglcosts = (
dglInt32_t
) costs *1000;
138
139
ret =
140
dglAddEdge
(graph, (
dglInt32_t
) from, (
dglInt32_t
) to, dglcosts,
141
(
dglInt32_t
)
id
);
142
if
(ret < 0)
143
G_fatal_error
(_(
"Unable to add network arc"
));
144
}
145
159
void
Vect_graph_set_node_costs
(GRAPH * graph,
int
node,
double
costs)
160
{
161
dglInt32_t
dglcosts;
162
163
/* TODO: Not tested! */
164
G_debug
(3,
"Vect_graph_set_node_costs()"
);
165
166
dglcosts = (
dglInt32_t
) costs *1000;
167
168
dglNodeSet_Attr
(graph,
dglGetNode
(graph, (
dglInt32_t
) node), &dglcosts);
169
}
170
188
int
189
Vect_graph_shortest_path
(GRAPH * graph,
int
from,
int
to,
struct
ilist *List,
190
double
*cost)
191
{
192
int
i, line, *pclip, cArc, nRet;
193
dglSPReport_s
*pSPReport;
194
dglInt32_t
nDistance;
195
196
G_debug
(3,
"Vect_graph_shortest_path(): from = %d, to = %d"
, from, to);
197
198
/* Note : if from == to dgl goes to nearest node and returns back (dgl feature) =>
199
* check here for from == to */
200
201
if
(List !=
NULL
)
202
Vect_reset_list
(List);
203
204
/* Check if from and to are identical, otherwise dglib returns path to neares node and back! */
205
if
(from == to) {
206
if
(cost !=
NULL
)
207
*cost = 0;
208
return
0;
209
}
210
211
From_node = from;
212
213
pclip =
NULL
;
214
if
(List !=
NULL
) {
215
nRet =
216
dglShortestPath
(graph, &pSPReport, (
dglInt32_t
) from,
217
(
dglInt32_t
) to, clipper, pclip,
NULL
);
218
}
219
else
{
220
nRet =
221
dglShortestDistance
(graph, &nDistance, (
dglInt32_t
) from,
222
(
dglInt32_t
) to, clipper, pclip,
NULL
);
223
}
224
225
if
(nRet == 0) {
226
if
(cost !=
NULL
)
227
*cost = PORT_DOUBLE_MAX;
228
return
-1;
229
}
230
else
if
(nRet < 0) {
231
G_warning
(_(
"dglShortestPath error: %s"
),
dglStrerror
(graph));
232
return
-1;
233
}
234
235
if
(List !=
NULL
) {
236
for
(i = 0; i < pSPReport->
cArc
; i++) {
237
line =
dglEdgeGet_Id
(graph, pSPReport->
pArc
[i].
pnEdge
);
238
G_debug
(2,
"From %ld to %ld - cost %ld user %d distance %ld"
,
239
pSPReport->
pArc
[i].
nFrom
, pSPReport->
pArc
[i].
nTo
,
240
/* this is the cost from clip() */
241
dglEdgeGet_Cost
(graph, pSPReport->
pArc
[i].
pnEdge
) / 1000,
242
line, pSPReport->
pArc
[i].
nDistance
);
243
Vect_list_append
(List, line);
244
}
245
}
246
247
if
(cost !=
NULL
) {
248
if
(List !=
NULL
)
249
*cost = (double)pSPReport->
nDistance
/ 1000;
250
else
251
*cost = (
double
)nDistance / 1000;
252
}
253
254
if
(List !=
NULL
) {
255
cArc = pSPReport->
cArc
;
256
dglFreeSPReport
(graph, pSPReport);
257
}
258
else
259
cArc = 0;
260
261
return
(cArc);
262
}
lib
vector
Vlib
graph.c
Generated on Sat Oct 5 2013 12:11:08 for GRASS Programmer's Manual by
1.8.4