Python Implementation#

Main module.

kleinberg_grid_simulator.python_implementation.python_edt.python_edt(n=1000, r=2, p=1, q=1, n_runs=10000, numba=True, parallel=False)[source]#

Python-based computation of the expected delivery time (edt).

Parameters:

n (int, default=1000) – Grid siDe
r (float, default=2.0) – Shortcut exponent
p (int, default=1) – Local range
q (int, default=1) – Number of shortcuts
n_runs (int, default=10000) – Number of routes to compute
numba (bool, default=True) – Use JiT compilation
parallel (bool, default=False) – Parallelize runs. Use for single, lengthy computation. Coarse-grained (high-level) parallelisation is preferred.

Returns:

The expected number of steps to go from one point of the grid to another point of the grid.

Return type:

Result

kleinberg_grid_simulator.python_implementation.greedy_walk.edt_gen(gen, n, p, q, n_runs)[source]#

Core computation of Expected Delivery Time (edt).

Parameters:

gen (callable) – Function that draws relative shortcuts
n (int) – Grid siDe
p (int) – Local range
q (int) – Number of shortcuts
n_runs (int) – Number of routes to compute

Returns:

Expected Delivery Time

Return type:

float

kleinberg_grid_simulator.python_implementation.shortcuts.draw_1_lt_r_lt_2(n, r)[source]#

Parameters:

n (int) – grid size
r (float) – Shortcut exponent (1<r<2)

Returns:

A shortcut generator

Return type:

callable

Examples

>>> set_seeds()
>>> gen = draw_1_lt_r_lt_2(100, 1.5)
>>> gen()
(-78, -103)
>>> gen = draw_1_lt_r_lt_2(1000000000, 1.8)
>>> gen()
(123799, 141186)

kleinberg_grid_simulator.python_implementation.shortcuts.draw_2_lt_r(n, r)[source]#

Parameters:

n (int) – grid size
r (float) – Shortcut exponent (>2)

Returns:

A shortcut generator

Return type:

callable

Examples

>>> set_seeds()
>>> gen = draw_2_lt_r(100, 2.5)
>>> gen()
(29, -45)
>>> gen = draw_2_lt_r(10000000, 2.8)
>>> gen()
(2, 0)
>>> gen = draw_2_lt_r(100000, 2.2)
>>> gen()
(0, -1)
>>> gen()
(-39, -15)

kleinberg_grid_simulator.python_implementation.shortcuts.draw_r_eq_1(n)[source]#

Parameters:: n (int) – grid size
Returns:: A shortcut generator
Return type:: callable

Examples

>>> set_seeds()
>>> gen = draw_r_eq_1(100)
>>> gen()
(0, -103)
>>> gen = draw_r_eq_1(1000000000)
>>> gen()
(677037233, 596605187)

kleinberg_grid_simulator.python_implementation.shortcuts.draw_r_eq_2(n)[source]#

Parameters:: n (int) – grid size
Returns:: A shortcut generator
Return type:: callable

Examples

>>> set_seeds()
>>> gen = draw_r_eq_2(100)
>>> gen()
(-50, -103)
>>> gen = draw_r_eq_2(1000000000)
>>> gen()
(23, -6)

kleinberg_grid_simulator.python_implementation.shortcuts.draw_r_lt_1(n, r)[source]#

Parameters:

n (int) – grid size
r (float) – Shortcut exponent (<1)

Returns:

A shortcut generator

Return type:

callable

Examples

>>> set_seeds()
>>> gen = draw_r_lt_1(100, .5)
>>> gen()
(0, -103)
>>> gen = draw_r_lt_1(1000000000, .8)
>>> gen()
(1482484865, 59640099)

kleinberg_grid_simulator.python_implementation.shortcuts.radius2shortcut(radius)[source]#

Parameters:

radius (int) – Radius to draw shortcut from.

Returns:

x (int) – x relative coordinate
y (int) – y relative coordinate

Examples

>>> set_seeds()
>>> radius2shortcut(10)
(-9, 1)
>>> radius2shortcut(2**40)
(772882432861, -326629194915)

kleinberg_grid_simulator.python_implementation.seed.set_seeds(seed=42, numba_seed=None)[source]#

Parameters:

seed (int, optional) – Numpy seed
numba_seed (int, optional) – Numba seed

Return type:

None