GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d37ee165c
defs/neta.h File Reference
This graph shows which files directly or indirectly include this file:

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

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
Inpointer to Map_info structure (input vector map)
[in,out]Outpointer to Map_info structure (output vector map)
nodenode id
Catspointer 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
graphinput graph
[out]articulation_listlist 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
graphinput graph
[out]betweennessbetweeness values
[out]closenesscloneness 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
graphinput graph
[out]bridge_listlist 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
graphinput graph
[out]degreearray 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
graphinput graph
fromlist of 'from' positions
[out]dstarray of costs to reach nodes
[out]prevarray 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
graphinput graph
tolist of 'to' positions
[out]dstarray of costs to reach nodes
[out]nxtarray 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
graphinput graph
iterationsnumber of iterations
error?
[out]eigenvectoreigen 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
graphinput graph
from'from' position
to'to' position
edgesarray of edges indicating whether an edge should be used
[out]listlist 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
graphinput graph
source_listlist of sources
sink_listlist of sinks
[out]flowmax 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
Inpointer to Map_info structure
layerlayer number
columnname of column
[out]node_costslist 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
Inpointer to Map_info structure
route_layerlayer number of routes
walk_layerlayer number of walkers
route_idid of route
timeslist of timestamps
to_stop?
walk_lengthwalk length as string
timetablepointer to neta_timetable
route_idslist of route ids
stop_idslits 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
Inpointer to Map_info structure
layerlayer number
mask_type?
wherewhere statement
cat?
[out]pointerto 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
graphinput graph
source_listlist of sources
sink_listlist of sinks
flow
[out]cutlist 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
Inpointer to Map_info structure
point_listlist 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
graphinput graph
[out]listof 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
infrom graph
outto graph
node_costslist 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
graphinput graph
[out]componentarray 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
timetablepointer to neta_timetable structure
stop'stop' node id
routeroute 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)

◆ 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
timetablepointer to neta_timetable structure
from_stop'from' node
to_stop'to' stop
start_timestart timestamp
min_change?
max_changes?
walking_change?
[out]resultpointer 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
mappointer to Map_info structure
varraypointer to varray structure
[out]nodeslist of node ids
[out]nodes_to_featuresmaps 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
graphinput graph
[out]componentarray 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.