GRASS GIS 7 Programmer's Manual  7.7.svn(2018)-r73373
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
vector/neta/path.c File Reference

Network Analysis library - shortest path. More...

#include <stdio.h>
#include <stdlib.h>
#include <grass/gis.h>
#include <grass/vector.h>
#include <grass/glocale.h>
#include <grass/dgl/graph.h>
#include <grass/neta.h>
Include dependency graph for vector/neta/path.c:

Go to the source code of this file.

Functions

int NetA_distance_from_points (dglGraph_s *graph, struct ilist *from, int *dst, dglInt32_t **prev)
 Computes shortest paths to every node from nodes in "from". More...
 
int NetA_distance_to_points (dglGraph_s *graph, struct ilist *to, int *dst, dglInt32_t **nxt)
 Computes shortest paths from every node to nodes in "to". More...
 
int NetA_find_path (dglGraph_s *graph, int from, int to, int *edges, struct ilist *list)
 Find a path (minimum number of edges) from 'from' to 'to' using only edges flagged as valid in 'edges'. Edge costs are not considered. Closed nodes are not traversed. More...
 

Detailed Description

Network Analysis library - shortest path.

Shortest paths from a set of nodes.

(C) 2009-2010 by Daniel Bundala, and the GRASS Development Team

This program is free software under the GNU General Public License (>=v2). Read the file COPYING that comes with GRASS for details.

Author
Daniel Bundala (Google Summer of Code 2009)
Markus Metz

Definition in file vector/neta/path.c.

Function Documentation

int NetA_distance_from_points ( dglGraph_s graph,
struct ilist from,
int dst,
dglInt32_t **  prev 
)

Computes shortest paths to every node from nodes in "from".

Array "dst" contains the cost of the path or -1 if the node is not reachable. Prev contains edges from predecessor along the shortest path.

Parameters
graphinput graph
fromlist of 'from' positions
[out]dstarray of costs to reach nodes
[out]prevarray of edges from predecessor along the shortest path
Returns
0 on success
-1 on failure

Definition at line 40 of file vector/neta/path.c.

References dglEdgeGet_Cost(), dglEdgeGet_Tail(), dglEdgeset_T_First(), dglEdgeset_T_Initialize(), dglEdgeset_T_Next(), dglEdgeset_T_Release(), dglGet_NodeAttrSize(), dglGet_NodeCount(), dglGetNode(), dglHeapExtractMin(), dglHeapFree(), dglHeapInit(), dglHeapInsertMin(), dglNodeGet_Attr(), dglNodeGet_Id(), dglNodeGet_OutEdgeset(), _dglHeapNode::key, ilist::n_values, NULL, _dglHeapData::ul, _dglHeapNode::value, and ilist::value.

int NetA_distance_to_points ( dglGraph_s graph,
struct ilist to,
int dst,
dglInt32_t **  nxt 
)

Computes shortest paths from every node to nodes in "to".

Array "dst" contains the cost of the path or -1 if the node is not reachable. Nxt contains edges from successor along the shortest path. This method does reverse search starting with "to" nodes and going backward.

Parameters
graphinput graph
tolist of 'to' positions
[out]dstarray of costs to reach nodes
[out]nxtarray of edges from successor along the shortest path
Returns
0 on success
-1 on failure

Definition at line 140 of file vector/neta/path.c.

References dglEdgeGet_Cost(), dglEdgeGet_Head(), dglEdgeset_T_First(), dglEdgeset_T_Initialize(), dglEdgeset_T_Next(), dglEdgeset_T_Release(), dglGet_NodeAttrSize(), dglGet_NodeCount(), dglGetNode(), dglHeapExtractMin(), dglHeapFree(), dglHeapInit(), dglHeapInsertMin(), dglNodeGet_Attr(), dglNodeGet_Id(), dglNodeGet_InEdgeset(), G_warning(), _dglHeapNode::key, ilist::n_values, NULL, _dglHeapData::ul, _dglHeapNode::value, ilist::value, and _dglGraph::Version.

int NetA_find_path ( dglGraph_s graph,
int  from,
int  to,
int edges,
struct ilist list 
)

Find a path (minimum number of edges) from 'from' to 'to' using only edges flagged as valid in 'edges'. Edge costs are not considered. Closed nodes are not traversed.

Precisely, edge with id I is used if edges[abs(i)] == 1. List stores the indices of lines on the path. The method returns the number of edges or -1 if no path exists.

Parameters
graphinput graph
from'from' position
to'to' position
edgesarray of edges indicating whether an edge should be used
[out]listlist of edges
Returns
number of edges
-1 on failure

Definition at line 247 of file vector/neta/path.c.

References _, dglEdgeGet_Head(), dglEdgeGet_Id(), dglEdgeGet_Tail(), dglEdgeset_T_First(), dglEdgeset_T_Initialize(), dglEdgeset_T_Next(), dglEdgeset_T_Release(), dglGet_NodeAttrSize(), dglGet_NodeCount(), dglGetNode(), dglNodeGet_Attr(), dglNodeGet_Id(), dglNodeGet_OutEdgeset(), G_fatal_error(), G_free(), ilist::n_values, NULL, Vect_list_append(), and Vect_reset_list().