This graph shows which files directly or indirectly include this file:

Data Structures
struct	neta_timetable

struct	neta_timetable_result

Functions
int	NetA_compute_bridges (dglGraph_s graph, struct ilist bridge_list)
	Get number of bridges in the graph. More...

int	NetA_articulation_points (dglGraph_s graph, struct ilist articulation_list)
	Get number of articulation points in the graph. More...

int	NetA_weakly_connected_components (dglGraph_s graph, int component)
	Computes weakly connected components. More...

int	NetA_strongly_connected_components (dglGraph_s graph, int component)
	Computes strongly connected components with Kosaraju's two-pass algorithm. More...

int	NetA_spanning_tree (dglGraph_s graph, struct ilist tree_list)
	Get number of edges in the spanning forest. More...

int	NetA_flow (dglGraph_s graph, struct ilist source_list, struct ilist sink_list, int flow)
	Get max flow from source to sink. More...

int	NetA_min_cut (dglGraph_s graph, struct ilist source_list, struct ilist sink_list, int flow, struct ilist *cut)
	Calculates minimum cut between source(s) and sink(s). More...

int	NetA_split_vertices (dglGraph_s in, dglGraph_s out, int *node_costs)
	Splits each vertex of in graph into two vertices. More...

void	NetA_add_point_on_node (struct Map_info In, struct Map_info Out, int node, struct line_cats *Cats)
	Writes point. More...

void	NetA_points_to_nodes (struct Map_info In, struct ilist point_list)
	Finds node. More...

int	NetA_get_node_costs (struct Map_info In, int layer, char column, int *node_costs)
	Get node cost. More...

void	NetA_varray_to_nodes (struct Map_info map, struct varray varray, struct ilist nodes, int nodes_to_features)
	Get list of nodes from varray. More...

int	NetA_initialise_varray (struct Map_info In, int layer, int mask_type, char where, char cat, struct varray *varray)
	Initialize varray. More...

void	NetA_degree_centrality (dglGraph_s graph, double degree)
	Computes degree centrality measure. More...

int	NetA_eigenvector_centrality (dglGraph_s graph, int iterations, double error, double eigenvector)
	Computes eigenvector centrality using edge costs as weights. More...

int	NetA_betweenness_closeness (dglGraph_s graph, double betweenness, double *closeness)
	Computes betweenness and closeness centrality measure using Brandes algorithm. More...

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...

int	NetA_init_timetable_from_db (struct Map_info In, int route_layer, int walk_layer, char route_id, char times, char to_stop, char walk_length, neta_timetable timetable, int route_ids, int stop_ids)
	Initialises timetable from a database. More...

int	NetA_timetable_shortest_path (neta_timetable timetable, int from_stop, int to_stop, int start_time, int min_change, int max_changes, int walking_change, neta_timetable_result result)
	Computes the earliest arrival time. More...

int	NetA_timetable_get_route_time (neta_timetable *timetable, int stop, int route)
	Get time. More...

void	NetA_timetable_result_release (neta_timetable_result *result)
	Free neta_timetable_result structure. More...

Function Documentation

◆ NetA_add_point_on_node()

void NetA_add_point_on_node	(	struct Map_info *	In,
		struct Map_info *	Out,
		int	node,
		struct line_cats *	Cats
	)

Writes point.

Writes GV_POINT to Out at the position of the node in In.

Parameters

	In	pointer to Map_info structure (input vector map)
[in,out]	Out	pointer to Map_info structure (output vector map)
	node	node id
	Cats	pointer to line_cats structures

Definition at line 35 of file utils.c.

◆ NetA_articulation_points()

int NetA_articulation_points	(	dglGraph_s *	graph,
		struct ilist *	articulation_list
	)

Get number of articulation points in the graph.

Parameters

	graph	input graph
[out]	articulation_list	list of articulation points

Returns: number of points; -1 on error

Definition at line 32 of file articulation_point.c.

◆ NetA_betweenness_closeness()

int NetA_betweenness_closeness	(	dglGraph_s *	graph,
		double *	betweenness,
		double *	closeness
	)

Computes betweenness and closeness centrality measure using Brandes algorithm.

Edge costs must be nonnegative. If some edge costs are negative then the behaviour of this method is undefined.

Parameters

	graph	input graph
[out]	betweenness	betweeness values
[out]	closeness	cloneness values

Returns: 0 on success; -1 on failure

Definition at line 126 of file centrality.c.

References _, count, dglGet_NodeCount(), dglNode_T_First(), dglNode_T_Initialize(), dglNode_T_Next(), dst, G_calloc, G_fatal_error(), G_percent(), G_percent_reset(), complex::i, and Vect_new_list().

◆ NetA_compute_bridges()

int NetA_compute_bridges	(	dglGraph_s *	graph,
		struct ilist *	bridge_list
	)

Get number of bridges in the graph.

Bridge is an array containing the indices of the bridges.

Parameters

	graph	input graph
[out]	bridge_list	list of bridges

Returns: number of bridges, -1 on error

Definition at line 33 of file bridge.c.

◆ NetA_degree_centrality()

void NetA_degree_centrality	(	dglGraph_s *	graph,
		double *	degree
	)

Computes degree centrality measure.

Array degree has to be properly initialised to nnodes+1 elements

Parameters

	graph	input graph
[out]	degree	array of degrees

Definition at line 32 of file centrality.c.

References dglGet_NodeCount(), dglGetNode(), dglNodeGet_OutDegree(), and complex::i.

◆ 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_eigenvector_centrality()

int NetA_eigenvector_centrality	(	dglGraph_s *	graph,
		int	iterations,
		double	error,
		double *	eigenvector
	)

Computes eigenvector centrality using edge costs as weights.

Parameters

	graph	input graph
	iterations	number of iterations
	error	?
[out]	eigenvector	eigen vector value

Returns: 0 on success; -1 on failure

Definition at line 54 of file centrality.c.

References complex::i.

◆ 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.

◆ NetA_flow()

int NetA_flow	(	dglGraph_s *	graph,
		struct ilist *	source_list,
		struct ilist *	sink_list,
		int *	flow
	)

Get max flow from source to sink.

Array flow stores flow for each edge. Negative flow corresponds to a flow in opposite direction. The function assumes that the edge costs correspond to edge capacities.

Parameters

	graph	input graph
	source_list	list of sources
	sink_list	list of sinks
[out]	flow	max flows

Returns: number of flows; -1 on failure

Definition at line 47 of file flow.c.

References _, dglGet_EdgeCount(), dglGet_NodeAttrSize(), dglGet_NodeCount(), G_calloc, G_fatal_error(), ilist::n_values, NULL, and ilist::value.

◆ NetA_get_node_costs()

int NetA_get_node_costs	(	struct Map_info *	In,
		int	layer,
		char *	column,
		int *	node_costs
	)

Get node cost.

For each node in the map, finds the category of the point on it (if there is any) and stores the value associated with this category in the array node_costs. If there is no point with a category, node_costs=0.

node_costs are multiplied by the graph's cost multiplier and truncated to integers (as is done in Vect_net_build_graph)

Parameters

	In	pointer to Map_info structure
	layer	layer number
	column	name of column
[out]	node_costs	list of node costs

Returns: 1 on success; 0 on failure

Definition at line 105 of file utils.c.

◆ NetA_init_timetable_from_db()

int NetA_init_timetable_from_db	(	struct Map_info *	In,
		int	route_layer,
		int	walk_layer,
		char *	route_id,
		char *	times,
		char *	to_stop,
		char *	walk_length,
		neta_timetable *	timetable,
		int **	route_ids,
		int **	stop_ids
	)

Initialises timetable from a database.

Parameters

In	pointer to Map_info structure
route_layer	layer number of routes
walk_layer	layer number of walkers
route_id	id of route
times	list of timestamps
to_stop	?
walk_length	walk length as string
timetable	pointer to neta_timetable
route_ids	list of route ids
stop_ids	lits of stop ids

Returns: 0 on success; non-zero value on failure

Definition at line 113 of file timetables.c.

◆ NetA_initialise_varray()

int NetA_initialise_varray	(	struct Map_info *	In,
		int	layer,
		int	mask_type,
		char *	where,
		char *	cat,
		struct varray **	varray
	)

Initialize varray.

Parameters

	In	pointer to Map_info structure
	layer	layer number
	mask_type	?
	where	where statement
	cat	?
[out]	pointer	to varray structure

Returns: number of items set; -1 on error

Definition at line 229 of file utils.c.

References _, G_fatal_error(), G_warning(), NULL, Vect_cat_get(), Vect_destroy_cats_struct(), Vect_get_num_lines(), Vect_new_cats_struct(), Vect_new_varray(), Vect_read_line(), Vect_set_varray_from_cat_string(), and Vect_set_varray_from_db().

◆ NetA_min_cut()

int NetA_min_cut	(	dglGraph_s *	graph,
		struct ilist *	source_list,
		struct ilist *	sink_list,
		int *	flow,
		struct ilist *	cut
	)

Calculates minimum cut between source(s) and sink(s).

Flow is the array produced by NetA_flow() method when called with source_list and sink_list as the input. The output of this and NetA_flow() method should be the same.

Parameters

	graph	input graph
	source_list	list of sources
	sink_list	list of sinks
	flow
[out]	cut	list of edges (cut)

Returns: number of edges; -1 on failure

Definition at line 177 of file flow.c.

References _, dglGet_NodeCount(), G_calloc, G_fatal_error(), ilist::n_values, and ilist::value.

◆ NetA_points_to_nodes()

void NetA_points_to_nodes	(	struct Map_info *	In,
		struct ilist *	point_list
	)

Finds node.

Find the node corresponding to each point in the point_list

Parameters

In	pointer to Map_info structure
point_list	list of points (their ids)

Definition at line 73 of file utils.c.

◆ NetA_spanning_tree()

int NetA_spanning_tree	(	dglGraph_s *	graph,
		struct ilist *	tree_list
	)

Get number of edges in the spanning forest.

Parameters

	graph	input graph
[out]	list	of edges

Returns: number of edges; -1 on failure

Definition at line 91 of file spanningtree.c.

References dglGet_EdgeCount(), dglGet_NodeCount(), and G_calloc.

◆ NetA_split_vertices()

int NetA_split_vertices	(	dglGraph_s *	in,
		dglGraph_s *	out,
		int *	node_costs
	)

Splits each vertex of in graph into two vertices.

The method splits each vertex of in graph into two vertices: in vertex and out vertex. Also, it adds an edge from an in vertex to the corresponding out vertex (capacity=2) and it adds an edge from out vertex to in vertex for each edge present in the in graph (forward capacity=1, backward capacity=0). If the id of a vertex is v then id of in vertex is 2*v-1 and of out vertex 2*v.

Parameters

in	from graph
out	to graph
node_costs	list of node costs

Returns: number of undirected edges in the graph; -1 on failure

Definition at line 270 of file flow.c.

References dglAddEdge(), dglGet_NodeCount(), dglInitialize(), dglNode_T_First(), dglNode_T_Initialize(), dglNode_T_Next(), dglNode_T_Release(), and dglNodeGet_Id().

◆ NetA_strongly_connected_components()

int NetA_strongly_connected_components	(	dglGraph_s *	graph,
		int *	component
	)

Computes strongly connected components with Kosaraju's two-pass algorithm.

Parameters

	graph	input graph
[out]	component	array of component ids

Returns: number of components; -1 on failure

Definition at line 154 of file components.c.

References _, dglGet_NodeAttrSize(), dglGet_NodeCount(), dglNode_T_First(), dglNode_T_Initialize(), dglNode_T_Next(), dglNodeGet_Id(), G_calloc, G_fatal_error(), G_warning(), order(), and _dglGraph::Version.

◆ NetA_timetable_get_route_time()

int NetA_timetable_get_route_time	(	neta_timetable *	timetable,
		int	stop,
		int	route
	)

Get time.

Get time when route "route" arrives at stop "stop" or -1.

Parameters

timetable	pointer to neta_timetable structure
stop	'stop' node id
route	route id

Returns: time; -1 if not found

Definition at line 534 of file timetables.c.

References neta_timetable::route_length, neta_timetable::route_stops, and neta_timetable::route_times.

◆ NetA_timetable_result_release()

void NetA_timetable_result_release ( neta_timetable_result * result )

Free neta_timetable_result structure.

Parameters

result pointer to neta_timetable_result structure

Definition at line 550 of file timetables.c.

References neta_timetable_result::dst, G_free(), neta_timetable_result::prev_route, neta_timetable_result::prev_stop, and neta_timetable_result::rows.

◆ NetA_timetable_shortest_path()

int NetA_timetable_shortest_path	(	neta_timetable *	timetable,
		int	from_stop,
		int	to_stop,
		int	start_time,
		int	min_change,
		int	max_changes,
		int	walking_change,
		neta_timetable_result *	result
	)

Computes the earliest arrival time.

Computes the earliest arrival time to to_stop from from_stop starting at start_time, or -1 if no path exists

Parameters

	timetable	pointer to neta_timetable structure
	from_stop	'from' node
	to_stop	'to' stop
	start_time	start timestamp
	min_change	?
	max_changes	?
	walking_change	?
[out]	result	pointer to neta_timetable_result

Returns: ?; -1 on error

Definition at line 392 of file timetables.c.

References _, dglHeapInit(), neta_timetable_result::dst, G_calloc, G_warning(), neta_timetable_result::prev_conn, neta_timetable_result::prev_route, neta_timetable_result::prev_stop, _dglHeapData::pv, neta_timetable_result::routes, neta_timetable_result::rows, and neta_timetable::stops.

◆ NetA_varray_to_nodes()

void NetA_varray_to_nodes	(	struct Map_info *	map,
		struct varray *	varray,
		struct ilist *	nodes,
		int *	nodes_to_features
	)

Get list of nodes from varray.

Returns the list of all nodes on features selected by varray. nodes_to_features contains the index of a feature adjacent to each node or -1 if no such feature specified by varray exists. Nodes_to_features might be NULL, in which case it is left unitialised. Nodes_to_features will be wrong if several lines connect to the same node.

Parameters

	map	pointer to Map_info structure
	varray	pointer to varray structure
[out]	nodes	list of node ids
[out]	nodes_to_features	maps nodes to features

Definition at line 174 of file utils.c.

◆ NetA_weakly_connected_components()

int NetA_weakly_connected_components	(	dglGraph_s *	graph,
		int *	component
	)

Computes weakly connected components.

Parameters

	graph	input graph
[out]	component	array of component ids

Returns: number of components; -1 on failure

Definition at line 52 of file components.c.

References _, dglGet_NodeAttrSize(), dglGet_NodeCount(), dglNode_T_First(), dglNode_T_Initialize(), dglNode_T_Next(), dglNodeGet_Id(), G_calloc, G_fatal_error(), G_warning(), and _dglGraph::Version.

Data Structures

Functions

Function Documentation

◆ NetA_add_point_on_node()

◆ NetA_articulation_points()

◆ NetA_betweenness_closeness()

◆ NetA_compute_bridges()

◆ NetA_degree_centrality()

◆ NetA_distance_from_points()

◆ NetA_distance_to_points()

◆ NetA_eigenvector_centrality()

◆ NetA_find_path()

◆ NetA_flow()

◆ NetA_get_node_costs()

◆ NetA_init_timetable_from_db()

◆ NetA_initialise_varray()

◆ NetA_min_cut()

◆ NetA_points_to_nodes()

◆ NetA_spanning_tree()

◆ NetA_split_vertices()

◆ NetA_strongly_connected_components()

◆ NetA_timetable_get_route_time()

◆ NetA_timetable_result_release()

◆ NetA_timetable_shortest_path()

◆ NetA_varray_to_nodes()

◆ NetA_weakly_connected_components()