Paths
Abstract
These functions help with path manipulation, and in particular the identification of shortest paths between any two nodes.
Shortest path algorithms
#
SpeciesInteractionNetworks.ShortestPathMethod — Type.
ShortestPathMethod
The first argument of shortestpath is a sub-type of ShortestPathMethod which specifies the algorithm to use.
In ecological networks, the weight of interactions typically measure how easy it is to move frome one node to the next. For this reason, we apply transformations to various interaction types.
In binary networks, the weights and the distance are the same, because all interactions have a value of 1.
For quantitative networks, we follow the approach of Newman (2001), where the distance of an interaction is the inverse of interaction strength. Nevertheless, it may be a good idea to correct the interaction strength before applying the shortest path search, for example by using normalize. This normalization is not done by default, and has to be explicit. Note that this normalisation is not changing the relative ordering of paths, but is making the distances a little more comparable to the binary case.
For probabilistic networks, the distance of an interaction is defined as $1 + (1 - p)$, so that an interaction happening with probability 1 has a distance of one.
References
#
SpeciesInteractionNetworks.BellmanFord — Type.
BellmanFord
The Bellman-Ford algorithmm (Shimbel, 1955) measures the distance from a source node to all other reachable nodes in the network.
Bellman-Ford is a weighted measure, in which the interactions are represented as costs of moving from a node to another.
References
#
SpeciesInteractionNetworks.Dijkstra — Type.
Dijkstra
References
Shortest path calculation
#
SpeciesInteractionNetworks.shortestpath — Function.
shortestpath(N::SpeciesInteractionNetwork{<:Partiteness{T}, <:Interactions}, sp::T)
Defaults to BellmanFord for the shortest path algorithm. See also Dijkstra.
Note that in order to work with pathbetween, any overload of shortestpath must accept an include_paths keyword argument, that when true returns a second dictionary giving the predecessors of each reached node.
Path reconstruction
#
SpeciesInteractionNetworks.pathbetween — Function.
pathbetween(::Type{ShortestPathMethod}, N::SpeciesInteractionNetwork{<:Partiteness{T}, <:Interactions}, source::T, target::T) where {T}
Returns the path between source and target. The result is given as a vector of interactions, i.e. it gives the subset of the output of interactions(N) going from source to target.
pathbetween(N::SpeciesInteractionNetwork{<:Partiteness{T}, <:Interactions}, source::T, target::T) where {T}
Returns the path between source and target, using BellmanFord as the default algorithm.
Utility functions
#
SpeciesInteractionNetworks.normalize — Function.
normalize(N::SpeciesInteractionNetwork{<:Partiteness, <:Quantitative})
Returns a quantitative network in which the interactions are normalized so that the average of interactions is one. Note that this excludes self-interactions.