Dijkstra functions

From ObjectVision

(Difference between revisions)
Jump to: navigation, search
(interaction)
 
(16 intermediate revisions not shown)
Line 1: Line 1:
-
  This page reflects the dijkstra functions of GeoDMS 7.115.
+
  This page reflects the dijkstra functions of GeoDMS 7.212.
-
  See [[GeoDms Setups]] for installing 7.115.
+
  See [[GeoDms Setups]] for installing GeoDMS 7.212 or later.
-
The dijkstra functions:
+
''[[Network functions]] dijkstra functions''
-
* determine the minimum impedance of the routes through a network of nodes and links with given link-impedance
+
-
* for each combination of given origins and destinations.
+
-
The user can filter the set of origin destination combinations (further: od-pairs) in two ways:
+
== '''Functions''' ==
-
* by setting a maximum impedance (per origin) and/or
+
-
* a maximum amount of visited destination mass per origin.
+
-
 
+
-
Furthermore, the user can specify the production of additional results per origin, destination, link, or od-pair such as:
+
-
* the specification of an an alternative link impedance measure, to be aggregated over the found routes.
+
-
* interaction results: trip generation, distribution, and network flow assignment, following Alonso's Theory of Movements.
+
-
Origin and destination zones can be specified as a set of startPoints or endPoints that relate to the network nodes with an optional additional Impedance per startPoint and/or endPoint.
+
-
 
+
-
When no od-pair related output is requested, the memory usage remains proportional to the memory size of the given network and calculation time remains proportional to the number of actually visited nodes (plus some initialization time proportional to the size of the network).
+
-
 
+
-
=Entities=
+
-
Key entities of the arguments and results of these functions are:
+
-
; Node: a set of abstract locations, connected by links.
+
-
; Link: a set of connections between nodes identified by two mappings, \(f_1: \text{Link}\rightarrow\text{Node}\), and \(f_2: \text{Link}\rightarrow\text{Node}\) indicating the start and end node for each link.
+
-
; OrgZone: a set of origins
+
-
; DstZone: a set of destinations
+
-
; startPoint: a set of combinations of origins and nodes (thus allowing multiple nodes per origin and multiple origins per node).
+
-
; endPoint: a set of combinations of destinations and nodes (thus allowing multiple nodes per destination and multiple destinations per node).
+
-
 
+
-
Depending on the given arguments, it may well be that these entities are not distinctive, for example: OrgZone may be equal to DstZone.
+
-
 
+
-
Relevant value-units are:
+
-
; Impedance: a non-negative numerical expression of travel resistance for which comparison and addition make sense.
+
-
; Impedance2: a non-negative numerical expression of an alternative travel resistance for which addition make sense. If no alternative impedance is given, Impedance2 is set equal to Impedance.
+
-
; Mass: a non-negative numerical expression of OrgZone related demand or DstZone related supply
+
-
 
+
-
=Functions=
+
There are only three preferred dijkstra operations:  
There are only three preferred dijkstra operations:  
*'''dijkstra_s(...)''': when all given startPoints have to be considered as a '''s'''ingle origin zone, resulting in:
*'''dijkstra_s(...)''': when all given startPoints have to be considered as a '''s'''ingle origin zone, resulting in:
Line 49: Line 20:
* \( \text{f2}: \text{Link} \rightarrow \text{Node} \), a '''Node''' attribute of '''Link''' indicating the to node of each link.
* \( \text{f2}: \text{Link} \rightarrow \text{Node} \), a '''Node''' attribute of '''Link''' indicating the to node of each link.
-
=options specification=
+
Note that dijkstra can run different OrgZones in parallel, up to the number of cores of the running machine, as their tree growing is independent. This does not affect dijkstra_s, as that only grows one tree.
-
The options parameter indicates how to calculate routes, which additional arguments are given and which results are to be produced. Each section is separated by a ';', starts with a label and indicates comma separated extra arguments between '(' and ')'. Optional results are specified by name after a ':'. All sections, extra arguments and products must be specified in the order of the following description. All labels and names are case-sensitive and no intermediate spaces are allowed.
+
-
 
+
-
==link direction==
+
-
The first section is obligatory and indicates the allowed traversal direction of each link. It can be
+
-
* '''directed''': only routes from a startPoint to an endPoint that traverses each link forward from node \(\text{f1}\) to node \(\text{f2}\) are considered and not vice versa.
+
-
* '''bidirectional''': also backward traversal is considered through each link, from node \(\text{f2}\) to node \(\text{f1}\).
+
-
* '''bidirectional(link_flag)''': indicates an additional argument \(\text{Link}\rightarrow\text{Bool}\), a boolean attribute of \(\text{Link}\), that indicates for each link if it is to be considered as bidirectional. False indicates forward traversal only.
+
-
 
+
-
==startPoints==
+
-
The optional '''startPoint(Node_rel, impedance, OrgZone_rel):max_imp''' specifies a set of origin zones.
+
-
* the '''Node_rel''', optional for '''dijkstra_m''', indicates the presence of an additional argument: \(\text{startPoint}\rightarrow\text{Node}\), a Node attribute of startPoint in order to select a subset of nodes as startPoints. Required for the '''dijkstra_s''' function. Default: when omitted with the '''dijkstra_m''' function, all Nodes are considered as startPoints and '''startPoint''' := '''Node'''.
+
-
* the optional '''impedance''' indicates the presence of an additional argument: \(\text{startPoint}\rightarrow\text{Impedance}\), as departure impedance attribute of startPoint, useful mainly when origin zones contain multiple startPoints with specific departure impedances. Default value when omitted: zero.
+
-
* the '''OrgZone_rel''', optional for '''dijkstra_m''' and not allowed for '''dijkstra_s''', indicates the presence of an additional argument: \(\text{startPoint}\rightarrow\text{OrgZone}\), an origin zone attribute of startPoint, in order to define multiple startPoints per origin zone. Default for the '''dijkstra_m''' function when omitted: all startPoints are considered as separate origin zones. This option is not allowed with the '''dijkstra_s''', where all startPoints are assumed to belong to the same origin zone.
+
-
* the optional '''max_imp''', indicates the production of a sub-item \(\text{OrgZone}\rightarrow\text{Imp}\), an Imp attribute of OrgZone, named '''MaxImp''' that contains the maximum impedance for each OrgZone for all connected DstZones. This is especially useful in combination with the '''limit(OrgZone_max_mass,DstZone_mass)''' option with which one can produce the distance to the n-th unit of a DstZone specific quantity. When all Nodes are considered as separate OrgZones, one can specify '''startPoints:max_imp'''. This option is available in GeoDMS 7.168 and later versions.
+
-
* when no additional arguments are indicated, this section should be omitted; '''startPoint()''' is non-allowed syntax.
+
-
* when no startPoints are specified (not allowed with '''dijkstra_s'''), all Nodes are considered as separate origin zones.
+
-
 
+
-
==endPoints==
+
-
The optional '''endPoint(Node_rel, impedance, DstZone_rel)''' specifies a set of destination zones.
+
-
* the optional '''Node_rel''' indicates the presence of an additional argument \(\text{endPoint} \rightarrow \text{Node} \), a Node attribute of endPoint in order to select a subset of nodes as endPoints. Default: all Nodes are considered as separate endPoints
+
-
* the optional '''impedance''' indicates the presence of an additional argument \(\text{endPoint} \rightarrow \text{MeasureType} \), an arrival impedance attribute of endPoint, useful mainly for when Destination Zones contain multiple endPoints.
+
-
* the optional '''DstZone_rel''' indicates the presence of an additional argument \(\text{endPoint} \rightarrow \text{DstZone} \), a destination zone per endPoint, in order to define multiple endPoints per DstZone. Default: each endPoint is considered as a separate destination.
+
-
* when no additional arguments are indicated, this section should be omitted; '''endPoint()''' is non-allowed syntax.
+
-
* when no endPoints are specified, all Nodes are considered as separate destination zones.
+
-
 
+
-
==filters==
+
-
The optional '''cut(OrgZone_max_imp)''' specifies that a maximum route impedance will limit the route search, which requires as additional argument: \(\text{OrgZone}\rightarrow\text{Impedance}\), an impedance attribute of the origin zones or a single impedance limit parameter that is applied for all origin zones.
+
-
 
+
-
The optional '''limit(OrgZone_max_mass,DstZone_mass)''' specifies that a maximum amount of destinations per origin zone will limit the route development, which requires 2 additional arguments:
+
-
* \(\text{OrgZone}\rightarrow\text{Mass}\) or \(\{\emptyset\}\rightarrow\text{Mass}\) (must have the same ValuesType as '''Impedance'''), a Mass attribute of OrgZone or a single Mass parameter, that sets a maximum on the amount of Mass to be reached at the DstZones.
+
-
* \(\text{DstZone}\rightarrow\text{Mass}\) or \(\{\emptyset\}\rightarrow\text{Mass}\) (must have the same ValuesType as '''Impedance'''), a Mass attribute of DstZone or a single Mass parameter, that indicates a Mass for each DstZone, which is accumulated until the limit is reached for each OrgZone.
+
-
 
+
-
==alternative impedance==
+
-
The optional '''alternative(link_impedance):alt_imp''' specifies that an alternative link impedance is to be used to calculate an impedance per od-pair for further use in the interaction potential calculation.
+
-
* This requires an additional argument: \(\text{Links}\rightarrow\text{Impedance2}\), an alternative impedance per link, where Impedance2 must have the same values type as the original impedance, but may have a different metric.
+
-
* the optional product '''alt_imp''' indicates the production of an Impedance2 attribute of the resulting od-pair entity named '''alt_imp''' with the total alternative impedance of the found routes for each od-pair.
+
-
* when this section is omitted, the original Impedance is used in the interaction calculation and the unit Impedance2 is set to be equal to Impedance.
+
-
* when not filtering applies, some od-pairs may represent combinations without connecting route. The impedance is MAX_VALUE<ImpType> there but the alt_imp is <null> there. Both values will not be taken into account in an interaction distribution.
+
-
 
+
-
==interaction==
+
-
 
+
-
The optional '''interaction(OrgZone_min,DstZone_min,v_i,w_j,dist_decay,OrgZone_alpha):D_i,M_ix,C_j,M_xj,Link_flow''' indicates the application of a free or origin constrained interaction model following the thoughts and notation of Alonso's General Theory of Movement (GTM) with a fixed supply elasticity per destination of 1 (thus \(\beta_j = 1.0\); no constraint on the destination side).
+
-
* the optional '''OrgZone_min''' indicates an additional argument: \(\text{OrgZone}\rightarrow\text{Impedance2}\) which can also be a single value  (an attribute of void), indicating a minimum (alternative) impedance to be used for each destination to avoid infinite auto interaction potential for each origin. Default value is 0.
+
-
* the optional '''DstZone_min''' indicates an additional argument: \(\text{DstZone}\rightarrow\text{Impedance2}\) which can also be a single value, indicating a minimum (alternative) impedance to be used for each origin to avoid infinite auto interaction potential for each destination. Default value is 0.
+
-
* the obligatory '''v_i''' indicates an additional argument: \(\text{OrgZone}\rightarrow\text{Mass}\) which can also be a single value, indicating a trip generation weight per origin, aka \( v_i \).
+
-
* the obligatory '''w_j''' indicates an additional argument: \(\text{DstZone}\rightarrow\text{Mass}\) which can also be a single value, indicating a trip distribution weight per destination, aka \( w_j \).
+
-
* the obligatory '''dist_decay''' indicates an additional argument  \( \gamma: \text{Float32}\)  that indicates the rate of distance decay. The used interaction potential \(t_{ij}\) is calculated as \( t_{ij} := d_{ij}^{-\gamma} \).
+
-
**\( \gamma = 1.0  \) thus indicates \( t_{ij} = 1/d_{ij} \)
+
-
**If no route exists from \(i\) to \(j\) (which can be visible in the results when no filtering was applied), \(t_{ij}\) is set to \(0\).
+
-
**\( \gamma = 0.0 \) indicates \( t_{ij} = 1 \), even when \( d_{ij} \le 0 \), except when no route exists.
+
-
**\( \gamma = -1.0 \) indicates \( t_{ij} = d_{ij} \)
+
-
**when \( d_{ij} \le 0 \) and \( \gamma \ne 0.0  \), \( t_{ij} \) is set to zero, to avoid incorporating infinite potentials when no minimum impedances nor departure or arrival impedances were specified. Auto-interaction is then excluded, but included when \( \gamma = 0.0 \).
+
-
* the optional '''demand_alpha''' indicates an additional argument: \(\text{OrgZone}->\text{Float32}\)  which can also be a single value,  indicating the elasticity of origin's supply for the amount of demand alternatives. \( \alpha = 1.0  \) indicates an elastic model; \( \alpha = 0.0  \) indicates a push model with fixed supply \( v_i \) per origin.
+
-
 
+
-
Calculated products (at least one should be specified):
+
-
* the optional '''D_i''', indicates the production of a sub-item \(\text{OrgZone}\rightarrow\text{Mass}\), a Mass attribute of OrgZone, named '''D_i''', aka \(D_i\), defined as \( D_i:= \sum\limits_{j} w_j \cdot t_{ij}\).
+
-
* the optional '''M_ix''', indicates the production of a sub-item \(\text{OrgZone}\rightarrow\text{Mass}\), a Mass attribute of OrgZone, named '''M_ix''', aka \(M_{ix}\), defined as \( M_{ix} := v_i \cdot\ D_i^\alpha = \sum\limits_{j} v_i \cdot w_j \cdot t_{ij} \cdot D_i^{(\alpha-1)}\). Note that when \(D_i = 0\), \( D_i^\alpha \) is assumed to be zero, even if \(\alpha = 0\), in order to respect the fact that if there is no demand potential at all, it cannot be raised to a set demand whatever the elasticity.
+
-
* the optional '''C_j''', indicates the production of a sub-item \(\text{DstZone}\rightarrow\text{Mass}\), a Mass attribute of DstZone, named '''C_j''', aka \(C_j\), defined as \( C_j:= \sum\limits_{i} v_i \cdot t_{ij} \cdot D_i^{(\alpha-1)}\).
+
-
* the optional '''M_xj''', indicates the production of a sub-item \(\text{DstZone}\rightarrow\text{Mass}\), a Mass attribute of DstZone, named '''M_xj''', aka \(m_{xj}\), defined as \( M_{xj}:= w_j \cdot C_j = \sum\limits_{i} v_i \cdot w_j \cdot t_{ij} \cdot D_i^{(\alpha-1)}\).
+
-
* the optional '''Link_flow''', indicates the production of a traffic flow network assignment, a sub-item \(\text{Link}\rightarrow\text{Mass}\), a Mass attribute of Link, named '''Link_flow''', aka \(LF_l\), defined as \( LF_l := \sum\limits_{l \in i \rightarrow j} v_i \cdot w_j \cdot t_{ij} \cdot D_i^{(\alpha-1)}\).
+
-
 
+
-
==Traceback production==
+
-
the optional '''node:TraceBack''' (only available for '''dijkstra_s''') produces a sub-item \(\text{TraceBack}: \text{Node} \rightarrow \text{Node} \), a Node attribute of Node, indicating for each node which previous node of the grown tree(s) traces back to the origin of startPoint Node(s).
+
-
 
+
-
For the '''dijkstra_m''' function, producing this info is complicated by the fact that a trace back would be available for each origin.
+
-
 
+
-
==od-pair specification and attribute production==
+
-
the optional '''od:impedance,OrgZone_rel,DstZone_rel,LinkSet''', indicates the production of a specific kind of od-paid entity and related attributes.
+
-
* the optional '''impedance''' indicates the production of a sub-item \(\text{impedance}: \text{OD} \rightarrow \text{Impedance} \), an attribute with the lowest route impedance per found od-pair. This impedance includes startPoint(impedance) and endPoint(impedance) but not OrgZone_min nor DstZone_min.
+
-
* the optional '''OrgZone_rel''' indicates the production of a sub-item \(\text{OrgZone_rel}: \text{OD} \rightarrow \text{OrgZone} \), an attribute with the OrgZone of each od-pair.
+
-
* the optional '''DstZone_rel''' indicates the production of a sub-item \(\text{DstZone_rel}: \text{OD} \rightarrow \text{DstZone} \), an attribute with the DstZone of each od-pair.
+
-
* the optional '''LinkSet'''    indicates the production of a sub-item \(\text{LinkSet}: \text{OD} \rightarrow \text{Link-sequence} \), an attribute with the sequence of Links of each od-pair route.
+
-
 
+
-
When no od-pair related products are requested (including no '''alt_imp'''), the memory footprint of the operation will be greatly reduced as intermediate potentials and route flows per od-pair are produced per OrgZone and directly aggregated to the OrgZone, DstZone, and/or Link level and no storage is required per od-pair simultaneously for different OrgZones.
+
-
 
+
-
=production of \(t_{ij}\) and \(M_{ij}\)=
+
-
 
+
-
In order to get \(t_{ij}\) and \(M_{ij}\), the calculated interaction potential and trip flow per od-pair, one can recalculate them from the results available from '''od:impedance,OrgZone_rel,DstZone_rel'''
+
-
 
+
-
*When no alternative link impedance is given, define as extra sub-item of the resulting od-pair unit:
+
-
attribute<Float32> t_ij := impedance >= 1e+38f ? 0.0f : distDecay == 0.0f ? 1.0f : impedance^-distDecay;
+
-
Note that \(t_{ij} >= \text{max_dist}\) only for od-pairs without available route, which only appears in results when no filtering option was used. If filtering was used and it is known that distDecay is non-zero, the above can be simplified to
+
-
attribute<Float32> t_ij := impedance^-distDecay;
+
-
*When alternative(link_imp):alt_imp is used, use:
+
-
attribute<Float32> t_ij := !IsDefined(alt_imp) ? 0.0f : distDecay == 0.0f ? 1.0f : alt_imp^-distDecay;
+
-
*When '''OrgZone_min''' or '''DstZone_min''' were specified , replace the last impedance measure ('''impedance''' or '''alt_imp''') by
+
-
**'''max_elem(impedance, min_imp[OrgZone_rel])''' when '''min_imp''' is given per origin zone,
+
-
**'''max_elem(impedance, min_imp[DstZone_rel])''' when '''min_imp''' is given per destination zone, or just
+
-
**'''max_elem(impedance, min_imp)''' when it is a single value parameter, applied for all od-pairs.
+
-
 
+
-
* The \(M_{ij} \) can then be calculated with
+
-
attribute<Float32> M_ij := D_i[OrgZone_rel] <= 0.0f ? 0.0f : t_ij*D_i[OrgZone_rel]^(demand_alpha-1.0f);
+
-
* if the demand for each zone i is assumed to be inelastic , i.e. demand_alpha == 0f, this can be simplified to
+
-
attribute<Float32> M_ij := D_i[OrgZone_rel] <= 0.0f ? 0.0f : t_ij*(1.0f / D_i)[OrgZone_rel];
+
-
An example of this can be found in the operator test configuration at '''/Network/UnTiled/dijkstra_all_interaction'''.
+
-
 
+
-
=Addtional notes=
+
-
 
+
-
* Filtering with '''cut''' or '''limit''' is an essential tool for limiting the computation effort when modelling network flow due to local traffic with many origins and destinations. The implementation only processes localized data per OrgZone when such filtering is applied, making the computation time per OrgZone independent of the network size after initial initialization. For example, the processing of 4000 PC4 zones (both Origin and Destination) on the OpenStreetMap network of the Netherlands with boundary extensions took 10 minutes when pcut was set to 1800[sec], resulting in an OD set of 750.000 pairs, thus approximately an average of 175 destinations per origin (of the 4000 potential destinations), whereas processing all od-pairs took several hours. The generation of Link_flow (Network Assignment) from the 4000 PC4 origins to all 5.000.000 nodes as destinations with a cut of 5 minutes took approximately 1 minute to produce. See item /Analyses/PC4_2_PC4/MakeOD/OD_impcut5min_all_na/UsedLinks/LinkFlow in the oda configuration and its [[http://www.objectvision.nl/out/AllPC4_AllNodes_NetworkFlow.png MapView]];
+
-
 
+
-
* one can model constrained supply by iteratively adjusting \( w_j \) with \( C_j^{\beta_j-1} \) with \(\beta_j\) as supply elasticiy parameter.
+
-
* one can model a congested network equilibriumby iterative application of the network assignment by implementing a feedback loop (http://en.wikipedia.org/wiki/Transportation_forecasting) on the link impedances.
+
-
* by assigning a heterogeneous set of transport users (mode, income, trip purpose, etc.) in slices of, say 10% per slice, one can also obtain a balanced load of the network and the choice of startPoints per
+
-
* by using short cuts for interactions between many small zones and larger cuts for interaction between a smaller number of larger zones, one can obtain a balanced load of the network within a reasonable amount of computation time.
+
-
* one can generate route counts per link with '''interaction(v_i,w_j,dist_decay,OrgZone_alpha):D_i,C_j,Link_flow''' by setting \( v_i = w_j = \alpha_i = 1.0 \) and \( \gamma = 0.0 \). The resulting \(D_i\) and \(C_j\) are total route counts per origin an destination.
+
-
* one can generate link counts per od-pair with '''alternative(link_impedance):alt_imp''' by providing 1.0 as alternative link impedance.
+
-
 
+
-
=Future extensions=
+
-
Possible extensions include:
+
-
* Log-logistic distance decay \(d \to 1/(1+e^{a+b \ln d}) = 1/(1 + e^a d^b) \).
+
-
 
+
-
Possible speedup optimizations are:
+
-
* Parallel processing of different OrgZones, as most time is now spent in growing trees, which can be done per origin zone separately, a speedup factor is expected close to the number of available cores.
+
-
* Pre processing, overview: http://algo2.iti.kit.edu/schultes/hwy/dynamic.pdf
+
-
** using highway hierarchies along the lines of http://algo2.iti.kit.edu/schultes/hwy/distTable.pdf, and http://algo2.iti.kit.edu/schultes/hwy/esaHwyHierarchiesSlides.pdf
+
-
** edge reduction
+
-
** transit node routing and separators
+
-
** A* methods, geometric containment and goal direction search, useful only for individual OD-pairs.
+
-
=Links=
+
== '''see also''' ==
-
* For a discussion of Alonso's General Theory of Movements (GTM), see:
+
*[[dijkstra general]]
-
**[http://dare.ubvu.vu.nl/bitstream/handle/1871/3400/11744.pdf?sequence=1 Alonso's General Theory of Movement: Advances in Spatial Interaction Modeling, de Vries, Nijkamp and Rietveld] The changed notation can be reverted by applying the following rewrite rules: \( T_{ij} \rightarrow M_{ij}; F_{ij} \rightarrow t_{ij}; O_i \rightarrow M_{ix}; D_j \rightarrow M_{xj}; A_i \rightarrow D_i^{-1};B_j \rightarrow C_j^{-1}; V_i \rightarrow v_i; W_j \rightarrow w_j; c_{ij} \rightarrow d_{ij}; \gamma_1 \rightarrow \gamma \)
+
*[[dijkstra key entities]]
-
* Example code can be found in the [http://svn.objectvision.nl/public/geodms/trunk/prj/oda oda configuration], more specifically in configuration file [http://svn.objectvision.nl/public/geodms/trunk/prj/oda/cfg/stam/analyses/PC4_2_PC4.dms cfg/stam/analyses/PC4_2_PC4.dms]. See in oda for example
+
*[[dijkstra options]]
-
** item /Analyses/PC4_2_PC4/MakeOD/OD_impcut_td/DstMass in MapView.
+
*[[dijkstra warning]]
-
** item /Analyses/PC4_2_PC4/MakeOD/OD_impcut_na/LinkFlow in MapView.
+
*[[dijkstra interaction potential]]
-
** [[http://www.objectvision.nl/out/AmsterdamPC4_NetworkFlow.png Screenshot of /Analyses/PC4_2_PC4/MakeOD/OD_impcut_na/LinkFlow in MapView]]
+
*[[dijkstra additional]]
-
** [[http://www.objectvision.nl/out/AllPC4_AllNodes_NetworkFlow.png Screenshot of /Analyses/PC4_2_PC4/MakeOD/OD_impcut5min_all_na/UsedLinks/LinkFlow in MapView]]
+
*[[dijkstra future]]
-
* more basic (and contrived) examples can be found in the [http://svn.objectvision.nl/public/geodms/trunk/tst/Operator/cfg/Operator.dms GeoDms regression tests], more specifically: in the Network section thereof.
+
*[[dijkstra links]]

Current revision as of 19:20, 25 May 2020

This page reflects the dijkstra functions of GeoDMS 7.212.
See GeoDms Setups for installing GeoDMS 7.212 or later.

Network functions dijkstra functions

Functions

There are only three preferred dijkstra operations:

  • dijkstra_s(...): when all given startPoints have to be considered as a single origin zone, resulting in:
    • an attribute DstZone->Impedance with the lowest route Impedance per destination zone.
    • optional attributes as sub-items depending on the used options.
  • dijkstra_m(...) when startPoints can relate to multiple origin zones, resulting in
    • a unit<uint32> reflecting the set of all or all found od-pairs
    • optional attributes as sub-items depending on the used options.
  • dijkstra_m64(...), similar to dijkstra_m(...), but resulting in a unit<uint64> in order to accommodate more than \(2^{32}-2\) od-pairs.

All these operations require at least the following four arguments:

  • \( \text{options}: \{\emptyset\} \rightarrow \text{String} \), a String parameter indicating function options, described below.
  • \( \text{impedance}: \text{Link} \rightarrow \text{Impedance} \), a Measure (Float32 or Float64) attribute of Links with the Impedance per Link.
  • \( \text{f1}: \text{Link} \rightarrow \text{Node} \), a Node attribute of Link indicating the from node of each link.
  • \( \text{f2}: \text{Link} \rightarrow \text{Node} \), a Node attribute of Link indicating the to node of each link.

Note that dijkstra can run different OrgZones in parallel, up to the number of cores of the running machine, as their tree growing is independent. This does not affect dijkstra_s, as that only grows one tree.

see also

Personal tools