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

NetA_distance_from_points()

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

	graph	input graph
	from	list of 'from' positions
[out]	dst	array of costs to reach nodes
[out]	prev	array 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 dglGet_NodeAttrSize(), dglGet_NodeCount(), dglHeapInit(), dglHeapInsertMin(), ilist::n_values, NULL, _dglHeapData::ul, and ilist::value.

NetA_distance_to_points()

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

	graph	input graph
	to	list of 'to' positions
[out]	dst	array of costs to reach nodes
[out]	nxt	array 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 dglGet_NodeAttrSize(), dglGet_NodeCount(), dglHeapInit(), dglHeapInsertMin(), G_warning(), ilist::n_values, NULL, _dglHeapData::ul, ilist::value, and _dglGraph::Version.

NetA_find_path()

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

	graph	input graph
	from	'from' position
	to	'to' position
	edges	array of edges indicating whether an edge should be used
[out]	list	list of edges

Returns

number of edges

-1 on failure

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