Generated by Cython 0.29.14
Yellow lines hint at Python interaction.
Click on a line that starts with a "+" to see the C code that Cython generated for it.
Raw output: basic_path_finding.pyx
001: """
002: -----------------------------------------------------------------------------------------------------------
003: Package: AequilibraE
004: Name: Core path computation algorithms, accessible only at Cython/C Level
005: Purpose: Supports the implementation shortest path and network loading routines
006: Original Author: Pedro Camargo (c@margo.co)
007: Contributors:
008: Last edited by: Pedro Camrgo
009: Website: www.AequilibraE.com
010: Repository: https://github.com/AequilibraE/AequilibraE
011: Created: 15/09/2013
012: Updated: 24/04/2018
013: Copyright: (c) AequilibraE authors
014: Licence: See LICENSE.TXT
015: -----------------------------------------------------------------------------------------------------------
016: Original Algorithm for Shortest path (Dijkstra with a Fibonacci heap) was written by Jake Vanderplas <vanderplas@astro.washington.edu> under license: BSD, (C) 2012
017: """
018:
019: """
020: TODO:
021: LIST OF ALL THE THINGS WE NEED TO DO TO NOT HAVE TO HAVE nodes 1..n as CENTROIDS. ARBITRARY NUMBERING
022: - Checks of weather the centroid we are computing path from is a centroid and/or exists in the graph
023: - Re-write function **network_loading** on the part of loading flows to centroids
024: """
025: cimport cython
026: from libc.math cimport isnan
027:
028: include 'parameters.pxi'
029: from libc.stdlib cimport abort, malloc, free
030:
031: @cython.wraparound(False)
032: @cython.embedsignature(True)
033: @cython.boundscheck(False) # turn of bounds-checking for entire function
+034: cpdef void network_loading(long classes,
static PyObject *__pyx_pw_3AoN_1network_loading(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static void __pyx_f_3AoN_network_loading(long __pyx_v_classes, __Pyx_memviewslice __pyx_v_demand, __Pyx_memviewslice __pyx_v_pred, __Pyx_memviewslice __pyx_v_conn, __Pyx_memviewslice __pyx_v_link_loads, CYTHON_UNUSED __Pyx_memviewslice __pyx_v_no_path, __Pyx_memviewslice __pyx_v_reached_first, __Pyx_memviewslice __pyx_v_node_load, long __pyx_v_found, CYTHON_UNUSED int __pyx_skip_dispatch) {
PY_LONG_LONG __pyx_v_i;
PY_LONG_LONG __pyx_v_j;
PY_LONG_LONG __pyx_v_predecessor;
PY_LONG_LONG __pyx_v_connector;
PY_LONG_LONG __pyx_v_node;
PY_LONG_LONG __pyx_v_zones;
PY_LONG_LONG __pyx_v_N;
/* … */
/* function exit code */
goto __pyx_L0;
__pyx_L1_error:;
__PYX_XDEC_MEMVIEW(&__pyx_t_4, 0);
__Pyx_WriteUnraisable("AoN.network_loading", __pyx_clineno, __pyx_lineno, __pyx_filename, 1, 1);
__pyx_L0:;
}
/* Python wrapper */
static PyObject *__pyx_pw_3AoN_1network_loading(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static char __pyx_doc_3AoN_network_loading[] = "network_loading(long classes, double[:, :] demand, long long[:] pred, long long[:] conn, double[:, :] link_loads, long long[:] no_path, long long[:] reached_first, double[:, :] node_load, long found) -> void";
static PyObject *__pyx_pw_3AoN_1network_loading(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
long __pyx_v_classes;
__Pyx_memviewslice __pyx_v_demand = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_pred = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_conn = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_link_loads = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_no_path = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_reached_first = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_node_load = { 0, 0, { 0 }, { 0 }, { 0 } };
long __pyx_v_found;
PyObject *__pyx_r = 0;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("network_loading (wrapper)", 0);
{
static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_classes,&__pyx_n_s_demand,&__pyx_n_s_pred,&__pyx_n_s_conn,&__pyx_n_s_link_loads,&__pyx_n_s_no_path,&__pyx_n_s_reached_first,&__pyx_n_s_node_load,&__pyx_n_s_found,0};
PyObject* values[9] = {0,0,0,0,0,0,0,0,0};
if (unlikely(__pyx_kwds)) {
Py_ssize_t kw_args;
const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
switch (pos_args) {
case 9: values[8] = PyTuple_GET_ITEM(__pyx_args, 8);
CYTHON_FALLTHROUGH;
case 8: values[7] = PyTuple_GET_ITEM(__pyx_args, 7);
CYTHON_FALLTHROUGH;
case 7: values[6] = PyTuple_GET_ITEM(__pyx_args, 6);
CYTHON_FALLTHROUGH;
case 6: values[5] = PyTuple_GET_ITEM(__pyx_args, 5);
CYTHON_FALLTHROUGH;
case 5: values[4] = PyTuple_GET_ITEM(__pyx_args, 4);
CYTHON_FALLTHROUGH;
case 4: values[3] = PyTuple_GET_ITEM(__pyx_args, 3);
CYTHON_FALLTHROUGH;
case 3: values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
CYTHON_FALLTHROUGH;
case 2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
CYTHON_FALLTHROUGH;
case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
CYTHON_FALLTHROUGH;
case 0: break;
default: goto __pyx_L5_argtuple_error;
}
kw_args = PyDict_Size(__pyx_kwds);
switch (pos_args) {
case 0:
if (likely((values[0] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_classes)) != 0)) kw_args--;
else goto __pyx_L5_argtuple_error;
CYTHON_FALLTHROUGH;
case 1:
if (likely((values[1] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_demand)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("network_loading", 1, 9, 9, 1); __PYX_ERR(0, 34, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 2:
if (likely((values[2] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_pred)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("network_loading", 1, 9, 9, 2); __PYX_ERR(0, 34, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 3:
if (likely((values[3] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_conn)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("network_loading", 1, 9, 9, 3); __PYX_ERR(0, 34, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 4:
if (likely((values[4] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_link_loads)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("network_loading", 1, 9, 9, 4); __PYX_ERR(0, 34, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 5:
if (likely((values[5] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_no_path)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("network_loading", 1, 9, 9, 5); __PYX_ERR(0, 34, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 6:
if (likely((values[6] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_reached_first)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("network_loading", 1, 9, 9, 6); __PYX_ERR(0, 34, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 7:
if (likely((values[7] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_node_load)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("network_loading", 1, 9, 9, 7); __PYX_ERR(0, 34, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 8:
if (likely((values[8] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_found)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("network_loading", 1, 9, 9, 8); __PYX_ERR(0, 34, __pyx_L3_error)
}
}
if (unlikely(kw_args > 0)) {
if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "network_loading") < 0)) __PYX_ERR(0, 34, __pyx_L3_error)
}
} else if (PyTuple_GET_SIZE(__pyx_args) != 9) {
goto __pyx_L5_argtuple_error;
} else {
values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
values[3] = PyTuple_GET_ITEM(__pyx_args, 3);
values[4] = PyTuple_GET_ITEM(__pyx_args, 4);
values[5] = PyTuple_GET_ITEM(__pyx_args, 5);
values[6] = PyTuple_GET_ITEM(__pyx_args, 6);
values[7] = PyTuple_GET_ITEM(__pyx_args, 7);
values[8] = PyTuple_GET_ITEM(__pyx_args, 8);
}
__pyx_v_classes = __Pyx_PyInt_As_long(values[0]); if (unlikely((__pyx_v_classes == (long)-1) && PyErr_Occurred())) __PYX_ERR(0, 34, __pyx_L3_error)
__pyx_v_demand = __Pyx_PyObject_to_MemoryviewSlice_dsds_double(values[1], PyBUF_WRITABLE); if (unlikely(!__pyx_v_demand.memview)) __PYX_ERR(0, 35, __pyx_L3_error)
__pyx_v_pred = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[2], PyBUF_WRITABLE); if (unlikely(!__pyx_v_pred.memview)) __PYX_ERR(0, 36, __pyx_L3_error)
__pyx_v_conn = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[3], PyBUF_WRITABLE); if (unlikely(!__pyx_v_conn.memview)) __PYX_ERR(0, 37, __pyx_L3_error)
__pyx_v_link_loads = __Pyx_PyObject_to_MemoryviewSlice_dsds_double(values[4], PyBUF_WRITABLE); if (unlikely(!__pyx_v_link_loads.memview)) __PYX_ERR(0, 38, __pyx_L3_error)
__pyx_v_no_path = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[5], PyBUF_WRITABLE); if (unlikely(!__pyx_v_no_path.memview)) __PYX_ERR(0, 39, __pyx_L3_error)
__pyx_v_reached_first = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[6], PyBUF_WRITABLE); if (unlikely(!__pyx_v_reached_first.memview)) __PYX_ERR(0, 40, __pyx_L3_error)
__pyx_v_node_load = __Pyx_PyObject_to_MemoryviewSlice_dsds_double(values[7], PyBUF_WRITABLE); if (unlikely(!__pyx_v_node_load.memview)) __PYX_ERR(0, 41, __pyx_L3_error)
__pyx_v_found = __Pyx_PyInt_As_long(values[8]); if (unlikely((__pyx_v_found == (long)-1) && PyErr_Occurred())) __PYX_ERR(0, 42, __pyx_L3_error)
}
goto __pyx_L4_argument_unpacking_done;
__pyx_L5_argtuple_error:;
__Pyx_RaiseArgtupleInvalid("network_loading", 1, 9, 9, PyTuple_GET_SIZE(__pyx_args)); __PYX_ERR(0, 34, __pyx_L3_error)
__pyx_L3_error:;
__Pyx_AddTraceback("AoN.network_loading", __pyx_clineno, __pyx_lineno, __pyx_filename);
__Pyx_RefNannyFinishContext();
return NULL;
__pyx_L4_argument_unpacking_done:;
__pyx_r = __pyx_pf_3AoN_network_loading(__pyx_self, __pyx_v_classes, __pyx_v_demand, __pyx_v_pred, __pyx_v_conn, __pyx_v_link_loads, __pyx_v_no_path, __pyx_v_reached_first, __pyx_v_node_load, __pyx_v_found);
/* function exit code */
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
static PyObject *__pyx_pf_3AoN_network_loading(CYTHON_UNUSED PyObject *__pyx_self, long __pyx_v_classes, __Pyx_memviewslice __pyx_v_demand, __Pyx_memviewslice __pyx_v_pred, __Pyx_memviewslice __pyx_v_conn, __Pyx_memviewslice __pyx_v_link_loads, __Pyx_memviewslice __pyx_v_no_path, __Pyx_memviewslice __pyx_v_reached_first, __Pyx_memviewslice __pyx_v_node_load, long __pyx_v_found) {
PyObject *__pyx_r = NULL;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("network_loading", 0);
__Pyx_XDECREF(__pyx_r);
if (unlikely(!__pyx_v_demand.memview)) { __Pyx_RaiseUnboundLocalError("demand"); __PYX_ERR(0, 34, __pyx_L1_error) }
if (unlikely(!__pyx_v_pred.memview)) { __Pyx_RaiseUnboundLocalError("pred"); __PYX_ERR(0, 34, __pyx_L1_error) }
if (unlikely(!__pyx_v_conn.memview)) { __Pyx_RaiseUnboundLocalError("conn"); __PYX_ERR(0, 34, __pyx_L1_error) }
if (unlikely(!__pyx_v_link_loads.memview)) { __Pyx_RaiseUnboundLocalError("link_loads"); __PYX_ERR(0, 34, __pyx_L1_error) }
if (unlikely(!__pyx_v_no_path.memview)) { __Pyx_RaiseUnboundLocalError("no_path"); __PYX_ERR(0, 34, __pyx_L1_error) }
if (unlikely(!__pyx_v_reached_first.memview)) { __Pyx_RaiseUnboundLocalError("reached_first"); __PYX_ERR(0, 34, __pyx_L1_error) }
if (unlikely(!__pyx_v_node_load.memview)) { __Pyx_RaiseUnboundLocalError("node_load"); __PYX_ERR(0, 34, __pyx_L1_error) }
__pyx_t_1 = __Pyx_void_to_None(__pyx_f_3AoN_network_loading(__pyx_v_classes, __pyx_v_demand, __pyx_v_pred, __pyx_v_conn, __pyx_v_link_loads, __pyx_v_no_path, __pyx_v_reached_first, __pyx_v_node_load, __pyx_v_found, 0)); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 34, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_1);
__pyx_r = __pyx_t_1;
__pyx_t_1 = 0;
goto __pyx_L0;
/* function exit code */
__pyx_L1_error:;
__Pyx_XDECREF(__pyx_t_1);
__Pyx_AddTraceback("AoN.network_loading", __pyx_clineno, __pyx_lineno, __pyx_filename);
__pyx_r = NULL;
__pyx_L0:;
__PYX_XDEC_MEMVIEW(&__pyx_v_demand, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_pred, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_conn, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_link_loads, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_no_path, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_reached_first, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_node_load, 1);
__Pyx_XGIVEREF(__pyx_r);
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
035: double[:, :] demand,
036: long long [:] pred,
037: long long [:] conn,
038: double[:, :] link_loads,
039: long long [:] no_path,
040: long long [:] reached_first,
041: double [:, :] node_load,
042: long found) nogil:
043:
044: cdef long long i, j, predecessor, connector, node
+045: cdef long long zones = demand.shape[0]
__pyx_v_zones = (__pyx_v_demand.shape[0]);
+046: cdef long long N = node_load.shape[0]
__pyx_v_N = (__pyx_v_node_load.shape[0]);
047:
048: # Clean the node load array
+049: for i in range(N):
__pyx_t_1 = __pyx_v_N;
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_i = __pyx_t_3;
+050: node_load[i] = 0
__pyx_t_4.data = __pyx_v_node_load.data;
__pyx_t_4.memview = __pyx_v_node_load.memview;
__PYX_INC_MEMVIEW(&__pyx_t_4, 0);
{
Py_ssize_t __pyx_tmp_idx = __pyx_v_i;
Py_ssize_t __pyx_tmp_stride = __pyx_v_node_load.strides[0];
if ((0)) __PYX_ERR(0, 50, __pyx_L1_error)
__pyx_t_4.data += __pyx_tmp_idx * __pyx_tmp_stride;
}
__pyx_t_4.shape[0] = __pyx_v_node_load.shape[1];
__pyx_t_4.strides[0] = __pyx_v_node_load.strides[1];
__pyx_t_4.suboffsets[0] = -1;
{
double __pyx_temp_scalar = 0.0;
{
Py_ssize_t __pyx_temp_extent_0 = __pyx_t_4.shape[0];
Py_ssize_t __pyx_temp_stride_0 = __pyx_t_4.strides[0];
char *__pyx_temp_pointer_0;
Py_ssize_t __pyx_temp_idx_0;
__pyx_temp_pointer_0 = __pyx_t_4.data;
for (__pyx_temp_idx_0 = 0; __pyx_temp_idx_0 < __pyx_temp_extent_0; __pyx_temp_idx_0++) {
*((double *) __pyx_temp_pointer_0) = __pyx_temp_scalar;
__pyx_temp_pointer_0 += __pyx_temp_stride_0;
}
}
}
__PYX_XDEC_MEMVIEW(&__pyx_t_4, 0);
__pyx_t_4.memview = NULL;
__pyx_t_4.data = NULL;
}
051:
052: # Loads the demand to the centroids
+053: for j in range(classes):
__pyx_t_5 = __pyx_v_classes;
__pyx_t_6 = __pyx_t_5;
for (__pyx_t_1 = 0; __pyx_t_1 < __pyx_t_6; __pyx_t_1+=1) {
__pyx_v_j = __pyx_t_1;
+054: for i in range(zones):
__pyx_t_2 = __pyx_v_zones;
__pyx_t_3 = __pyx_t_2;
for (__pyx_t_7 = 0; __pyx_t_7 < __pyx_t_3; __pyx_t_7+=1) {
__pyx_v_i = __pyx_t_7;
+055: if not isnan(demand[i, j]):
__pyx_t_8 = __pyx_v_i;
__pyx_t_9 = __pyx_v_j;
__pyx_t_10 = ((!(isnan((*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_demand.data + __pyx_t_8 * __pyx_v_demand.strides[0]) ) + __pyx_t_9 * __pyx_v_demand.strides[1]) )))) != 0)) != 0);
if (__pyx_t_10) {
/* … */
}
}
}
+056: node_load[i, j] = demand[i, j]
__pyx_t_11 = __pyx_v_i;
__pyx_t_12 = __pyx_v_j;
__pyx_t_13 = __pyx_v_i;
__pyx_t_14 = __pyx_v_j;
*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_load.data + __pyx_t_13 * __pyx_v_node_load.strides[0]) ) + __pyx_t_14 * __pyx_v_node_load.strides[1]) )) = (*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_demand.data + __pyx_t_11 * __pyx_v_demand.strides[0]) ) + __pyx_t_12 * __pyx_v_demand.strides[1]) )));
057:
058: #Recursevely cascades to the origin
+059: for i in range(found, 0, -1):
for (__pyx_t_1 = __pyx_v_found; __pyx_t_1 > 0; __pyx_t_1-=1) {
__pyx_v_i = __pyx_t_1;
+060: node = reached_first[i]
__pyx_t_2 = __pyx_v_i;
__pyx_v_node = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_reached_first.data + __pyx_t_2 * __pyx_v_reached_first.strides[0]) )));
061:
062: # captures how we got to that node
+063: predecessor = pred[node]
__pyx_t_3 = __pyx_v_node;
__pyx_v_predecessor = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_pred.data + __pyx_t_3 * __pyx_v_pred.strides[0]) )));
+064: connector = conn[node]
__pyx_t_7 = __pyx_v_node;
__pyx_v_connector = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_conn.data + __pyx_t_7 * __pyx_v_conn.strides[0]) )));
065:
066: # loads the flow to the links for each class
+067: for j in range(classes):
__pyx_t_5 = __pyx_v_classes;
__pyx_t_6 = __pyx_t_5;
for (__pyx_t_15 = 0; __pyx_t_15 < __pyx_t_6; __pyx_t_15+=1) {
__pyx_v_j = __pyx_t_15;
+068: link_loads[connector, j] += node_load[node, j]
__pyx_t_16 = __pyx_v_node;
__pyx_t_17 = __pyx_v_j;
__pyx_t_18 = __pyx_v_connector;
__pyx_t_19 = __pyx_v_j;
*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_link_loads.data + __pyx_t_18 * __pyx_v_link_loads.strides[0]) ) + __pyx_t_19 * __pyx_v_link_loads.strides[1]) )) += (*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_load.data + __pyx_t_16 * __pyx_v_node_load.strides[0]) ) + __pyx_t_17 * __pyx_v_node_load.strides[1]) )));
069:
070: # Cascades the load from the node to their predecessor
+071: node_load[predecessor, j] += node_load[node, j]
__pyx_t_20 = __pyx_v_node;
__pyx_t_21 = __pyx_v_j;
__pyx_t_22 = __pyx_v_predecessor;
__pyx_t_23 = __pyx_v_j;
*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_load.data + __pyx_t_22 * __pyx_v_node_load.strides[0]) ) + __pyx_t_23 * __pyx_v_node_load.strides[1]) )) += (*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_load.data + __pyx_t_20 * __pyx_v_node_load.strides[0]) ) + __pyx_t_21 * __pyx_v_node_load.strides[1]) )));
}
}
072:
073: @cython.wraparound(False)
074: @cython.embedsignature(True)
075: @cython.boundscheck(False)
+076: cdef void _copy_skims(double[:,:] skim_matrix, #Skim matrix_procedures computed from one origin to all nodes
static void __pyx_f_3AoN__copy_skims(__Pyx_memviewslice __pyx_v_skim_matrix, __Pyx_memviewslice __pyx_v_final_skim_matrix) {
long __pyx_v_i;
long __pyx_v_j;
long __pyx_v_N;
long __pyx_v_skims;
/* … */
/* function exit code */
}
077: double[:,:] final_skim_matrix) nogil: #Skim matrix_procedures computed for one origin to all other centroids only
078:
079: cdef long i, j
+080: cdef long N = final_skim_matrix.shape[0]
__pyx_v_N = (__pyx_v_final_skim_matrix.shape[0]);
+081: cdef long skims = final_skim_matrix.shape[1]
__pyx_v_skims = (__pyx_v_final_skim_matrix.shape[1]);
082:
+083: for i in range(N):
__pyx_t_1 = __pyx_v_N;
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_i = __pyx_t_3;
+084: for j in range(skims):
__pyx_t_4 = __pyx_v_skims;
__pyx_t_5 = __pyx_t_4;
for (__pyx_t_6 = 0; __pyx_t_6 < __pyx_t_5; __pyx_t_6+=1) {
__pyx_v_j = __pyx_t_6;
+085: final_skim_matrix[i,j]=skim_matrix[i,j]
__pyx_t_7 = __pyx_v_i;
__pyx_t_8 = __pyx_v_j;
__pyx_t_9 = __pyx_v_i;
__pyx_t_10 = __pyx_v_j;
*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_final_skim_matrix.data + __pyx_t_9 * __pyx_v_final_skim_matrix.strides[0]) ) + __pyx_t_10 * __pyx_v_final_skim_matrix.strides[1]) )) = (*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_skim_matrix.data + __pyx_t_7 * __pyx_v_skim_matrix.strides[0]) ) + __pyx_t_8 * __pyx_v_skim_matrix.strides[1]) )));
}
}
086:
087:
+088: cdef return_an_int_view(input):
static PyObject *__pyx_f_3AoN_return_an_int_view(PyObject *__pyx_v_input) {
__Pyx_memviewslice __pyx_v_critical_links_view = { 0, 0, { 0 }, { 0 }, { 0 } };
PyObject *__pyx_r = NULL;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("return_an_int_view", 0);
/* … */
/* function exit code */
__pyx_L1_error:;
__PYX_XDEC_MEMVIEW(&__pyx_t_1, 1);
__Pyx_XDECREF(__pyx_t_2);
__Pyx_AddTraceback("AoN.return_an_int_view", __pyx_clineno, __pyx_lineno, __pyx_filename);
__pyx_r = 0;
__pyx_L0:;
__PYX_XDEC_MEMVIEW(&__pyx_v_critical_links_view, 1);
__Pyx_XGIVEREF(__pyx_r);
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
+089: cdef int [:] critical_links_view = input
__pyx_t_1 = __Pyx_PyObject_to_MemoryviewSlice_ds_int(__pyx_v_input, PyBUF_WRITABLE); if (unlikely(!__pyx_t_1.memview)) __PYX_ERR(0, 89, __pyx_L1_error) __pyx_v_critical_links_view = __pyx_t_1; __pyx_t_1.memview = NULL; __pyx_t_1.data = NULL;
+090: return critical_links_view
__Pyx_XDECREF(__pyx_r); __pyx_t_2 = __pyx_memoryview_fromslice(__pyx_v_critical_links_view, 1, (PyObject *(*)(char *)) __pyx_memview_get_int, (int (*)(char *, PyObject *)) __pyx_memview_set_int, 0);; if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 90, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_2); __pyx_r = __pyx_t_2; __pyx_t_2 = 0; goto __pyx_L0;
091:
092:
093: @cython.wraparound(False)
094: @cython.embedsignature(True)
095: @cython.boundscheck(False)
+096: cpdef void perform_select_link_analysis(long origin,
static PyObject *__pyx_pw_3AoN_3perform_select_link_analysis(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static void __pyx_f_3AoN_perform_select_link_analysis(CYTHON_UNUSED long __pyx_v_origin, CYTHON_UNUSED int __pyx_v_classes, __Pyx_memviewslice __pyx_v_demand, __Pyx_memviewslice __pyx_v_pred, __Pyx_memviewslice __pyx_v_conn, __Pyx_memviewslice __pyx_v_aux_link_flows, __Pyx_memviewslice __pyx_v_critical_array, int __pyx_v_query_type, CYTHON_UNUSED int __pyx_skip_dispatch) {
__pyx_t_3AoN_ITYPE_t __pyx_v_c;
__pyx_t_3AoN_ITYPE_t __pyx_v_j;
__pyx_t_3AoN_ITYPE_t __pyx_v_i;
__pyx_t_3AoN_ITYPE_t __pyx_v_p;
__pyx_t_3AoN_ITYPE_t __pyx_v_l;
unsigned int __pyx_v_dests;
unsigned int __pyx_v_q;
/* … */
/* function exit code */
}
/* Python wrapper */
static PyObject *__pyx_pw_3AoN_3perform_select_link_analysis(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static char __pyx_doc_3AoN_2perform_select_link_analysis[] = "perform_select_link_analysis(long origin, int classes, double[:, :] demand, long long[:] pred, long long[:] conn, long long[:] aux_link_flows, double[:, :] critical_array, int query_type) -> void";
static PyObject *__pyx_pw_3AoN_3perform_select_link_analysis(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
long __pyx_v_origin;
int __pyx_v_classes;
__Pyx_memviewslice __pyx_v_demand = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_pred = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_conn = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_aux_link_flows = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_critical_array = { 0, 0, { 0 }, { 0 }, { 0 } };
int __pyx_v_query_type;
PyObject *__pyx_r = 0;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("perform_select_link_analysis (wrapper)", 0);
{
static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_origin,&__pyx_n_s_classes,&__pyx_n_s_demand,&__pyx_n_s_pred,&__pyx_n_s_conn,&__pyx_n_s_aux_link_flows,&__pyx_n_s_critical_array,&__pyx_n_s_query_type,0};
PyObject* values[8] = {0,0,0,0,0,0,0,0};
if (unlikely(__pyx_kwds)) {
Py_ssize_t kw_args;
const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
switch (pos_args) {
case 8: values[7] = PyTuple_GET_ITEM(__pyx_args, 7);
CYTHON_FALLTHROUGH;
case 7: values[6] = PyTuple_GET_ITEM(__pyx_args, 6);
CYTHON_FALLTHROUGH;
case 6: values[5] = PyTuple_GET_ITEM(__pyx_args, 5);
CYTHON_FALLTHROUGH;
case 5: values[4] = PyTuple_GET_ITEM(__pyx_args, 4);
CYTHON_FALLTHROUGH;
case 4: values[3] = PyTuple_GET_ITEM(__pyx_args, 3);
CYTHON_FALLTHROUGH;
case 3: values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
CYTHON_FALLTHROUGH;
case 2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
CYTHON_FALLTHROUGH;
case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
CYTHON_FALLTHROUGH;
case 0: break;
default: goto __pyx_L5_argtuple_error;
}
kw_args = PyDict_Size(__pyx_kwds);
switch (pos_args) {
case 0:
if (likely((values[0] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_origin)) != 0)) kw_args--;
else goto __pyx_L5_argtuple_error;
CYTHON_FALLTHROUGH;
case 1:
if (likely((values[1] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_classes)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("perform_select_link_analysis", 1, 8, 8, 1); __PYX_ERR(0, 96, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 2:
if (likely((values[2] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_demand)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("perform_select_link_analysis", 1, 8, 8, 2); __PYX_ERR(0, 96, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 3:
if (likely((values[3] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_pred)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("perform_select_link_analysis", 1, 8, 8, 3); __PYX_ERR(0, 96, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 4:
if (likely((values[4] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_conn)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("perform_select_link_analysis", 1, 8, 8, 4); __PYX_ERR(0, 96, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 5:
if (likely((values[5] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_aux_link_flows)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("perform_select_link_analysis", 1, 8, 8, 5); __PYX_ERR(0, 96, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 6:
if (likely((values[6] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_critical_array)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("perform_select_link_analysis", 1, 8, 8, 6); __PYX_ERR(0, 96, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 7:
if (likely((values[7] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_query_type)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("perform_select_link_analysis", 1, 8, 8, 7); __PYX_ERR(0, 96, __pyx_L3_error)
}
}
if (unlikely(kw_args > 0)) {
if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "perform_select_link_analysis") < 0)) __PYX_ERR(0, 96, __pyx_L3_error)
}
} else if (PyTuple_GET_SIZE(__pyx_args) != 8) {
goto __pyx_L5_argtuple_error;
} else {
values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
values[3] = PyTuple_GET_ITEM(__pyx_args, 3);
values[4] = PyTuple_GET_ITEM(__pyx_args, 4);
values[5] = PyTuple_GET_ITEM(__pyx_args, 5);
values[6] = PyTuple_GET_ITEM(__pyx_args, 6);
values[7] = PyTuple_GET_ITEM(__pyx_args, 7);
}
__pyx_v_origin = __Pyx_PyInt_As_long(values[0]); if (unlikely((__pyx_v_origin == (long)-1) && PyErr_Occurred())) __PYX_ERR(0, 96, __pyx_L3_error)
__pyx_v_classes = __Pyx_PyInt_As_int(values[1]); if (unlikely((__pyx_v_classes == (int)-1) && PyErr_Occurred())) __PYX_ERR(0, 97, __pyx_L3_error)
__pyx_v_demand = __Pyx_PyObject_to_MemoryviewSlice_dsds_double(values[2], PyBUF_WRITABLE); if (unlikely(!__pyx_v_demand.memview)) __PYX_ERR(0, 98, __pyx_L3_error)
__pyx_v_pred = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[3], PyBUF_WRITABLE); if (unlikely(!__pyx_v_pred.memview)) __PYX_ERR(0, 99, __pyx_L3_error)
__pyx_v_conn = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[4], PyBUF_WRITABLE); if (unlikely(!__pyx_v_conn.memview)) __PYX_ERR(0, 100, __pyx_L3_error)
__pyx_v_aux_link_flows = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[5], PyBUF_WRITABLE); if (unlikely(!__pyx_v_aux_link_flows.memview)) __PYX_ERR(0, 101, __pyx_L3_error)
__pyx_v_critical_array = __Pyx_PyObject_to_MemoryviewSlice_dsds_double(values[6], PyBUF_WRITABLE); if (unlikely(!__pyx_v_critical_array.memview)) __PYX_ERR(0, 102, __pyx_L3_error)
__pyx_v_query_type = __Pyx_PyInt_As_int(values[7]); if (unlikely((__pyx_v_query_type == (int)-1) && PyErr_Occurred())) __PYX_ERR(0, 103, __pyx_L3_error)
}
goto __pyx_L4_argument_unpacking_done;
__pyx_L5_argtuple_error:;
__Pyx_RaiseArgtupleInvalid("perform_select_link_analysis", 1, 8, 8, PyTuple_GET_SIZE(__pyx_args)); __PYX_ERR(0, 96, __pyx_L3_error)
__pyx_L3_error:;
__Pyx_AddTraceback("AoN.perform_select_link_analysis", __pyx_clineno, __pyx_lineno, __pyx_filename);
__Pyx_RefNannyFinishContext();
return NULL;
__pyx_L4_argument_unpacking_done:;
__pyx_r = __pyx_pf_3AoN_2perform_select_link_analysis(__pyx_self, __pyx_v_origin, __pyx_v_classes, __pyx_v_demand, __pyx_v_pred, __pyx_v_conn, __pyx_v_aux_link_flows, __pyx_v_critical_array, __pyx_v_query_type);
/* function exit code */
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
static PyObject *__pyx_pf_3AoN_2perform_select_link_analysis(CYTHON_UNUSED PyObject *__pyx_self, long __pyx_v_origin, int __pyx_v_classes, __Pyx_memviewslice __pyx_v_demand, __Pyx_memviewslice __pyx_v_pred, __Pyx_memviewslice __pyx_v_conn, __Pyx_memviewslice __pyx_v_aux_link_flows, __Pyx_memviewslice __pyx_v_critical_array, int __pyx_v_query_type) {
PyObject *__pyx_r = NULL;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("perform_select_link_analysis", 0);
__Pyx_XDECREF(__pyx_r);
if (unlikely(!__pyx_v_demand.memview)) { __Pyx_RaiseUnboundLocalError("demand"); __PYX_ERR(0, 96, __pyx_L1_error) }
if (unlikely(!__pyx_v_pred.memview)) { __Pyx_RaiseUnboundLocalError("pred"); __PYX_ERR(0, 96, __pyx_L1_error) }
if (unlikely(!__pyx_v_conn.memview)) { __Pyx_RaiseUnboundLocalError("conn"); __PYX_ERR(0, 96, __pyx_L1_error) }
if (unlikely(!__pyx_v_aux_link_flows.memview)) { __Pyx_RaiseUnboundLocalError("aux_link_flows"); __PYX_ERR(0, 96, __pyx_L1_error) }
if (unlikely(!__pyx_v_critical_array.memview)) { __Pyx_RaiseUnboundLocalError("critical_array"); __PYX_ERR(0, 96, __pyx_L1_error) }
__pyx_t_1 = __Pyx_void_to_None(__pyx_f_3AoN_perform_select_link_analysis(__pyx_v_origin, __pyx_v_classes, __pyx_v_demand, __pyx_v_pred, __pyx_v_conn, __pyx_v_aux_link_flows, __pyx_v_critical_array, __pyx_v_query_type, 0)); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 96, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_1);
__pyx_r = __pyx_t_1;
__pyx_t_1 = 0;
goto __pyx_L0;
/* function exit code */
__pyx_L1_error:;
__Pyx_XDECREF(__pyx_t_1);
__Pyx_AddTraceback("AoN.perform_select_link_analysis", __pyx_clineno, __pyx_lineno, __pyx_filename);
__pyx_r = NULL;
__pyx_L0:;
__PYX_XDEC_MEMVIEW(&__pyx_v_demand, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_pred, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_conn, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_aux_link_flows, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_critical_array, 1);
__Pyx_XGIVEREF(__pyx_r);
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
097: int classes,
098: double[:, :] demand,
099: long long [:] pred,
100: long long [:] conn,
101: long long [:] aux_link_flows,
102: double [:, :] critical_array,
103: int query_type) nogil:
104: cdef unsigned int t_origin
105: cdef ITYPE_t c, j, i, p, l
+106: cdef unsigned int dests = demand.shape[0]
__pyx_v_dests = (__pyx_v_demand.shape[0]);
+107: cdef unsigned int q = critical_array.shape[0]
__pyx_v_q = (__pyx_v_critical_array.shape[0]);
108:
109: """ TODO:
110: FIX THE SELECT LINK ANALYSIS FOR MULTIPLE CLASSES"""
+111: l = 0
__pyx_v_l = 0;
+112: for j in range(dests):
__pyx_t_1 = __pyx_v_dests;
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_j = __pyx_t_3;
+113: if demand[j, l] > 0:
__pyx_t_4 = __pyx_v_j;
__pyx_t_5 = __pyx_v_l;
__pyx_t_6 = (((*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_demand.data + __pyx_t_4 * __pyx_v_demand.strides[0]) ) + __pyx_t_5 * __pyx_v_demand.strides[1]) ))) > 0.0) != 0);
if (__pyx_t_6) {
/* … */
}
+114: p = pred[j]
__pyx_t_7 = __pyx_v_j;
__pyx_v_p = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_pred.data + __pyx_t_7 * __pyx_v_pred.strides[0]) )));
+115: j = i
__pyx_v_j = __pyx_v_i;
+116: while p >= 0:
while (1) {
__pyx_t_6 = ((__pyx_v_p >= 0) != 0);
if (!__pyx_t_6) break;
+117: c = conn[j]
__pyx_t_8 = __pyx_v_j;
__pyx_v_c = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_conn.data + __pyx_t_8 * __pyx_v_conn.strides[0]) )));
+118: aux_link_flows[c] = 1
__pyx_t_9 = __pyx_v_c;
*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_aux_link_flows.data + __pyx_t_9 * __pyx_v_aux_link_flows.strides[0]) )) = 1;
+119: j = p
__pyx_v_j = __pyx_v_p;
+120: p = pred[j]
__pyx_t_10 = __pyx_v_j;
__pyx_v_p = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_pred.data + __pyx_t_10 * __pyx_v_pred.strides[0]) )));
}
+121: if query_type == 1: # Either one of the links in the query
__pyx_t_6 = ((__pyx_v_query_type == 1) != 0);
if (__pyx_t_6) {
/* … */
}
}
+122: for i in range(q):
__pyx_t_11 = __pyx_v_q;
__pyx_t_12 = __pyx_t_11;
for (__pyx_t_13 = 0; __pyx_t_13 < __pyx_t_12; __pyx_t_13+=1) {
__pyx_v_i = __pyx_t_13;
+123: if aux_link_flows[i] == 1:
__pyx_t_14 = __pyx_v_i;
__pyx_t_6 = (((*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_aux_link_flows.data + __pyx_t_14 * __pyx_v_aux_link_flows.strides[0]) ))) == 1) != 0);
if (__pyx_t_6) {
}
}
124: critical_array
125:
126:
127: @cython.wraparound(False)
128: @cython.embedsignature(True)
129: @cython.boundscheck(False)
+130: cpdef void put_path_file_on_disk(unsigned int orig,
static PyObject *__pyx_pw_3AoN_5put_path_file_on_disk(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static void __pyx_f_3AoN_put_path_file_on_disk(unsigned int __pyx_v_orig, __Pyx_memviewslice __pyx_v_pred, __Pyx_memviewslice __pyx_v_predecessors, __Pyx_memviewslice __pyx_v_conn, __Pyx_memviewslice __pyx_v_connectors, __Pyx_memviewslice __pyx_v_all_nodes, __Pyx_memviewslice __pyx_v_origins_to_write, __Pyx_memviewslice __pyx_v_nodes_to_write, CYTHON_UNUSED int __pyx_skip_dispatch) {
PY_LONG_LONG __pyx_v_i;
PY_LONG_LONG __pyx_v_k;
/* … */
/* function exit code */
}
/* Python wrapper */
static PyObject *__pyx_pw_3AoN_5put_path_file_on_disk(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static char __pyx_doc_3AoN_4put_path_file_on_disk[] = "put_path_file_on_disk(unsigned int orig, unsigned int[:] pred, long long[:] predecessors, unsigned int[:] conn, long long[:] connectors, long long[:] all_nodes, unsigned int[:] origins_to_write, unsigned int[:] nodes_to_write) -> void";
static PyObject *__pyx_pw_3AoN_5put_path_file_on_disk(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
unsigned int __pyx_v_orig;
__Pyx_memviewslice __pyx_v_pred = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_predecessors = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_conn = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_connectors = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_all_nodes = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_origins_to_write = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_nodes_to_write = { 0, 0, { 0 }, { 0 }, { 0 } };
PyObject *__pyx_r = 0;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("put_path_file_on_disk (wrapper)", 0);
{
static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_orig,&__pyx_n_s_pred,&__pyx_n_s_predecessors,&__pyx_n_s_conn,&__pyx_n_s_connectors,&__pyx_n_s_all_nodes,&__pyx_n_s_origins_to_write,&__pyx_n_s_nodes_to_write,0};
PyObject* values[8] = {0,0,0,0,0,0,0,0};
if (unlikely(__pyx_kwds)) {
Py_ssize_t kw_args;
const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
switch (pos_args) {
case 8: values[7] = PyTuple_GET_ITEM(__pyx_args, 7);
CYTHON_FALLTHROUGH;
case 7: values[6] = PyTuple_GET_ITEM(__pyx_args, 6);
CYTHON_FALLTHROUGH;
case 6: values[5] = PyTuple_GET_ITEM(__pyx_args, 5);
CYTHON_FALLTHROUGH;
case 5: values[4] = PyTuple_GET_ITEM(__pyx_args, 4);
CYTHON_FALLTHROUGH;
case 4: values[3] = PyTuple_GET_ITEM(__pyx_args, 3);
CYTHON_FALLTHROUGH;
case 3: values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
CYTHON_FALLTHROUGH;
case 2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
CYTHON_FALLTHROUGH;
case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
CYTHON_FALLTHROUGH;
case 0: break;
default: goto __pyx_L5_argtuple_error;
}
kw_args = PyDict_Size(__pyx_kwds);
switch (pos_args) {
case 0:
if (likely((values[0] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_orig)) != 0)) kw_args--;
else goto __pyx_L5_argtuple_error;
CYTHON_FALLTHROUGH;
case 1:
if (likely((values[1] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_pred)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("put_path_file_on_disk", 1, 8, 8, 1); __PYX_ERR(0, 130, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 2:
if (likely((values[2] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_predecessors)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("put_path_file_on_disk", 1, 8, 8, 2); __PYX_ERR(0, 130, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 3:
if (likely((values[3] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_conn)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("put_path_file_on_disk", 1, 8, 8, 3); __PYX_ERR(0, 130, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 4:
if (likely((values[4] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_connectors)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("put_path_file_on_disk", 1, 8, 8, 4); __PYX_ERR(0, 130, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 5:
if (likely((values[5] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_all_nodes)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("put_path_file_on_disk", 1, 8, 8, 5); __PYX_ERR(0, 130, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 6:
if (likely((values[6] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_origins_to_write)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("put_path_file_on_disk", 1, 8, 8, 6); __PYX_ERR(0, 130, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 7:
if (likely((values[7] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_nodes_to_write)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("put_path_file_on_disk", 1, 8, 8, 7); __PYX_ERR(0, 130, __pyx_L3_error)
}
}
if (unlikely(kw_args > 0)) {
if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "put_path_file_on_disk") < 0)) __PYX_ERR(0, 130, __pyx_L3_error)
}
} else if (PyTuple_GET_SIZE(__pyx_args) != 8) {
goto __pyx_L5_argtuple_error;
} else {
values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
values[3] = PyTuple_GET_ITEM(__pyx_args, 3);
values[4] = PyTuple_GET_ITEM(__pyx_args, 4);
values[5] = PyTuple_GET_ITEM(__pyx_args, 5);
values[6] = PyTuple_GET_ITEM(__pyx_args, 6);
values[7] = PyTuple_GET_ITEM(__pyx_args, 7);
}
__pyx_v_orig = __Pyx_PyInt_As_unsigned_int(values[0]); if (unlikely((__pyx_v_orig == (unsigned int)-1) && PyErr_Occurred())) __PYX_ERR(0, 130, __pyx_L3_error)
__pyx_v_pred = __Pyx_PyObject_to_MemoryviewSlice_ds_unsigned_int(values[1], PyBUF_WRITABLE); if (unlikely(!__pyx_v_pred.memview)) __PYX_ERR(0, 131, __pyx_L3_error)
__pyx_v_predecessors = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[2], PyBUF_WRITABLE); if (unlikely(!__pyx_v_predecessors.memview)) __PYX_ERR(0, 132, __pyx_L3_error)
__pyx_v_conn = __Pyx_PyObject_to_MemoryviewSlice_ds_unsigned_int(values[3], PyBUF_WRITABLE); if (unlikely(!__pyx_v_conn.memview)) __PYX_ERR(0, 133, __pyx_L3_error)
__pyx_v_connectors = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[4], PyBUF_WRITABLE); if (unlikely(!__pyx_v_connectors.memview)) __PYX_ERR(0, 134, __pyx_L3_error)
__pyx_v_all_nodes = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[5], PyBUF_WRITABLE); if (unlikely(!__pyx_v_all_nodes.memview)) __PYX_ERR(0, 135, __pyx_L3_error)
__pyx_v_origins_to_write = __Pyx_PyObject_to_MemoryviewSlice_ds_unsigned_int(values[6], PyBUF_WRITABLE); if (unlikely(!__pyx_v_origins_to_write.memview)) __PYX_ERR(0, 136, __pyx_L3_error)
__pyx_v_nodes_to_write = __Pyx_PyObject_to_MemoryviewSlice_ds_unsigned_int(values[7], PyBUF_WRITABLE); if (unlikely(!__pyx_v_nodes_to_write.memview)) __PYX_ERR(0, 137, __pyx_L3_error)
}
goto __pyx_L4_argument_unpacking_done;
__pyx_L5_argtuple_error:;
__Pyx_RaiseArgtupleInvalid("put_path_file_on_disk", 1, 8, 8, PyTuple_GET_SIZE(__pyx_args)); __PYX_ERR(0, 130, __pyx_L3_error)
__pyx_L3_error:;
__Pyx_AddTraceback("AoN.put_path_file_on_disk", __pyx_clineno, __pyx_lineno, __pyx_filename);
__Pyx_RefNannyFinishContext();
return NULL;
__pyx_L4_argument_unpacking_done:;
__pyx_r = __pyx_pf_3AoN_4put_path_file_on_disk(__pyx_self, __pyx_v_orig, __pyx_v_pred, __pyx_v_predecessors, __pyx_v_conn, __pyx_v_connectors, __pyx_v_all_nodes, __pyx_v_origins_to_write, __pyx_v_nodes_to_write);
/* function exit code */
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
static PyObject *__pyx_pf_3AoN_4put_path_file_on_disk(CYTHON_UNUSED PyObject *__pyx_self, unsigned int __pyx_v_orig, __Pyx_memviewslice __pyx_v_pred, __Pyx_memviewslice __pyx_v_predecessors, __Pyx_memviewslice __pyx_v_conn, __Pyx_memviewslice __pyx_v_connectors, __Pyx_memviewslice __pyx_v_all_nodes, __Pyx_memviewslice __pyx_v_origins_to_write, __Pyx_memviewslice __pyx_v_nodes_to_write) {
PyObject *__pyx_r = NULL;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("put_path_file_on_disk", 0);
__Pyx_XDECREF(__pyx_r);
if (unlikely(!__pyx_v_pred.memview)) { __Pyx_RaiseUnboundLocalError("pred"); __PYX_ERR(0, 130, __pyx_L1_error) }
if (unlikely(!__pyx_v_predecessors.memview)) { __Pyx_RaiseUnboundLocalError("predecessors"); __PYX_ERR(0, 130, __pyx_L1_error) }
if (unlikely(!__pyx_v_conn.memview)) { __Pyx_RaiseUnboundLocalError("conn"); __PYX_ERR(0, 130, __pyx_L1_error) }
if (unlikely(!__pyx_v_connectors.memview)) { __Pyx_RaiseUnboundLocalError("connectors"); __PYX_ERR(0, 130, __pyx_L1_error) }
if (unlikely(!__pyx_v_all_nodes.memview)) { __Pyx_RaiseUnboundLocalError("all_nodes"); __PYX_ERR(0, 130, __pyx_L1_error) }
if (unlikely(!__pyx_v_origins_to_write.memview)) { __Pyx_RaiseUnboundLocalError("origins_to_write"); __PYX_ERR(0, 130, __pyx_L1_error) }
if (unlikely(!__pyx_v_nodes_to_write.memview)) { __Pyx_RaiseUnboundLocalError("nodes_to_write"); __PYX_ERR(0, 130, __pyx_L1_error) }
__pyx_t_1 = __Pyx_void_to_None(__pyx_f_3AoN_put_path_file_on_disk(__pyx_v_orig, __pyx_v_pred, __pyx_v_predecessors, __pyx_v_conn, __pyx_v_connectors, __pyx_v_all_nodes, __pyx_v_origins_to_write, __pyx_v_nodes_to_write, 0)); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 130, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_1);
__pyx_r = __pyx_t_1;
__pyx_t_1 = 0;
goto __pyx_L0;
/* function exit code */
__pyx_L1_error:;
__Pyx_XDECREF(__pyx_t_1);
__Pyx_AddTraceback("AoN.put_path_file_on_disk", __pyx_clineno, __pyx_lineno, __pyx_filename);
__pyx_r = NULL;
__pyx_L0:;
__PYX_XDEC_MEMVIEW(&__pyx_v_pred, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_predecessors, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_conn, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_connectors, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_all_nodes, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_origins_to_write, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_nodes_to_write, 1);
__Pyx_XGIVEREF(__pyx_r);
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
131: unsigned int [:] pred,
132: long long [:] predecessors,
133: unsigned int [:] conn,
134: long long [:] connectors,
135: long long [:] all_nodes,
136: unsigned int [:] origins_to_write,
137: unsigned int [:] nodes_to_write) nogil:
138: cdef long long i
+139: cdef long long k = pred.shape[0]
__pyx_v_k = (__pyx_v_pred.shape[0]);
140:
+141: for i in range(k):
__pyx_t_1 = __pyx_v_k;
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_i = __pyx_t_3;
+142: origins_to_write[i] = orig
__pyx_t_4 = __pyx_v_i;
*((unsigned int *) ( /* dim=0 */ (__pyx_v_origins_to_write.data + __pyx_t_4 * __pyx_v_origins_to_write.strides[0]) )) = __pyx_v_orig;
+143: nodes_to_write[i] = all_nodes[i]
__pyx_t_5 = __pyx_v_i;
__pyx_t_6 = __pyx_v_i;
*((unsigned int *) ( /* dim=0 */ (__pyx_v_nodes_to_write.data + __pyx_t_6 * __pyx_v_nodes_to_write.strides[0]) )) = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_all_nodes.data + __pyx_t_5 * __pyx_v_all_nodes.strides[0]) )));
+144: pred[i] = all_nodes[predecessors[i]]
__pyx_t_7 = __pyx_v_i;
__pyx_t_8 = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_predecessors.data + __pyx_t_7 * __pyx_v_predecessors.strides[0]) )));
__pyx_t_9 = __pyx_v_i;
*((unsigned int *) ( /* dim=0 */ (__pyx_v_pred.data + __pyx_t_9 * __pyx_v_pred.strides[0]) )) = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_all_nodes.data + __pyx_t_8 * __pyx_v_all_nodes.strides[0]) )));
+145: conn[i] = connectors[i]
__pyx_t_10 = __pyx_v_i;
__pyx_t_11 = __pyx_v_i;
*((unsigned int *) ( /* dim=0 */ (__pyx_v_conn.data + __pyx_t_11 * __pyx_v_conn.strides[0]) )) = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_connectors.data + __pyx_t_10 * __pyx_v_connectors.strides[0]) )));
}
146:
147:
148: @cython.wraparound(False)
149: @cython.embedsignature(True)
150: @cython.boundscheck(False)
+151: cdef void blocking_centroid_flows(int action,
static void __pyx_f_3AoN_blocking_centroid_flows(int __pyx_v_action, PY_LONG_LONG __pyx_v_orig, __Pyx_memviewslice __pyx_v_fs, __Pyx_memviewslice __pyx_v_temp_b_nodes, __Pyx_memviewslice __pyx_v_real_b_nodes) {
PY_LONG_LONG __pyx_v_i;
/* … */
/* function exit code */
}
152: long long orig,
153: long long [:] fs,
154: long long [:] temp_b_nodes,
155: long long [:] real_b_nodes) nogil:
156: cdef long long i
157:
+158: if action == 0: # We are unblocking
__pyx_t_1 = ((__pyx_v_action == 0) != 0);
if (__pyx_t_1) {
/* … */
goto __pyx_L3;
}
+159: for i in range(fs[orig], fs[orig + 1]):
__pyx_t_2 = (__pyx_v_orig + 1);
__pyx_t_3 = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_fs.data + __pyx_t_2 * __pyx_v_fs.strides[0]) )));
__pyx_t_4 = __pyx_v_orig;
__pyx_t_5 = __pyx_t_3;
for (__pyx_t_6 = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_fs.data + __pyx_t_4 * __pyx_v_fs.strides[0]) ))); __pyx_t_6 < __pyx_t_5; __pyx_t_6+=1) {
__pyx_v_i = __pyx_t_6;
+160: temp_b_nodes[i] = real_b_nodes[i]
__pyx_t_7 = __pyx_v_i;
__pyx_t_8 = __pyx_v_i;
*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_temp_b_nodes.data + __pyx_t_8 * __pyx_v_temp_b_nodes.strides[0]) )) = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_real_b_nodes.data + __pyx_t_7 * __pyx_v_real_b_nodes.strides[0]) )));
}
161: else: # We are blocking:
+162: for i in range(fs[orig], fs[orig + 1]):
/*else*/ {
__pyx_t_3 = (__pyx_v_orig + 1);
__pyx_t_5 = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_fs.data + __pyx_t_3 * __pyx_v_fs.strides[0]) )));
__pyx_t_6 = __pyx_v_orig;
__pyx_t_9 = __pyx_t_5;
for (__pyx_t_10 = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_fs.data + __pyx_t_6 * __pyx_v_fs.strides[0]) ))); __pyx_t_10 < __pyx_t_9; __pyx_t_10+=1) {
__pyx_v_i = __pyx_t_10;
+163: temp_b_nodes[i] = orig
__pyx_t_11 = __pyx_v_i;
*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_temp_b_nodes.data + __pyx_t_11 * __pyx_v_temp_b_nodes.strides[0]) )) = __pyx_v_orig;
}
}
__pyx_L3:;
164:
165:
166: @cython.wraparound(False)
167: @cython.embedsignature(True)
168: @cython.boundscheck(False) # turn of bounds-checking for entire function
+169: cdef void skim_single_path(long origin,
static void __pyx_f_3AoN_skim_single_path(long __pyx_v_origin, long __pyx_v_nodes, long __pyx_v_skims, __Pyx_memviewslice __pyx_v_node_skims, __Pyx_memviewslice __pyx_v_pred, __Pyx_memviewslice __pyx_v_conn, __Pyx_memviewslice __pyx_v_graph_costs, __Pyx_memviewslice __pyx_v_reached_first, long __pyx_v_found) {
PY_LONG_LONG __pyx_v_i;
PY_LONG_LONG __pyx_v_node;
PY_LONG_LONG __pyx_v_predecessor;
PY_LONG_LONG __pyx_v_connector;
PY_LONG_LONG __pyx_v_j;
/* … */
/* function exit code */
}
170: long nodes,
171: long skims,
172: double[:, :] node_skims,
173: long long [:] pred,
174: long long [:] conn,
175: double[:, :] graph_costs,
176: long long [:] reached_first,
177: long found) nogil:
178: cdef long long i, node, predecessor, connector, j
179:
180: # sets all skims to infinity
+181: for i in range(nodes):
__pyx_t_1 = __pyx_v_nodes;
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_i = __pyx_t_3;
+182: for j in range(skims):
__pyx_t_4 = __pyx_v_skims;
__pyx_t_5 = __pyx_t_4;
for (__pyx_t_6 = 0; __pyx_t_6 < __pyx_t_5; __pyx_t_6+=1) {
__pyx_v_j = __pyx_t_6;
+183: node_skims[i, j] = INFINITE
__pyx_t_7 = __pyx_v_i;
__pyx_t_8 = __pyx_v_j;
*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_skims.data + __pyx_t_7 * __pyx_v_node_skims.strides[0]) ) + __pyx_t_8 * __pyx_v_node_skims.strides[1]) )) = __pyx_v_3AoN_INFINITE;
}
}
184:
185: # Zeroes the intrazonal cost
+186: for j in range(skims):
__pyx_t_1 = __pyx_v_skims;
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_j = __pyx_t_3;
+187: node_skims[origin, j] = 0
__pyx_t_9 = __pyx_v_origin;
__pyx_t_6 = __pyx_v_j;
*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_skims.data + __pyx_t_9 * __pyx_v_node_skims.strides[0]) ) + __pyx_t_6 * __pyx_v_node_skims.strides[1]) )) = 0.0;
}
188:
189: # Cascade skimming
+190: for i in range(1, found + 1):
__pyx_t_1 = (__pyx_v_found + 1);
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 1; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_i = __pyx_t_3;
+191: node = reached_first[i]
__pyx_t_10 = __pyx_v_i;
__pyx_v_node = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_reached_first.data + __pyx_t_10 * __pyx_v_reached_first.strides[0]) )));
192:
193: # captures how we got to that node
+194: predecessor = pred[node]
__pyx_t_11 = __pyx_v_node;
__pyx_v_predecessor = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_pred.data + __pyx_t_11 * __pyx_v_pred.strides[0]) )));
+195: connector = conn[node]
__pyx_t_12 = __pyx_v_node;
__pyx_v_connector = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_conn.data + __pyx_t_12 * __pyx_v_conn.strides[0]) )));
196:
+197: for j in range(skims):
__pyx_t_4 = __pyx_v_skims;
__pyx_t_5 = __pyx_t_4;
for (__pyx_t_13 = 0; __pyx_t_13 < __pyx_t_5; __pyx_t_13+=1) {
__pyx_v_j = __pyx_t_13;
+198: node_skims[node, j] = node_skims[predecessor, j] + graph_costs[connector, j]
__pyx_t_14 = __pyx_v_predecessor;
__pyx_t_15 = __pyx_v_j;
__pyx_t_16 = __pyx_v_connector;
__pyx_t_17 = __pyx_v_j;
__pyx_t_18 = __pyx_v_node;
__pyx_t_19 = __pyx_v_j;
*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_skims.data + __pyx_t_18 * __pyx_v_node_skims.strides[0]) ) + __pyx_t_19 * __pyx_v_node_skims.strides[1]) )) = ((*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_skims.data + __pyx_t_14 * __pyx_v_node_skims.strides[0]) ) + __pyx_t_15 * __pyx_v_node_skims.strides[1]) ))) + (*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_graph_costs.data + __pyx_t_16 * __pyx_v_graph_costs.strides[0]) ) + __pyx_t_17 * __pyx_v_graph_costs.strides[1]) ))));
}
}
199:
200:
201: @cython.wraparound(False)
202: @cython.embedsignature(True)
203: @cython.boundscheck(False) # turn of bounds-checking for entire function
+204: cpdef void skim_multiple_fields(long origin,
static PyObject *__pyx_pw_3AoN_7skim_multiple_fields(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static void __pyx_f_3AoN_skim_multiple_fields(long __pyx_v_origin, long __pyx_v_nodes, long __pyx_v_zones, long __pyx_v_skims, __Pyx_memviewslice __pyx_v_node_skims, __Pyx_memviewslice __pyx_v_pred, __Pyx_memviewslice __pyx_v_conn, __Pyx_memviewslice __pyx_v_graph_costs, __Pyx_memviewslice __pyx_v_reached_first, long __pyx_v_found, __Pyx_memviewslice __pyx_v_final_skims, CYTHON_UNUSED int __pyx_skip_dispatch) {
PY_LONG_LONG __pyx_v_i;
PY_LONG_LONG __pyx_v_node;
PY_LONG_LONG __pyx_v_predecessor;
PY_LONG_LONG __pyx_v_connector;
PY_LONG_LONG __pyx_v_j;
/* … */
/* function exit code */
}
/* Python wrapper */
static PyObject *__pyx_pw_3AoN_7skim_multiple_fields(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static char __pyx_doc_3AoN_6skim_multiple_fields[] = "skim_multiple_fields(long origin, long nodes, long zones, long skims, double[:, :] node_skims, long long[:] pred, long long[:] conn, double[:, :] graph_costs, long long[:] reached_first, long found, double[:, :] final_skims) -> void";
static PyObject *__pyx_pw_3AoN_7skim_multiple_fields(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
long __pyx_v_origin;
long __pyx_v_nodes;
long __pyx_v_zones;
long __pyx_v_skims;
__Pyx_memviewslice __pyx_v_node_skims = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_pred = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_conn = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_graph_costs = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_reached_first = { 0, 0, { 0 }, { 0 }, { 0 } };
long __pyx_v_found;
__Pyx_memviewslice __pyx_v_final_skims = { 0, 0, { 0 }, { 0 }, { 0 } };
PyObject *__pyx_r = 0;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("skim_multiple_fields (wrapper)", 0);
{
static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_origin,&__pyx_n_s_nodes,&__pyx_n_s_zones,&__pyx_n_s_skims,&__pyx_n_s_node_skims,&__pyx_n_s_pred,&__pyx_n_s_conn,&__pyx_n_s_graph_costs,&__pyx_n_s_reached_first,&__pyx_n_s_found,&__pyx_n_s_final_skims,0};
PyObject* values[11] = {0,0,0,0,0,0,0,0,0,0,0};
if (unlikely(__pyx_kwds)) {
Py_ssize_t kw_args;
const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
switch (pos_args) {
case 11: values[10] = PyTuple_GET_ITEM(__pyx_args, 10);
CYTHON_FALLTHROUGH;
case 10: values[9] = PyTuple_GET_ITEM(__pyx_args, 9);
CYTHON_FALLTHROUGH;
case 9: values[8] = PyTuple_GET_ITEM(__pyx_args, 8);
CYTHON_FALLTHROUGH;
case 8: values[7] = PyTuple_GET_ITEM(__pyx_args, 7);
CYTHON_FALLTHROUGH;
case 7: values[6] = PyTuple_GET_ITEM(__pyx_args, 6);
CYTHON_FALLTHROUGH;
case 6: values[5] = PyTuple_GET_ITEM(__pyx_args, 5);
CYTHON_FALLTHROUGH;
case 5: values[4] = PyTuple_GET_ITEM(__pyx_args, 4);
CYTHON_FALLTHROUGH;
case 4: values[3] = PyTuple_GET_ITEM(__pyx_args, 3);
CYTHON_FALLTHROUGH;
case 3: values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
CYTHON_FALLTHROUGH;
case 2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
CYTHON_FALLTHROUGH;
case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
CYTHON_FALLTHROUGH;
case 0: break;
default: goto __pyx_L5_argtuple_error;
}
kw_args = PyDict_Size(__pyx_kwds);
switch (pos_args) {
case 0:
if (likely((values[0] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_origin)) != 0)) kw_args--;
else goto __pyx_L5_argtuple_error;
CYTHON_FALLTHROUGH;
case 1:
if (likely((values[1] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_nodes)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("skim_multiple_fields", 1, 11, 11, 1); __PYX_ERR(0, 204, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 2:
if (likely((values[2] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_zones)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("skim_multiple_fields", 1, 11, 11, 2); __PYX_ERR(0, 204, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 3:
if (likely((values[3] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_skims)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("skim_multiple_fields", 1, 11, 11, 3); __PYX_ERR(0, 204, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 4:
if (likely((values[4] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_node_skims)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("skim_multiple_fields", 1, 11, 11, 4); __PYX_ERR(0, 204, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 5:
if (likely((values[5] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_pred)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("skim_multiple_fields", 1, 11, 11, 5); __PYX_ERR(0, 204, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 6:
if (likely((values[6] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_conn)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("skim_multiple_fields", 1, 11, 11, 6); __PYX_ERR(0, 204, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 7:
if (likely((values[7] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_graph_costs)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("skim_multiple_fields", 1, 11, 11, 7); __PYX_ERR(0, 204, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 8:
if (likely((values[8] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_reached_first)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("skim_multiple_fields", 1, 11, 11, 8); __PYX_ERR(0, 204, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 9:
if (likely((values[9] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_found)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("skim_multiple_fields", 1, 11, 11, 9); __PYX_ERR(0, 204, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 10:
if (likely((values[10] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_final_skims)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("skim_multiple_fields", 1, 11, 11, 10); __PYX_ERR(0, 204, __pyx_L3_error)
}
}
if (unlikely(kw_args > 0)) {
if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "skim_multiple_fields") < 0)) __PYX_ERR(0, 204, __pyx_L3_error)
}
} else if (PyTuple_GET_SIZE(__pyx_args) != 11) {
goto __pyx_L5_argtuple_error;
} else {
values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
values[3] = PyTuple_GET_ITEM(__pyx_args, 3);
values[4] = PyTuple_GET_ITEM(__pyx_args, 4);
values[5] = PyTuple_GET_ITEM(__pyx_args, 5);
values[6] = PyTuple_GET_ITEM(__pyx_args, 6);
values[7] = PyTuple_GET_ITEM(__pyx_args, 7);
values[8] = PyTuple_GET_ITEM(__pyx_args, 8);
values[9] = PyTuple_GET_ITEM(__pyx_args, 9);
values[10] = PyTuple_GET_ITEM(__pyx_args, 10);
}
__pyx_v_origin = __Pyx_PyInt_As_long(values[0]); if (unlikely((__pyx_v_origin == (long)-1) && PyErr_Occurred())) __PYX_ERR(0, 204, __pyx_L3_error)
__pyx_v_nodes = __Pyx_PyInt_As_long(values[1]); if (unlikely((__pyx_v_nodes == (long)-1) && PyErr_Occurred())) __PYX_ERR(0, 205, __pyx_L3_error)
__pyx_v_zones = __Pyx_PyInt_As_long(values[2]); if (unlikely((__pyx_v_zones == (long)-1) && PyErr_Occurred())) __PYX_ERR(0, 206, __pyx_L3_error)
__pyx_v_skims = __Pyx_PyInt_As_long(values[3]); if (unlikely((__pyx_v_skims == (long)-1) && PyErr_Occurred())) __PYX_ERR(0, 207, __pyx_L3_error)
__pyx_v_node_skims = __Pyx_PyObject_to_MemoryviewSlice_dsds_double(values[4], PyBUF_WRITABLE); if (unlikely(!__pyx_v_node_skims.memview)) __PYX_ERR(0, 208, __pyx_L3_error)
__pyx_v_pred = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[5], PyBUF_WRITABLE); if (unlikely(!__pyx_v_pred.memview)) __PYX_ERR(0, 209, __pyx_L3_error)
__pyx_v_conn = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[6], PyBUF_WRITABLE); if (unlikely(!__pyx_v_conn.memview)) __PYX_ERR(0, 210, __pyx_L3_error)
__pyx_v_graph_costs = __Pyx_PyObject_to_MemoryviewSlice_dsds_double(values[7], PyBUF_WRITABLE); if (unlikely(!__pyx_v_graph_costs.memview)) __PYX_ERR(0, 211, __pyx_L3_error)
__pyx_v_reached_first = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[8], PyBUF_WRITABLE); if (unlikely(!__pyx_v_reached_first.memview)) __PYX_ERR(0, 212, __pyx_L3_error)
__pyx_v_found = __Pyx_PyInt_As_long(values[9]); if (unlikely((__pyx_v_found == (long)-1) && PyErr_Occurred())) __PYX_ERR(0, 213, __pyx_L3_error)
__pyx_v_final_skims = __Pyx_PyObject_to_MemoryviewSlice_dsds_double(values[10], PyBUF_WRITABLE); if (unlikely(!__pyx_v_final_skims.memview)) __PYX_ERR(0, 214, __pyx_L3_error)
}
goto __pyx_L4_argument_unpacking_done;
__pyx_L5_argtuple_error:;
__Pyx_RaiseArgtupleInvalid("skim_multiple_fields", 1, 11, 11, PyTuple_GET_SIZE(__pyx_args)); __PYX_ERR(0, 204, __pyx_L3_error)
__pyx_L3_error:;
__Pyx_AddTraceback("AoN.skim_multiple_fields", __pyx_clineno, __pyx_lineno, __pyx_filename);
__Pyx_RefNannyFinishContext();
return NULL;
__pyx_L4_argument_unpacking_done:;
__pyx_r = __pyx_pf_3AoN_6skim_multiple_fields(__pyx_self, __pyx_v_origin, __pyx_v_nodes, __pyx_v_zones, __pyx_v_skims, __pyx_v_node_skims, __pyx_v_pred, __pyx_v_conn, __pyx_v_graph_costs, __pyx_v_reached_first, __pyx_v_found, __pyx_v_final_skims);
/* function exit code */
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
static PyObject *__pyx_pf_3AoN_6skim_multiple_fields(CYTHON_UNUSED PyObject *__pyx_self, long __pyx_v_origin, long __pyx_v_nodes, long __pyx_v_zones, long __pyx_v_skims, __Pyx_memviewslice __pyx_v_node_skims, __Pyx_memviewslice __pyx_v_pred, __Pyx_memviewslice __pyx_v_conn, __Pyx_memviewslice __pyx_v_graph_costs, __Pyx_memviewslice __pyx_v_reached_first, long __pyx_v_found, __Pyx_memviewslice __pyx_v_final_skims) {
PyObject *__pyx_r = NULL;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("skim_multiple_fields", 0);
__Pyx_XDECREF(__pyx_r);
if (unlikely(!__pyx_v_node_skims.memview)) { __Pyx_RaiseUnboundLocalError("node_skims"); __PYX_ERR(0, 204, __pyx_L1_error) }
if (unlikely(!__pyx_v_pred.memview)) { __Pyx_RaiseUnboundLocalError("pred"); __PYX_ERR(0, 204, __pyx_L1_error) }
if (unlikely(!__pyx_v_conn.memview)) { __Pyx_RaiseUnboundLocalError("conn"); __PYX_ERR(0, 204, __pyx_L1_error) }
if (unlikely(!__pyx_v_graph_costs.memview)) { __Pyx_RaiseUnboundLocalError("graph_costs"); __PYX_ERR(0, 204, __pyx_L1_error) }
if (unlikely(!__pyx_v_reached_first.memview)) { __Pyx_RaiseUnboundLocalError("reached_first"); __PYX_ERR(0, 204, __pyx_L1_error) }
if (unlikely(!__pyx_v_final_skims.memview)) { __Pyx_RaiseUnboundLocalError("final_skims"); __PYX_ERR(0, 204, __pyx_L1_error) }
__pyx_t_1 = __Pyx_void_to_None(__pyx_f_3AoN_skim_multiple_fields(__pyx_v_origin, __pyx_v_nodes, __pyx_v_zones, __pyx_v_skims, __pyx_v_node_skims, __pyx_v_pred, __pyx_v_conn, __pyx_v_graph_costs, __pyx_v_reached_first, __pyx_v_found, __pyx_v_final_skims, 0)); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 204, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_1);
__pyx_r = __pyx_t_1;
__pyx_t_1 = 0;
goto __pyx_L0;
/* function exit code */
__pyx_L1_error:;
__Pyx_XDECREF(__pyx_t_1);
__Pyx_AddTraceback("AoN.skim_multiple_fields", __pyx_clineno, __pyx_lineno, __pyx_filename);
__pyx_r = NULL;
__pyx_L0:;
__PYX_XDEC_MEMVIEW(&__pyx_v_node_skims, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_pred, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_conn, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_graph_costs, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_reached_first, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_final_skims, 1);
__Pyx_XGIVEREF(__pyx_r);
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
205: long nodes,
206: long zones,
207: long skims,
208: double[:, :] node_skims,
209: long long [:] pred,
210: long long [:] conn,
211: double[:, :] graph_costs,
212: long long [:] reached_first,
213: long found,
214: double [:,:] final_skims) nogil:
215: cdef long long i, node, predecessor, connector, j
216:
217: # sets all skims to infinity
+218: for i in range(nodes):
__pyx_t_1 = __pyx_v_nodes;
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_i = __pyx_t_3;
+219: for j in range(skims):
__pyx_t_4 = __pyx_v_skims;
__pyx_t_5 = __pyx_t_4;
for (__pyx_t_6 = 0; __pyx_t_6 < __pyx_t_5; __pyx_t_6+=1) {
__pyx_v_j = __pyx_t_6;
+220: node_skims[i, j] = INFINITE
__pyx_t_7 = __pyx_v_i;
__pyx_t_8 = __pyx_v_j;
*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_skims.data + __pyx_t_7 * __pyx_v_node_skims.strides[0]) ) + __pyx_t_8 * __pyx_v_node_skims.strides[1]) )) = __pyx_v_3AoN_INFINITE;
}
}
221:
222: # Zeroes the intrazonal cost
+223: for j in range(skims):
__pyx_t_1 = __pyx_v_skims;
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_j = __pyx_t_3;
+224: node_skims[origin, j] = 0
__pyx_t_9 = __pyx_v_origin;
__pyx_t_6 = __pyx_v_j;
*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_skims.data + __pyx_t_9 * __pyx_v_node_skims.strides[0]) ) + __pyx_t_6 * __pyx_v_node_skims.strides[1]) )) = 0.0;
}
225:
226: # Cascade skimming
+227: for i in range(1, found + 1):
__pyx_t_1 = (__pyx_v_found + 1);
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 1; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_i = __pyx_t_3;
+228: node = reached_first[i]
__pyx_t_10 = __pyx_v_i;
__pyx_v_node = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_reached_first.data + __pyx_t_10 * __pyx_v_reached_first.strides[0]) )));
229:
230: # captures how we got to that node
+231: predecessor = pred[node]
__pyx_t_11 = __pyx_v_node;
__pyx_v_predecessor = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_pred.data + __pyx_t_11 * __pyx_v_pred.strides[0]) )));
+232: connector = conn[node]
__pyx_t_12 = __pyx_v_node;
__pyx_v_connector = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_conn.data + __pyx_t_12 * __pyx_v_conn.strides[0]) )));
233:
+234: for j in range(skims):
__pyx_t_4 = __pyx_v_skims;
__pyx_t_5 = __pyx_t_4;
for (__pyx_t_13 = 0; __pyx_t_13 < __pyx_t_5; __pyx_t_13+=1) {
__pyx_v_j = __pyx_t_13;
+235: node_skims[node, j] = node_skims[predecessor, j] + graph_costs[connector, j]
__pyx_t_14 = __pyx_v_predecessor;
__pyx_t_15 = __pyx_v_j;
__pyx_t_16 = __pyx_v_connector;
__pyx_t_17 = __pyx_v_j;
__pyx_t_18 = __pyx_v_node;
__pyx_t_19 = __pyx_v_j;
*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_skims.data + __pyx_t_18 * __pyx_v_node_skims.strides[0]) ) + __pyx_t_19 * __pyx_v_node_skims.strides[1]) )) = ((*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_skims.data + __pyx_t_14 * __pyx_v_node_skims.strides[0]) ) + __pyx_t_15 * __pyx_v_node_skims.strides[1]) ))) + (*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_graph_costs.data + __pyx_t_16 * __pyx_v_graph_costs.strides[0]) ) + __pyx_t_17 * __pyx_v_graph_costs.strides[1]) ))));
}
}
236:
+237: for i in range(zones):
__pyx_t_1 = __pyx_v_zones;
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_i = __pyx_t_3;
+238: for j in range(skims):
__pyx_t_4 = __pyx_v_skims;
__pyx_t_5 = __pyx_t_4;
for (__pyx_t_13 = 0; __pyx_t_13 < __pyx_t_5; __pyx_t_13+=1) {
__pyx_v_j = __pyx_t_13;
+239: final_skims[i, j] = node_skims[i, j]
__pyx_t_20 = __pyx_v_i;
__pyx_t_21 = __pyx_v_j;
__pyx_t_22 = __pyx_v_i;
__pyx_t_23 = __pyx_v_j;
*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_final_skims.data + __pyx_t_22 * __pyx_v_final_skims.strides[0]) ) + __pyx_t_23 * __pyx_v_final_skims.strides[1]) )) = (*((double *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_node_skims.data + __pyx_t_20 * __pyx_v_node_skims.strides[0]) ) + __pyx_t_21 * __pyx_v_node_skims.strides[1]) )));
}
}
240:
241:
242: # ###########################################################################################################################
243: #############################################################################################################################
244: #Original Dijkstra implementation by Jake Vanderplas, taken from SciPy V0.11
245: #The old Pyrex syntax for loops was replaced with Python syntax
246: #Old Numpy Buffers were replaces with latest memory views interface to allow for the release of the GIL
247: # Path tracking arrays and skim arrays were also added to it
248: #############################################################################################################################
249: # ###########################################################################################################################
250:
251: @cython.wraparound(False)
252: @cython.embedsignature(True)
253: @cython.boundscheck(False) # turn of bounds-checking for entire function
+254: cpdef int path_finding(long origin,
static PyObject *__pyx_pw_3AoN_9path_finding(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static int __pyx_f_3AoN_path_finding(long __pyx_v_origin, __Pyx_memviewslice __pyx_v_graph_costs, __Pyx_memviewslice __pyx_v_csr_indices, __Pyx_memviewslice __pyx_v_graph_fs, __Pyx_memviewslice __pyx_v_pred, __Pyx_memviewslice __pyx_v_ids, __Pyx_memviewslice __pyx_v_connectors, __Pyx_memviewslice __pyx_v_reached_first, CYTHON_UNUSED int __pyx_skip_dispatch) {
unsigned int __pyx_v_N;
unsigned int __pyx_v_M;
long __pyx_v_i;
long __pyx_v_k;
long __pyx_v_j_source;
long __pyx_v_j_current;
__pyx_t_3AoN_ITYPE_t __pyx_v_found;
long __pyx_v_j;
__pyx_t_3AoN_DTYPE_t __pyx_v_weight;
struct __pyx_t_3AoN_FibonacciHeap __pyx_v_heap;
struct __pyx_t_3AoN_FibonacciNode *__pyx_v_v;
struct __pyx_t_3AoN_FibonacciNode *__pyx_v_current_node;
struct __pyx_t_3AoN_FibonacciNode *__pyx_v_nodes;
int __pyx_r;
/* … */
/* function exit code */
__pyx_L0:;
return __pyx_r;
}
/* Python wrapper */
static PyObject *__pyx_pw_3AoN_9path_finding(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static char __pyx_doc_3AoN_8path_finding[] = "path_finding(long origin, double[:] graph_costs, long long[:] csr_indices, long long[:] graph_fs, long long[:] pred, long long[:] ids, long long[:] connectors, long long[:] reached_first) -> int";
static PyObject *__pyx_pw_3AoN_9path_finding(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
long __pyx_v_origin;
__Pyx_memviewslice __pyx_v_graph_costs = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_csr_indices = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_graph_fs = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_pred = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_ids = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_connectors = { 0, 0, { 0 }, { 0 }, { 0 } };
__Pyx_memviewslice __pyx_v_reached_first = { 0, 0, { 0 }, { 0 }, { 0 } };
PyObject *__pyx_r = 0;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("path_finding (wrapper)", 0);
{
static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_origin,&__pyx_n_s_graph_costs,&__pyx_n_s_csr_indices,&__pyx_n_s_graph_fs,&__pyx_n_s_pred,&__pyx_n_s_ids,&__pyx_n_s_connectors,&__pyx_n_s_reached_first,0};
PyObject* values[8] = {0,0,0,0,0,0,0,0};
if (unlikely(__pyx_kwds)) {
Py_ssize_t kw_args;
const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
switch (pos_args) {
case 8: values[7] = PyTuple_GET_ITEM(__pyx_args, 7);
CYTHON_FALLTHROUGH;
case 7: values[6] = PyTuple_GET_ITEM(__pyx_args, 6);
CYTHON_FALLTHROUGH;
case 6: values[5] = PyTuple_GET_ITEM(__pyx_args, 5);
CYTHON_FALLTHROUGH;
case 5: values[4] = PyTuple_GET_ITEM(__pyx_args, 4);
CYTHON_FALLTHROUGH;
case 4: values[3] = PyTuple_GET_ITEM(__pyx_args, 3);
CYTHON_FALLTHROUGH;
case 3: values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
CYTHON_FALLTHROUGH;
case 2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
CYTHON_FALLTHROUGH;
case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
CYTHON_FALLTHROUGH;
case 0: break;
default: goto __pyx_L5_argtuple_error;
}
kw_args = PyDict_Size(__pyx_kwds);
switch (pos_args) {
case 0:
if (likely((values[0] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_origin)) != 0)) kw_args--;
else goto __pyx_L5_argtuple_error;
CYTHON_FALLTHROUGH;
case 1:
if (likely((values[1] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_graph_costs)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("path_finding", 1, 8, 8, 1); __PYX_ERR(0, 254, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 2:
if (likely((values[2] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_csr_indices)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("path_finding", 1, 8, 8, 2); __PYX_ERR(0, 254, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 3:
if (likely((values[3] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_graph_fs)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("path_finding", 1, 8, 8, 3); __PYX_ERR(0, 254, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 4:
if (likely((values[4] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_pred)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("path_finding", 1, 8, 8, 4); __PYX_ERR(0, 254, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 5:
if (likely((values[5] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_ids)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("path_finding", 1, 8, 8, 5); __PYX_ERR(0, 254, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 6:
if (likely((values[6] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_connectors)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("path_finding", 1, 8, 8, 6); __PYX_ERR(0, 254, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 7:
if (likely((values[7] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_reached_first)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("path_finding", 1, 8, 8, 7); __PYX_ERR(0, 254, __pyx_L3_error)
}
}
if (unlikely(kw_args > 0)) {
if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "path_finding") < 0)) __PYX_ERR(0, 254, __pyx_L3_error)
}
} else if (PyTuple_GET_SIZE(__pyx_args) != 8) {
goto __pyx_L5_argtuple_error;
} else {
values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
values[3] = PyTuple_GET_ITEM(__pyx_args, 3);
values[4] = PyTuple_GET_ITEM(__pyx_args, 4);
values[5] = PyTuple_GET_ITEM(__pyx_args, 5);
values[6] = PyTuple_GET_ITEM(__pyx_args, 6);
values[7] = PyTuple_GET_ITEM(__pyx_args, 7);
}
__pyx_v_origin = __Pyx_PyInt_As_long(values[0]); if (unlikely((__pyx_v_origin == (long)-1) && PyErr_Occurred())) __PYX_ERR(0, 254, __pyx_L3_error)
__pyx_v_graph_costs = __Pyx_PyObject_to_MemoryviewSlice_ds_double(values[1], PyBUF_WRITABLE); if (unlikely(!__pyx_v_graph_costs.memview)) __PYX_ERR(0, 255, __pyx_L3_error)
__pyx_v_csr_indices = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[2], PyBUF_WRITABLE); if (unlikely(!__pyx_v_csr_indices.memview)) __PYX_ERR(0, 256, __pyx_L3_error)
__pyx_v_graph_fs = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[3], PyBUF_WRITABLE); if (unlikely(!__pyx_v_graph_fs.memview)) __PYX_ERR(0, 257, __pyx_L3_error)
__pyx_v_pred = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[4], PyBUF_WRITABLE); if (unlikely(!__pyx_v_pred.memview)) __PYX_ERR(0, 258, __pyx_L3_error)
__pyx_v_ids = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[5], PyBUF_WRITABLE); if (unlikely(!__pyx_v_ids.memview)) __PYX_ERR(0, 259, __pyx_L3_error)
__pyx_v_connectors = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[6], PyBUF_WRITABLE); if (unlikely(!__pyx_v_connectors.memview)) __PYX_ERR(0, 260, __pyx_L3_error)
__pyx_v_reached_first = __Pyx_PyObject_to_MemoryviewSlice_ds_PY_LONG_LONG(values[7], PyBUF_WRITABLE); if (unlikely(!__pyx_v_reached_first.memview)) __PYX_ERR(0, 261, __pyx_L3_error)
}
goto __pyx_L4_argument_unpacking_done;
__pyx_L5_argtuple_error:;
__Pyx_RaiseArgtupleInvalid("path_finding", 1, 8, 8, PyTuple_GET_SIZE(__pyx_args)); __PYX_ERR(0, 254, __pyx_L3_error)
__pyx_L3_error:;
__Pyx_AddTraceback("AoN.path_finding", __pyx_clineno, __pyx_lineno, __pyx_filename);
__Pyx_RefNannyFinishContext();
return NULL;
__pyx_L4_argument_unpacking_done:;
__pyx_r = __pyx_pf_3AoN_8path_finding(__pyx_self, __pyx_v_origin, __pyx_v_graph_costs, __pyx_v_csr_indices, __pyx_v_graph_fs, __pyx_v_pred, __pyx_v_ids, __pyx_v_connectors, __pyx_v_reached_first);
/* function exit code */
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
static PyObject *__pyx_pf_3AoN_8path_finding(CYTHON_UNUSED PyObject *__pyx_self, long __pyx_v_origin, __Pyx_memviewslice __pyx_v_graph_costs, __Pyx_memviewslice __pyx_v_csr_indices, __Pyx_memviewslice __pyx_v_graph_fs, __Pyx_memviewslice __pyx_v_pred, __Pyx_memviewslice __pyx_v_ids, __Pyx_memviewslice __pyx_v_connectors, __Pyx_memviewslice __pyx_v_reached_first) {
PyObject *__pyx_r = NULL;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("path_finding", 0);
__Pyx_XDECREF(__pyx_r);
if (unlikely(!__pyx_v_graph_costs.memview)) { __Pyx_RaiseUnboundLocalError("graph_costs"); __PYX_ERR(0, 254, __pyx_L1_error) }
if (unlikely(!__pyx_v_csr_indices.memview)) { __Pyx_RaiseUnboundLocalError("csr_indices"); __PYX_ERR(0, 254, __pyx_L1_error) }
if (unlikely(!__pyx_v_graph_fs.memview)) { __Pyx_RaiseUnboundLocalError("graph_fs"); __PYX_ERR(0, 254, __pyx_L1_error) }
if (unlikely(!__pyx_v_pred.memview)) { __Pyx_RaiseUnboundLocalError("pred"); __PYX_ERR(0, 254, __pyx_L1_error) }
if (unlikely(!__pyx_v_ids.memview)) { __Pyx_RaiseUnboundLocalError("ids"); __PYX_ERR(0, 254, __pyx_L1_error) }
if (unlikely(!__pyx_v_connectors.memview)) { __Pyx_RaiseUnboundLocalError("connectors"); __PYX_ERR(0, 254, __pyx_L1_error) }
if (unlikely(!__pyx_v_reached_first.memview)) { __Pyx_RaiseUnboundLocalError("reached_first"); __PYX_ERR(0, 254, __pyx_L1_error) }
__pyx_t_1 = __Pyx_PyInt_From_int(__pyx_f_3AoN_path_finding(__pyx_v_origin, __pyx_v_graph_costs, __pyx_v_csr_indices, __pyx_v_graph_fs, __pyx_v_pred, __pyx_v_ids, __pyx_v_connectors, __pyx_v_reached_first, 0)); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 254, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_1);
__pyx_r = __pyx_t_1;
__pyx_t_1 = 0;
goto __pyx_L0;
/* function exit code */
__pyx_L1_error:;
__Pyx_XDECREF(__pyx_t_1);
__Pyx_AddTraceback("AoN.path_finding", __pyx_clineno, __pyx_lineno, __pyx_filename);
__pyx_r = NULL;
__pyx_L0:;
__PYX_XDEC_MEMVIEW(&__pyx_v_graph_costs, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_csr_indices, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_graph_fs, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_pred, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_ids, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_connectors, 1);
__PYX_XDEC_MEMVIEW(&__pyx_v_reached_first, 1);
__Pyx_XGIVEREF(__pyx_r);
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
255: double[:] graph_costs,
256: long long [:] csr_indices,
257: long long [:] graph_fs,
258: long long [:] pred,
259: long long [:] ids,
260: long long [:] connectors,
261: long long [:] reached_first) nogil:
262:
+263: cdef unsigned int N = graph_costs.shape[0]
__pyx_v_N = (__pyx_v_graph_costs.shape[0]);
+264: cdef unsigned int M = pred.shape[0]
__pyx_v_M = (__pyx_v_pred.shape[0]);
265:
266: cdef long i, k, j_source, j_current
+267: cdef ITYPE_t found = 0
__pyx_v_found = 0;
268: cdef long j
269: cdef DTYPE_t weight
270:
271: cdef FibonacciHeap heap
272: cdef FibonacciNode *v
273: cdef FibonacciNode *current_node
+274: cdef FibonacciNode *nodes = <FibonacciNode*> malloc(N * sizeof(FibonacciNode))
__pyx_v_nodes = ((struct __pyx_t_3AoN_FibonacciNode *)malloc((__pyx_v_N * (sizeof(struct __pyx_t_3AoN_FibonacciNode)))));
275:
+276: for i in range(M):
__pyx_t_1 = __pyx_v_M;
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_i = __pyx_t_3;
+277: pred[i] = -1
__pyx_t_4 = __pyx_v_i;
*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_pred.data + __pyx_t_4 * __pyx_v_pred.strides[0]) )) = -1LL;
+278: connectors[i] = -1
__pyx_t_5 = __pyx_v_i;
*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_connectors.data + __pyx_t_5 * __pyx_v_connectors.strides[0]) )) = -1LL;
}
279:
+280: j_source = origin
__pyx_v_j_source = __pyx_v_origin;
+281: for k in range(N):
__pyx_t_1 = __pyx_v_N;
__pyx_t_2 = __pyx_t_1;
for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
__pyx_v_k = __pyx_t_3;
+282: initialize_node(&nodes[k], k)
__pyx_f_3AoN_initialize_node((&(__pyx_v_nodes[__pyx_v_k])), __pyx_v_k, NULL); }
283:
+284: heap.min_node = NULL
__pyx_v_heap.min_node = NULL;
+285: insert_node(&heap, &nodes[j_source])
__pyx_f_3AoN_insert_node((&__pyx_v_heap), (&(__pyx_v_nodes[__pyx_v_j_source])));
286:
+287: while heap.min_node:
while (1) {
__pyx_t_6 = (__pyx_v_heap.min_node != 0);
if (!__pyx_t_6) break;
+288: v = remove_min(&heap)
__pyx_v_v = __pyx_f_3AoN_remove_min((&__pyx_v_heap));
+289: reached_first[found] = v.index
__pyx_t_7 = __pyx_v_v->index;
__pyx_t_8 = __pyx_v_found;
*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_reached_first.data + __pyx_t_8 * __pyx_v_reached_first.strides[0]) )) = __pyx_t_7;
+290: found += 1
__pyx_v_found = (__pyx_v_found + 1);
+291: v.state = 1
__pyx_v_v->state = 1;
292:
+293: for j in range(graph_fs[v.index],graph_fs[v.index + 1]):
__pyx_t_7 = (__pyx_v_v->index + 1);
__pyx_t_9 = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_graph_fs.data + __pyx_t_7 * __pyx_v_graph_fs.strides[0]) )));
__pyx_t_10 = __pyx_v_v->index;
__pyx_t_11 = __pyx_t_9;
for (__pyx_t_3 = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_graph_fs.data + __pyx_t_10 * __pyx_v_graph_fs.strides[0]) ))); __pyx_t_3 < __pyx_t_11; __pyx_t_3+=1) {
__pyx_v_j = __pyx_t_3;
+294: j_current = csr_indices[j]
__pyx_t_12 = __pyx_v_j;
__pyx_v_j_current = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_csr_indices.data + __pyx_t_12 * __pyx_v_csr_indices.strides[0]) )));
+295: current_node = &nodes[j_current]
__pyx_v_current_node = (&(__pyx_v_nodes[__pyx_v_j_current]));
296:
+297: if current_node.state != 1:
__pyx_t_6 = ((__pyx_v_current_node->state != 1) != 0);
if (__pyx_t_6) {
/* … */
}
}
}
+298: weight = graph_costs[j]
__pyx_t_13 = __pyx_v_j;
__pyx_v_weight = (*((double *) ( /* dim=0 */ (__pyx_v_graph_costs.data + __pyx_t_13 * __pyx_v_graph_costs.strides[0]) )));
+299: if current_node.state == 2:
__pyx_t_6 = ((__pyx_v_current_node->state == 2) != 0);
if (__pyx_t_6) {
/* … */
goto __pyx_L12;
}
+300: current_node.state = 3
__pyx_v_current_node->state = 3;
+301: current_node.val = v.val + weight
__pyx_v_current_node->val = (__pyx_v_v->val + __pyx_v_weight);
+302: insert_node(&heap, current_node)
__pyx_f_3AoN_insert_node((&__pyx_v_heap), __pyx_v_current_node);
+303: pred[j_current] = v.index
__pyx_t_14 = __pyx_v_v->index;
__pyx_t_15 = __pyx_v_j_current;
*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_pred.data + __pyx_t_15 * __pyx_v_pred.strides[0]) )) = __pyx_t_14;
+304: connectors[j_current] = ids[j]
__pyx_t_16 = __pyx_v_j;
__pyx_t_17 = __pyx_v_j_current;
*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_connectors.data + __pyx_t_17 * __pyx_v_connectors.strides[0]) )) = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_ids.data + __pyx_t_16 * __pyx_v_ids.strides[0]) )));
305:
+306: elif current_node.val > v.val + weight:
__pyx_t_6 = ((__pyx_v_current_node->val > (__pyx_v_v->val + __pyx_v_weight)) != 0);
if (__pyx_t_6) {
/* … */
}
__pyx_L12:;
+307: decrease_val(&heap, current_node, v.val + weight)
__pyx_f_3AoN_decrease_val((&__pyx_v_heap), __pyx_v_current_node, (__pyx_v_v->val + __pyx_v_weight));
+308: pred[j_current] = v.index
__pyx_t_14 = __pyx_v_v->index;
__pyx_t_18 = __pyx_v_j_current;
*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_pred.data + __pyx_t_18 * __pyx_v_pred.strides[0]) )) = __pyx_t_14;
309: #The link that took us to such node
+310: connectors[j_current] = ids[j]
__pyx_t_19 = __pyx_v_j;
__pyx_t_20 = __pyx_v_j_current;
*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_connectors.data + __pyx_t_20 * __pyx_v_connectors.strides[0]) )) = (*((PY_LONG_LONG *) ( /* dim=0 */ (__pyx_v_ids.data + __pyx_t_19 * __pyx_v_ids.strides[0]) )));
311:
+312: free(nodes)
free(__pyx_v_nodes);
+313: return found -1
__pyx_r = (__pyx_v_found - 1); goto __pyx_L0;
314:
315: ######################################################################
316: # FibonacciNode structure
317: # This structure and the operations on it are the nodes of the
318: # Fibonacci heap.
319:
320: #cdef enum FibonacciState:
321: # SCANNED=1
322: # NOT_IN_HEAP=2
323: # IN_HEAP=3
324:
+325: cdef struct FibonacciNode:
struct __pyx_t_3AoN_FibonacciNode {
__pyx_t_3AoN_ITYPE_t index;
unsigned int rank;
unsigned int state;
__pyx_t_3AoN_DTYPE_t val;
struct __pyx_t_3AoN_FibonacciNode *parent;
struct __pyx_t_3AoN_FibonacciNode *left_sibling;
struct __pyx_t_3AoN_FibonacciNode *right_sibling;
struct __pyx_t_3AoN_FibonacciNode *children;
};
326: ITYPE_t index
327: unsigned int rank
328: #FibonacciState state
329: unsigned int state
330: DTYPE_t val
331: FibonacciNode* parent
332: FibonacciNode* left_sibling
333: FibonacciNode* right_sibling
334: FibonacciNode* children
335:
+336: cdef void initialize_node(FibonacciNode* node,
static void __pyx_f_3AoN_initialize_node(struct __pyx_t_3AoN_FibonacciNode *__pyx_v_node, unsigned int __pyx_v_index, struct __pyx_opt_args_3AoN_initialize_node *__pyx_optional_args) {
double __pyx_v_val = ((double)0.0);
if (__pyx_optional_args) {
if (__pyx_optional_args->__pyx_n > 0) {
__pyx_v_val = __pyx_optional_args->val;
}
}
/* … */
/* function exit code */
}
/* … */
struct __pyx_opt_args_3AoN_initialize_node {
int __pyx_n;
double val;
};
337: unsigned int index,
338: double val=0) nogil:
339: # Assumptions: - node is a valid pointer
340: # - node is not currently part of a heap
+341: node.index = index
__pyx_v_node->index = __pyx_v_index;
+342: node.val = val
__pyx_v_node->val = __pyx_v_val;
+343: node.rank = 0
__pyx_v_node->rank = 0;
+344: node.state = 2
__pyx_v_node->state = 2;
+345: node.parent = NULL
__pyx_v_node->parent = NULL;
+346: node.left_sibling = NULL
__pyx_v_node->left_sibling = NULL;
+347: node.right_sibling = NULL
__pyx_v_node->right_sibling = NULL;
+348: node.children = NULL
__pyx_v_node->children = NULL;
349:
+350: cdef FibonacciNode* rightmost_sibling(FibonacciNode* node) nogil:
static struct __pyx_t_3AoN_FibonacciNode *__pyx_f_3AoN_rightmost_sibling(struct __pyx_t_3AoN_FibonacciNode *__pyx_v_node) {
struct __pyx_t_3AoN_FibonacciNode *__pyx_v_temp;
struct __pyx_t_3AoN_FibonacciNode *__pyx_r;
/* … */
/* function exit code */
__pyx_L0:;
return __pyx_r;
}
351: # Assumptions: - node is a valid pointer
+352: cdef FibonacciNode* temp = node
__pyx_v_temp = __pyx_v_node;
+353: while(temp.right_sibling):
while (1) {
__pyx_t_1 = (__pyx_v_temp->right_sibling != 0);
if (!__pyx_t_1) break;
+354: temp = temp.right_sibling
__pyx_t_2 = __pyx_v_temp->right_sibling;
__pyx_v_temp = __pyx_t_2;
}
+355: return temp
__pyx_r = __pyx_v_temp; goto __pyx_L0;
356:
+357: cdef FibonacciNode* leftmost_sibling(FibonacciNode* node) nogil:
static struct __pyx_t_3AoN_FibonacciNode *__pyx_f_3AoN_leftmost_sibling(struct __pyx_t_3AoN_FibonacciNode *__pyx_v_node) {
struct __pyx_t_3AoN_FibonacciNode *__pyx_v_temp;
struct __pyx_t_3AoN_FibonacciNode *__pyx_r;
/* … */
/* function exit code */
__pyx_L0:;
return __pyx_r;
}
358: # Assumptions: - node is a valid pointer
+359: cdef FibonacciNode* temp = node
__pyx_v_temp = __pyx_v_node;
+360: while(temp.left_sibling):
while (1) {
__pyx_t_1 = (__pyx_v_temp->left_sibling != 0);
if (!__pyx_t_1) break;
+361: temp = temp.left_sibling
__pyx_t_2 = __pyx_v_temp->left_sibling;
__pyx_v_temp = __pyx_t_2;
}
+362: return temp
__pyx_r = __pyx_v_temp; goto __pyx_L0;
363:
+364: cdef void add_child(FibonacciNode* node, FibonacciNode* new_child) nogil:
static void __pyx_f_3AoN_add_child(struct __pyx_t_3AoN_FibonacciNode *__pyx_v_node, struct __pyx_t_3AoN_FibonacciNode *__pyx_v_new_child) {
/* … */
/* function exit code */
}
365: # Assumptions: - node is a valid pointer
366: # - new_child is a valid pointer
367: # - new_child is not the sibling or child of another node
+368: new_child.parent = node
__pyx_v_new_child->parent = __pyx_v_node;
369:
+370: if node.children:
__pyx_t_1 = (__pyx_v_node->children != 0);
if (__pyx_t_1) {
/* … */
goto __pyx_L3;
}
+371: add_sibling(node.children, new_child)
__pyx_f_3AoN_add_sibling(__pyx_v_node->children, __pyx_v_new_child);
372: else:
+373: node.children = new_child
/*else*/ {
__pyx_v_node->children = __pyx_v_new_child;
+374: new_child.right_sibling = NULL
__pyx_v_new_child->right_sibling = NULL;
+375: new_child.left_sibling = NULL
__pyx_v_new_child->left_sibling = NULL;
+376: node.rank = 1
__pyx_v_node->rank = 1; } __pyx_L3:;
377:
+378: cdef void add_sibling(FibonacciNode* node, FibonacciNode* new_sibling) nogil:
static void __pyx_f_3AoN_add_sibling(struct __pyx_t_3AoN_FibonacciNode *__pyx_v_node, struct __pyx_t_3AoN_FibonacciNode *__pyx_v_new_sibling) {
struct __pyx_t_3AoN_FibonacciNode *__pyx_v_temp;
/* … */
/* function exit code */
}
379: # Assumptions: - node is a valid pointer
380: # - new_sibling is a valid pointer
381: # - new_sibling is not the child or sibling of another node
+382: cdef FibonacciNode* temp = rightmost_sibling(node)
__pyx_v_temp = __pyx_f_3AoN_rightmost_sibling(__pyx_v_node);
+383: temp.right_sibling = new_sibling
__pyx_v_temp->right_sibling = __pyx_v_new_sibling;
+384: new_sibling.left_sibling = temp
__pyx_v_new_sibling->left_sibling = __pyx_v_temp;
+385: new_sibling.right_sibling = NULL
__pyx_v_new_sibling->right_sibling = NULL;
+386: new_sibling.parent = node.parent
__pyx_t_1 = __pyx_v_node->parent; __pyx_v_new_sibling->parent = __pyx_t_1;
+387: if new_sibling.parent:
__pyx_t_2 = (__pyx_v_new_sibling->parent != 0);
if (__pyx_t_2) {
/* … */
}
+388: new_sibling.parent.rank += 1
__pyx_v_new_sibling->parent->rank = (__pyx_v_new_sibling->parent->rank + 1);
389:
+390: cdef void remove(FibonacciNode* node) nogil:
static void __pyx_f_3AoN_remove(struct __pyx_t_3AoN_FibonacciNode *__pyx_v_node) {
/* … */
/* function exit code */
}
391: # Assumptions: - node is a valid pointer
+392: if node.parent:
__pyx_t_1 = (__pyx_v_node->parent != 0);
if (__pyx_t_1) {
/* … */
}
+393: node.parent.rank -= 1
__pyx_v_node->parent->rank = (__pyx_v_node->parent->rank - 1);
+394: if node.left_sibling:
__pyx_t_1 = (__pyx_v_node->left_sibling != 0);
if (__pyx_t_1) {
/* … */
goto __pyx_L4;
}
+395: node.parent.children = node.left_sibling
__pyx_t_2 = __pyx_v_node->left_sibling;
__pyx_v_node->parent->children = __pyx_t_2;
+396: elif node.right_sibling:
__pyx_t_1 = (__pyx_v_node->right_sibling != 0);
if (__pyx_t_1) {
/* … */
goto __pyx_L4;
}
+397: node.parent.children = node.right_sibling
__pyx_t_2 = __pyx_v_node->right_sibling;
__pyx_v_node->parent->children = __pyx_t_2;
398: else:
+399: node.parent.children = NULL
/*else*/ {
__pyx_v_node->parent->children = NULL;
}
__pyx_L4:;
400:
+401: if node.left_sibling:
__pyx_t_1 = (__pyx_v_node->left_sibling != 0);
if (__pyx_t_1) {
/* … */
}
+402: node.left_sibling.right_sibling = node.right_sibling
__pyx_t_2 = __pyx_v_node->right_sibling;
__pyx_v_node->left_sibling->right_sibling = __pyx_t_2;
+403: if node.right_sibling:
__pyx_t_1 = (__pyx_v_node->right_sibling != 0);
if (__pyx_t_1) {
/* … */
}
+404: node.right_sibling.left_sibling = node.left_sibling
__pyx_t_2 = __pyx_v_node->left_sibling;
__pyx_v_node->right_sibling->left_sibling = __pyx_t_2;
405:
+406: node.left_sibling = NULL
__pyx_v_node->left_sibling = NULL;
+407: node.right_sibling = NULL
__pyx_v_node->right_sibling = NULL;
+408: node.parent = NULL
__pyx_v_node->parent = NULL;
409:
410:
411: ######################################################################
412: # FibonacciHeap structure
413: # This structure and operations on it use the FibonacciNode
414: # routines to implement a Fibonacci heap
415:
+416: ctypedef FibonacciNode* pFibonacciNode
typedef struct __pyx_t_3AoN_FibonacciNode *__pyx_t_3AoN_pFibonacciNode;
417:
+418: cdef struct FibonacciHeap:
struct __pyx_t_3AoN_FibonacciHeap {
struct __pyx_t_3AoN_FibonacciNode *min_node;
__pyx_t_3AoN_pFibonacciNode roots_by_rank[0x64];
};
419: FibonacciNode* min_node
420: pFibonacciNode[100] roots_by_rank # maximum number of nodes is ~2^100.
421:
+422: cdef void insert_node(FibonacciHeap* heap,
static void __pyx_f_3AoN_insert_node(struct __pyx_t_3AoN_FibonacciHeap *__pyx_v_heap, struct __pyx_t_3AoN_FibonacciNode *__pyx_v_node) {
/* … */
/* function exit code */
}
423: FibonacciNode* node) nogil:
424: # Assumptions: - heap is a valid pointer
425: # - node is a valid pointer
426: # - node is not the child or sibling of another node
+427: if heap.min_node:
__pyx_t_1 = (__pyx_v_heap->min_node != 0);
if (__pyx_t_1) {
/* … */
goto __pyx_L3;
}
+428: add_sibling(heap.min_node, node)
__pyx_f_3AoN_add_sibling(__pyx_v_heap->min_node, __pyx_v_node);
+429: if node.val < heap.min_node.val:
__pyx_t_1 = ((__pyx_v_node->val < __pyx_v_heap->min_node->val) != 0);
if (__pyx_t_1) {
/* … */
}
+430: heap.min_node = node
__pyx_v_heap->min_node = __pyx_v_node;
431: else:
+432: heap.min_node = node
/*else*/ {
__pyx_v_heap->min_node = __pyx_v_node;
}
__pyx_L3:;
433:
+434: cdef void decrease_val(FibonacciHeap* heap,
static void __pyx_f_3AoN_decrease_val(struct __pyx_t_3AoN_FibonacciHeap *__pyx_v_heap, struct __pyx_t_3AoN_FibonacciNode *__pyx_v_node, __pyx_t_3AoN_DTYPE_t __pyx_v_newval) {
/* … */
/* function exit code */
}
435: FibonacciNode* node,
436: DTYPE_t newval) nogil:
437: # Assumptions: - heap is a valid pointer
438: # - newval <= node.val
439: # - node is a valid pointer
440: # - node is not the child or sibling of another node
441: # - node is in the heap
+442: node.val = newval
__pyx_v_node->val = __pyx_v_newval;
+443: if node.parent and (node.parent.val >= newval):
__pyx_t_2 = (__pyx_v_node->parent != 0);
if (__pyx_t_2) {
} else {
__pyx_t_1 = __pyx_t_2;
goto __pyx_L4_bool_binop_done;
}
__pyx_t_2 = ((__pyx_v_node->parent->val >= __pyx_v_newval) != 0);
__pyx_t_1 = __pyx_t_2;
__pyx_L4_bool_binop_done:;
if (__pyx_t_1) {
/* … */
goto __pyx_L3;
}
+444: remove(node)
__pyx_f_3AoN_remove(__pyx_v_node);
+445: insert_node(heap, node)
__pyx_f_3AoN_insert_node(__pyx_v_heap, __pyx_v_node);
+446: elif heap.min_node.val > node.val:
__pyx_t_1 = ((__pyx_v_heap->min_node->val > __pyx_v_node->val) != 0);
if (__pyx_t_1) {
/* … */
}
__pyx_L3:;
+447: heap.min_node = node
__pyx_v_heap->min_node = __pyx_v_node;
448:
+449: cdef void link(FibonacciHeap* heap, FibonacciNode* node) nogil:
static void __pyx_f_3AoN_link(struct __pyx_t_3AoN_FibonacciHeap *__pyx_v_heap, struct __pyx_t_3AoN_FibonacciNode *__pyx_v_node) {
struct __pyx_t_3AoN_FibonacciNode *__pyx_v_linknode;
/* … */
/* function exit code */
}
450: # Assumptions: - heap is a valid pointer
451: # - node is a valid pointer
452: # - node is already within heap
453:
454: cdef FibonacciNode *linknode
455: cdef FibonacciNode *parent
456: cdef FibonacciNode *child
457:
+458: if heap.roots_by_rank[node.rank] == NULL:
__pyx_t_1 = (((__pyx_v_heap->roots_by_rank[__pyx_v_node->rank]) == NULL) != 0);
if (__pyx_t_1) {
/* … */
goto __pyx_L3;
}
+459: heap.roots_by_rank[node.rank] = node
(__pyx_v_heap->roots_by_rank[__pyx_v_node->rank]) = __pyx_v_node;
460: else:
+461: linknode = heap.roots_by_rank[node.rank]
/*else*/ {
__pyx_v_linknode = (__pyx_v_heap->roots_by_rank[__pyx_v_node->rank]);
+462: heap.roots_by_rank[node.rank] = NULL
(__pyx_v_heap->roots_by_rank[__pyx_v_node->rank]) = NULL;
463:
+464: if node.val < linknode.val or node == heap.min_node:
__pyx_t_2 = ((__pyx_v_node->val < __pyx_v_linknode->val) != 0);
if (!__pyx_t_2) {
} else {
__pyx_t_1 = __pyx_t_2;
goto __pyx_L5_bool_binop_done;
}
__pyx_t_2 = ((__pyx_v_node == __pyx_v_heap->min_node) != 0);
__pyx_t_1 = __pyx_t_2;
__pyx_L5_bool_binop_done:;
if (__pyx_t_1) {
/* … */
goto __pyx_L4;
}
+465: remove(linknode)
__pyx_f_3AoN_remove(__pyx_v_linknode);
+466: add_child(node, linknode)
__pyx_f_3AoN_add_child(__pyx_v_node, __pyx_v_linknode);
+467: link(heap, node)
__pyx_f_3AoN_link(__pyx_v_heap, __pyx_v_node);
468: else:
+469: remove(node)
/*else*/ {
__pyx_f_3AoN_remove(__pyx_v_node);
+470: add_child(linknode, node)
__pyx_f_3AoN_add_child(__pyx_v_linknode, __pyx_v_node);
+471: link(heap, linknode)
__pyx_f_3AoN_link(__pyx_v_heap, __pyx_v_linknode);
}
__pyx_L4:;
}
__pyx_L3:;
472:
473: @cython.wraparound(False)
474: @cython.embedsignature(True)
475: @cython.boundscheck(False) # turn of bounds-checking for entire function
+476: cdef FibonacciNode* remove_min(FibonacciHeap* heap) nogil:
static struct __pyx_t_3AoN_FibonacciNode *__pyx_f_3AoN_remove_min(struct __pyx_t_3AoN_FibonacciHeap *__pyx_v_heap) {
struct __pyx_t_3AoN_FibonacciNode *__pyx_v_temp;
struct __pyx_t_3AoN_FibonacciNode *__pyx_v_temp_right;
struct __pyx_t_3AoN_FibonacciNode *__pyx_v_out;
unsigned int __pyx_v_i;
struct __pyx_t_3AoN_FibonacciNode *__pyx_r;
/* … */
/* function exit code */
__pyx_L0:;
return __pyx_r;
}
477: # Assumptions: - heap is a valid pointer
478: # - heap.min_node is a valid pointer
479: cdef FibonacciNode *temp
480: cdef FibonacciNode *temp_right
481: cdef FibonacciNode *out
482: cdef unsigned int i
483:
484: # make all min_node children into root nodes
+485: if heap.min_node.children:
__pyx_t_1 = (__pyx_v_heap->min_node->children != 0);
if (__pyx_t_1) {
/* … */
}
+486: temp = leftmost_sibling(heap.min_node.children)
__pyx_v_temp = __pyx_f_3AoN_leftmost_sibling(__pyx_v_heap->min_node->children);
+487: temp_right = NULL
__pyx_v_temp_right = NULL;
488:
+489: while temp:
while (1) {
__pyx_t_1 = (__pyx_v_temp != 0);
if (!__pyx_t_1) break;
+490: temp_right = temp.right_sibling
__pyx_t_2 = __pyx_v_temp->right_sibling;
__pyx_v_temp_right = __pyx_t_2;
+491: remove(temp)
__pyx_f_3AoN_remove(__pyx_v_temp);
+492: add_sibling(heap.min_node, temp)
__pyx_f_3AoN_add_sibling(__pyx_v_heap->min_node, __pyx_v_temp);
+493: temp = temp_right
__pyx_v_temp = __pyx_v_temp_right;
}
494:
+495: heap.min_node.children = NULL
__pyx_v_heap->min_node->children = NULL;
496:
497: # choose a root node other than min_node
+498: temp = leftmost_sibling(heap.min_node)
__pyx_v_temp = __pyx_f_3AoN_leftmost_sibling(__pyx_v_heap->min_node);
+499: if temp == heap.min_node:
__pyx_t_1 = ((__pyx_v_temp == __pyx_v_heap->min_node) != 0);
if (__pyx_t_1) {
/* … */
}
+500: if heap.min_node.right_sibling:
__pyx_t_1 = (__pyx_v_heap->min_node->right_sibling != 0);
if (__pyx_t_1) {
/* … */
goto __pyx_L7;
}
+501: temp = heap.min_node.right_sibling
__pyx_t_2 = __pyx_v_heap->min_node->right_sibling;
__pyx_v_temp = __pyx_t_2;
502: else:
+503: out = heap.min_node
/*else*/ {
__pyx_t_2 = __pyx_v_heap->min_node;
__pyx_v_out = __pyx_t_2;
+504: heap.min_node = NULL
__pyx_v_heap->min_node = NULL;
+505: return out
__pyx_r = __pyx_v_out;
goto __pyx_L0;
}
__pyx_L7:;
506:
507: # remove min_node, and point heap to the new min
+508: out = heap.min_node
__pyx_t_2 = __pyx_v_heap->min_node; __pyx_v_out = __pyx_t_2;
+509: remove(heap.min_node)
__pyx_f_3AoN_remove(__pyx_v_heap->min_node);
+510: heap.min_node = temp
__pyx_v_heap->min_node = __pyx_v_temp;
511:
512: # re-link the heap
+513: for i in range(100):
for (__pyx_t_3 = 0; __pyx_t_3 < 0x64; __pyx_t_3+=1) {
__pyx_v_i = __pyx_t_3;
+514: heap.roots_by_rank[i] = NULL
(__pyx_v_heap->roots_by_rank[__pyx_v_i]) = NULL; }
515:
+516: while temp:
while (1) {
__pyx_t_1 = (__pyx_v_temp != 0);
if (!__pyx_t_1) break;
+517: if temp.val < heap.min_node.val:
__pyx_t_1 = ((__pyx_v_temp->val < __pyx_v_heap->min_node->val) != 0);
if (__pyx_t_1) {
/* … */
}
+518: heap.min_node = temp
__pyx_v_heap->min_node = __pyx_v_temp;
+519: temp_right = temp.right_sibling
__pyx_t_2 = __pyx_v_temp->right_sibling;
__pyx_v_temp_right = __pyx_t_2;
+520: link(heap, temp)
__pyx_f_3AoN_link(__pyx_v_heap, __pyx_v_temp);
+521: temp = temp_right
__pyx_v_temp = __pyx_v_temp_right; }
522:
+523: return out
__pyx_r = __pyx_v_out; goto __pyx_L0;