← Back to branch summary

~ubuntu-branches/ubuntu/vivid/grass/vivid-proposed

« back to all changes in this revision

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

  • Committer: Package Import Robot
  • Author(s): Bas Couwenberg
  • Date: 2015-02-20 23:12:08 UTC
  • mfrom: (8.2.6 experimental)
  • Revision ID: package-import@ubuntu.com-20150220231208-1u6qvqm84v430b10
Tags: 7.0.0-1~exp1
* New upstream release.
* Update python-ctypes-ternary.patch to use if/else instead of and/or.
* Drop check4dev patch, rely on upstream check.
* Add build dependency on libpq-dev to grass-dev for libpq-fe.h.
* Drop patches applied upstream, refresh remaining patches.
* Update symlinks for images switched from jpg to png.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/vector/neta/path.c
16
16
#include <stdio.h>
17
17
#include <stdlib.h>
18
18
#include <grass/gis.h>
19
 
#include <grass/Vect.h>
 
19
#include <grass/vector.h>
20
20
#include <grass/glocale.h>
21
21
#include <grass/dgl/graph.h>
22
22
#include <grass/neta.h>
23
23
 
24
24
/*!
25
 
   \brief Computes shortests paths to every node from  nodes in "from".
 
25
   \brief Computes shortests paths to every node from nodes in "from".
26
26
 
27
27
   Array "dst" contains the length of the path or -1 if the node is not
28
28
   reachable. Prev contains edges from predecessor along the shortest
36
36
   \return 0 on success
37
37
   \return -1 on failure
38
38
 */
39
 
int NetA_distance_from_points(dglGraph_s * graph, struct ilist *from,
40
 
                              int *dst, dglInt32_t ** prev)
 
39
int NetA_distance_from_points(dglGraph_s *graph, struct ilist *from,
 
40
                              int *dst, dglInt32_t **prev)
41
41
{
42
42
    int i, nnodes;
43
43
    dglHeap_s heap;
45
45
    nnodes = dglGet_NodeCount(graph);
46
46
    dglEdgesetTraverser_s et;
47
47
 
 
48
    /* initialize costs and edge list */
48
49
    for (i = 1; i <= nnodes; i++) {
49
50
        dst[i] = -1;
50
51
        prev[i] = NULL;
57
58
 
58
59
        if (dst[v] == 0)
59
60
            continue;           /*ingore duplicates */
60
 
        dst[v] = 0;
 
61
        dst[v] = 0;             /* make sure all from nodes are processed first */
61
62
        dglHeapData_u heap_data;
62
63
 
63
64
        heap_data.ul = v;
80
81
        dglEdgeset_T_Initialize(&et, graph,
81
82
                                dglNodeGet_OutEdgeset(graph,
82
83
                                                      dglGetNode(graph, v)));
 
84
 
83
85
        for (edge = dglEdgeset_T_First(&et); edge;
84
86
             edge = dglEdgeset_T_Next(&et)) {
85
87
            dglInt32_t *to = dglEdgeGet_Tail(graph, edge);
86
88
            dglInt32_t to_id = dglNodeGet_Id(graph, to);
87
89
            dglInt32_t d = dglEdgeGet_Cost(graph, edge);
88
90
 
89
 
            if (dst[to_id] == -1 || dst[to_id] > dist + d) {
 
91
            if (dst[to_id] < 0 || dst[to_id] > dist + d) {
90
92
                dst[to_id] = dist + d;
91
93
                prev[to_id] = edge;
92
94
                heap_data.ul = to_id;
105
107
/*!
106
108
   \brief Find a path (minimum number of edges) from 'from' to 'to' using only edges in 'edges'.
107
109
 
108
 
   Precisely, edge with id I is used iff edges[abs(i)] == 1. List
 
110
   Precisely, edge with id I is used if edges[abs(i)] == 1. List
109
111
   stores the indices of lines on the path. Method return number of
110
112
   edges or -1 if no path exist.
111
113