1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
|
/****************************************************************************
*
* MODULE: Vector library
*
* AUTHOR(S): Radim Blazek
*
* PURPOSE: Higher level functions for reading/writing/manipulating vectors.
*
* This program is free software under the GNU General Public
* License (>=v2). Read the file COPYING that comes with GRASS
* for details.
*
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include "gis.h"
#include "dbmi.h"
#include "Vect.h"
/* TODO: Vect_graph_free ( GRAPH *graph ) */
static int From_node; /* from node set in SP and used by clipper for first arc */
static int clipper ( dglGraph_s *pgraph ,
dglSPClipInput_s * pargIn ,
dglSPClipOutput_s * pargOut ,
void * pvarg ) /* caller's pointer */
{
dglInt32_t cost;
dglInt32_t from;
G_debug ( 3, "Net: clipper()" );
from = dglNodeGet_Id(pgraph, pargIn->pnNodeFrom);
G_debug ( 3, " Edge = %d NodeFrom = %d NodeTo = %d edge cost = %d",
dglEdgeGet_Id (pgraph, pargIn->pnEdge),
from, dglNodeGet_Id(pgraph, pargIn->pnNodeTo),
pargOut->nEdgeCost);
if ( from != From_node ) { /* do not clip first */
if ( dglGet_NodeAttrSize(pgraph) > 0 ) {
memcpy( &cost, dglNodeGet_Attr(pgraph, pargIn->pnNodeFrom), sizeof(cost) );
if ( cost == -1 ) { /* closed, cannot go from this node except it is 'from' node */
G_debug ( 3, " closed node" );
return 1;
} else {
G_debug ( 3, " EdgeCost += %d (node)", cost );
pargOut->nEdgeCost += cost;
}
}
} else {
G_debug ( 3, " don't clip first node" );
}
return 0;
}
/*!
\fn Vect_graph_init ( GRAPH *graph, int nodes_costs )
\brief Build network graph. Internal format for edge costs is integer, costs are multiplied
before conversion to int by 1000.
Costs -1 for infinity i.e. arc or node is closed and cannot be traversed.
\param GRAPH *graph
\param nodes_costs use node costs
*/
void
Vect_graph_init ( GRAPH *graph, int nodes_costs )
{
dglInt32_t opaqueset[ 16 ] = { 360000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
G_debug (3, "Vect_graph_init()" );
if ( nodes_costs ) dglInitialize ( graph, 1, sizeof(dglInt32_t), 0, opaqueset );
else dglInitialize ( graph, 1, 0, 0, opaqueset );
}
/*!
\fn Vect_graph_init ( GRAPH *graph, int nodes_costs )
\brief Build network graph. Internal format for edge costs is integer, costs are multiplied
before conversion to int by 1000.
Costs -1 for infinity i.e. arc or node is closed and cannot be traversed.
\param GRAPH *graph
\param nodes_costs use node costs
*/
void
Vect_graph_build ( GRAPH *graph )
{
int ret;
G_debug (3, "Vect_graph_build()" );
ret = dglFlatten ( graph );
if ( ret < 0 ) G_fatal_error ("GngFlatten error");
}
/*!
\fn Vect_graph_add_edge ( GRAPH *graph, int from, int to, double costs, int id )
\brief Add edge to graph.
Internal format for edge costs is integer, costs are multiplied before conversion to int by 1000.
Costs -1 for infinity i.e. arc or node is closed and cannot be traversed.
\param GRAPH *graph
\param from from node
\param to to node
\param costs
\param id edge id
*/
void
Vect_graph_add_edge ( GRAPH *graph, int from, int to, double costs, int id )
{
int ret;
dglInt32_t dglcosts;
G_debug (3, "Vect_add_edge() from = %d to = %d, costs = %f, id = %d", from, to, costs, id );
dglcosts = (dglInt32_t) costs * 1000;
ret = dglAddEdge ( graph, from, to, dglcosts, id );
if ( ret < 0 ) G_fatal_error ("Cannot add network arc");
}
/*!
\fn Vect_graph_set_node_costs ( GRAPH *graph, int node, double costs )
\brief Set node costs
Internal format for edge costs is integer, costs are multiplied before conversion to int by 1000.
Costs -1 for infinity i.e. arc or node is closed and cannot be traversed.
\param GRAPH *graph
\param node
\param costs
*/
void
Vect_graph_set_node_costs ( GRAPH *graph, int node, double costs )
{
dglInt32_t dglcosts;
/* TODO: Not tested! */
G_debug (3, "Vect_graph_set_node_costs()" );
dglcosts = (dglInt32_t) costs * 1000;
dglNodeSet_Attr(graph, dglGetNode(graph,node), &dglcosts);
}
/*!
\fn int Vect_graph_shortest_path ( GRAPH *graph, int from, int to, struct ilist *List, double *cost )
\brief Find shortest path. Costs for 'from' and 'to' nodes are not considered (SP found even if
'from' or 'to' are 'closed' (costs = -1) and costs of these nodes are not added to SP costs result.
\return number of segments : ( 0 is correct for from = to, or List == NULL ),
? sum of costs is better return value,
-1 : destination unreachable
\param graph
\param from
\param to
\param List
\param cost
*/
int
Vect_graph_shortest_path ( GRAPH *graph, int from, int to, struct ilist *List, double *cost )
{
int i, line, *pclip, cArc, nRet;
dglSPReport_s * pSPReport;
dglInt32_t nDistance;
G_debug (3, "Vect_graph_shortest_path(): from = %d, to = %d", from, to );
/* Note : if from == to dgl goes to nearest node and returns back (dgl feature) =>
* check here for from == to */
if ( List != NULL ) Vect_reset_list ( List);
/* Check if from and to are identical, otherwise dglib returns path to neares node and back! */
if ( from == to ) {
if ( cost != NULL ) *cost = 0;
return 0;
}
From_node = from;
pclip = NULL;
if ( List != NULL ) {
nRet = dglShortestPath ( graph, &pSPReport, from, to, clipper, pclip, NULL);
} else {
nRet = dglShortestDistance ( graph, &nDistance, from, to, clipper, pclip, NULL);
}
if ( nRet == 0 ) {
if ( cost != NULL )
*cost = PORT_DOUBLE_MAX;
return -1;
}
else if ( nRet < 0 ) {
fprintf( stderr , "dglShortestPath error: %s\n", dglStrerror( graph ) );
return -1;
}
if ( List != NULL ) {
for( i = 0 ; i < pSPReport->cArc ; i ++ ) {
line = dglEdgeGet_Id(graph, pSPReport->pArc[i].pnEdge);
G_debug( 2, "From %ld to %ld - cost %ld user %d distance %ld" ,
pSPReport->pArc[i].nFrom,
pSPReport->pArc[i].nTo,
/* this is the cost from clip() */
dglEdgeGet_Cost(graph, pSPReport->pArc[i].pnEdge) / 1000,
line,
pSPReport->pArc[i].nDistance );
Vect_list_append ( List, line );
}
}
if ( cost != NULL ) {
if ( List != NULL )
*cost = (double) pSPReport->nDistance / 1000;
else
*cost = (double) nDistance / 1000;
}
if ( List != NULL ) {
cArc = pSPReport->cArc;
dglFreeSPReport( graph, pSPReport );
} else
cArc = 0;
return (cArc);
}
|
