Vlib/graph.c File Reference

#include <stdlib.h>
#include <string.h>
#include <grass/gis.h>
#include <grass/dbmi.h>
#include <grass/Vect.h>
#include <grass/glocale.h>

Include dependency graph for Vlib/graph.c:

Go to the source code of this file.

Functions
void	Vect_graph_init (GRAPH *graph, int nodes_costs)
	Initialize graph structure. More...
void	Vect_graph_build (GRAPH *graph)
	Build network graph. More...
void	Vect_graph_add_edge (GRAPH *graph, int from, int to, double costs, int id)
	Add edge to graph. More...
void	Vect_graph_set_node_costs (GRAPH *graph, int node, double costs)
	Set node costs. More...
int	Vect_graph_shortest_path (GRAPH *graph, int from, int to, struct ilist *List, double *cost)
	Find shortest path. More...

Function Documentation

void Vect_graph_add_edge	(	GRAPH *	graph,
		int	from,
		int	to,
		double	costs,
		int	id
	)

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.

Parameters

graph	poiter to graph structure
from	from node
to	to node
costs	costs value
id	edge id

Returns

void

Definition at line 129 of file Vlib/graph.c.

References dglAddEdge(), G_debug(), and G_fatal_error().

void Vect_graph_build

(

GRAPH *

graph

)

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.

Parameters

graph

poiter to graph structure

Returns

void

Definition at line 102 of file Vlib/graph.c.

References dglFlatten(), G_debug(), and G_fatal_error().

void Vect_graph_init	(	GRAPH *	graph,
		int	nodes_costs
	)

Initialize graph structure.

Parameters

graph	poiter to graph structure
nodes_costs	use node costs

Returns

void

Definition at line 76 of file Vlib/graph.c.

References dglInitialize(), and G_debug().

void Vect_graph_set_node_costs	(	GRAPH *	graph,
		int	node,
		double	costs
	)

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.

Parameters

graph	poiter to graph structure
node	node id
costs	costs value

Returns

void

Definition at line 159 of file Vlib/graph.c.

References dglGetNode(), dglNodeSet_Attr(), and G_debug().

int Vect_graph_shortest_path	(	GRAPH *	graph,
		int	from,
		int	to,
		struct ilist *	List,
		double *	cost
	)

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.

Parameters

graph	pointer to graph structure
from	from node
to	to node
List	list of line ids
cost	costs value

Returns

number of segments

0 is correct for from = to, or List == NULL ), ? sum of costs is better return value,

-1 destination unreachable

Definition at line 189 of file Vlib/graph.c.

References _dglSPReport::cArc, dglEdgeGet_Cost(), dglEdgeGet_Id(), dglFreeSPReport(), dglShortestDistance(), dglShortestPath(), dglStrerror(), G_debug(), G_warning(), _dglSPArc::nDistance, _dglSPReport::nDistance, _dglSPArc::nFrom, _dglSPArc::nTo, NULL, _dglSPReport::pArc, _dglSPArc::pnEdge, Vect_list_append(), and Vect_reset_list().