GRASS GIS 8 Programmer's Manual
8.2.2dev(2023)-3d2c704037
|
Go to the source code of 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... | |
int NetA_articulation_points | ( | dglGraph_s * | graph, |
struct ilist * | articulation_list | ||
) |
Get number of articulation points in the graph.
graph | input graph | |
[out] | articulation_list | list of articulation points |
Definition at line 32 of file articulation_point.c.
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.
graph | input graph | |
[out] | betweenness | betweeness values |
[out] | closeness | cloneness values |
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().
int NetA_compute_bridges | ( | dglGraph_s * | graph, |
struct ilist * | bridge_list | ||
) |
void NetA_degree_centrality | ( | dglGraph_s * | graph, |
double * | degree | ||
) |
Computes degree centrality measure.
Array degree has to be properly initialised to nnodes+1 elements
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.
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.
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 |
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.
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.
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 |
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.
int NetA_eigenvector_centrality | ( | dglGraph_s * | graph, |
int | iterations, | ||
double | error, | ||
double * | eigenvector | ||
) |
Computes eigenvector centrality using edge costs as weights.
graph | input graph | |
iterations | number of iterations | |
error | ? | |
[out] | eigenvector | eigen vector value |
Definition at line 54 of file centrality.c.
References complex::i.
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.
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 |
Definition at line 247 of file vector/neta/path.c.
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.
graph | input graph | |
source_list | list of sources | |
sink_list | list of sinks | |
[out] | flow | max flows |
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.
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)
In | pointer to Map_info structure | |
layer | layer number | |
column | name of column | |
[out] | node_costs | list of node costs |
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.
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 |
Definition at line 113 of file timetables.c.
int NetA_initialise_varray | ( | struct Map_info * | In, |
int | layer, | ||
int | mask_type, | ||
char * | where, | ||
char * | cat, | ||
struct varray ** | varray | ||
) |
Initialize varray.
In | pointer to Map_info structure | |
layer | layer number | |
mask_type | ? | |
where | where statement | |
cat | ? | |
[out] | pointer | to varray structure |
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().
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.
graph | input graph | |
source_list | list of sources | |
sink_list | list of sinks | |
flow | ||
[out] | cut | list of edges (cut) |
Definition at line 177 of file flow.c.
References _, dglGet_NodeCount(), G_calloc, G_fatal_error(), ilist::n_values, and ilist::value.
int NetA_spanning_tree | ( | dglGraph_s * | graph, |
struct ilist * | tree_list | ||
) |
Get number of edges in the spanning forest.
graph | input graph | |
[out] | list | of edges |
Definition at line 91 of file spanningtree.c.
References dglGet_EdgeCount(), dglGet_NodeCount(), and G_calloc.
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.
in | from graph |
out | to graph |
node_costs | list of node costs |
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().
int NetA_strongly_connected_components | ( | dglGraph_s * | graph, |
int * | component | ||
) |
Computes strongly connected components with Kosaraju's two-pass algorithm.
graph | input graph | |
[out] | component | array of component ids |
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.
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.
timetable | pointer to neta_timetable structure |
stop | 'stop' node id |
route | route id |
Definition at line 534 of file timetables.c.
References neta_timetable::route_length, neta_timetable::route_stops, and neta_timetable::route_times.
void NetA_timetable_result_release | ( | neta_timetable_result * | result | ) |
Free neta_timetable_result structure.
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.
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
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 |
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.
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.
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 |
int NetA_weakly_connected_components | ( | dglGraph_s * | graph, |
int * | component | ||
) |
Computes weakly connected components.
graph | input graph | |
[out] | component | array of component ids |
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.