path.c File Reference

Network Analysis library - shortest path. More...

#include <stdio.h>
#include <stdlib.h>
#include <grass/gis.h>
#include <grass/Vect.h>
#include <grass/glocale.h>
#include <grass/dgl/graph.h>
#include <grass/neta.h>

Include dependency graph for 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 shortests paths to every node from nodes in "from". 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 in 'edges'. 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)

Definition in file path.c.

Function Documentation

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

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

Array "dst" contains the length 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
	dst	list of 'to' positions
[out]	prev	list of edges from predecessor along the shortest path

Returns

0 on success

-1 on failure

Definition at line 39 of file path.c.

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

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 in 'edges'.

Precisely, edge with id I is used iff edges[abs(i)] == 1. List stores the indices of lines on the path. Method return number of edges or -1 if no path exist.

Parameters

	graph	input graph
	from	'from' position
	to	'to' position
	edges	list of available edges
[out]	list	list of edges

Returns

number of edges

-1 on failure

Definition at line 121 of file path.c.

References dglEdgeGet_Head(), dglEdgeGet_Id(), dglEdgeGet_Tail(), dglEdgeset_T_First(), dglEdgeset_T_Initialize(), dglEdgeset_T_Next(), dglEdgeset_T_Release(), dglGet_NodeCount(), dglGetNode(), dglNodeGet_Id(), dglNodeGet_OutEdgeset(), G_fatal_error(), G_free(), NULL, Vect_list_append(), and Vect_reset_list().