Graph Traversal: private API
PortfolioOptimisers.distance_wei — Function
distance_wei(L::MatNum)Compute the length of the shortest weighted path between each pair of vertices of a network.
The function runs the algorithm of Dijkstra on a weighted or unweighted network. Entry [u, v] of the result is the length of the shortest path from vertex u to vertex v. The mean of the shortest path lengths is the characteristic path length of the network.
It ports the function distance_wei of the Brain Connectivity Toolbox of Rubinov and Sporns [302].
The algorithm is Problem 2 of [303]. It settles the vertices in the order of their distance from the source, and by its Remark 1 it holds on a directed graph. The toolbox runs it from every source, settles every vertex at the least distance in one step, and counts the edges of each path in B. [303] states none of the three.
Mathematical definition
\[\begin{align} D_{u,\,v} &= \underset{p \in P(u,\, v)}{\min} \sum_{(i,\,j) \in p} L_{i,\,j}\,, \\ B_{u,\,v} &= \left| p^{\star}(u,\, v) \right|\,. \end{align}\]
Where:
- $L_{i,\,j}$: Connection length of the pair $(i,\, j)$, the entry of the input matrix.
- $P(u,\, v)$: Set of the paths from vertex $u$ to vertex $v$.
- $p^{\star}(u,\, v)$: Shortest of those paths, and $\left| p^{\star}(u,\, v) \right|$ its edge count.
- $D_{u,\,v}$: Shortest path length from vertex $u$ to vertex $v$.
- $B_{u,\,v}$: Edge count of that shortest path.
A pair that no path joins keeps $D_{u,\,v} = \infty$, because the minimum over an empty set is an infinity.
Algorithm
- Set every entry of
Dtotypemax, its diagonal to zero, and every entry ofBto zero. - For each source
u, mark every vertex temporary inS, copyLintoL1, and set the frontierVto[u]. - Make the frontier permanent in
S, and zero the columns ofL1atV, so no edge re-enters a settled vertex. - For each vertex
vof the frontier, read its remaining neighboursTand take, entry by entry, the smaller ofD[u, T]andD[u, v] + L1[v, T]. - Where the second of the two won, set
B[u, T]toB[u, v] + 1, so the edge count follows the path that won. - Take
minD, the smallest entry ofD[u, :]over the temporary vertices. Stop when no temporary vertex remains, and stop whenminDis infinite, which leaves every unreachable vertex attypemax. - Set the new frontier
Vto every vertex at distanceminD, and repeat from step 3.
Arguments
L:N × Nconnection-length matrix of a directed or undirected network.- A pair with no edge holds
0orInf. The function reads only the non-zero entries, and anInflength never gives a shorter path, so the two values give the same result. - The main diagonal holds
0.
- A pair with no edge holds
The input matrix must hold lengths, not weights. A caller maps each weight to a length, for example with the reciprocal of a similarity. DBHTs puts the entries of its distance matrix on the edges of the TMFG. In a weighted network, a shortest weighted path can have more edges than a shortest binary path.
Returns
D::Matrix{<:Number}:N × Nmatrix of the lengths of the shortest weighted paths.D[u, v]is the length of the shortest path from vertexuto vertexv.B::Matrix{Int}:N × Nmatrix of the edge count of each shortest weighted path.
Related
References
PortfolioOptimisers.breadth — Function
breadth(CIJ::MatNum, source::Integer)Run a breadth-first search from one source vertex.
The function searches a binary connection matrix of a directed or undirected graph, from the vertex source. It computes the shortest path distance from the source to each other vertex. It records in branch the predecessor of each vertex in the search tree. The tree holds one shortest path for each reachable vertex, and not every shortest path, so branch gives one path of minimum length to each vertex.
It ports the function breadth of the Brain Connectivity Toolbox of Rubinov and Sporns [302].
Breadth-first search is older than the toolbox. The library has no copy of the work that first states it, so this function follows the toolbox alone.
Algorithm
- Colour every vertex white, set every entry of
distancetoInf, and set every entry ofbranchto zero. - Colour
sourcegrey, set its distance to zero and its branch to-1, and put it in the queueQ. - Take the head
uofQ, and read its out-neighboursnsfrom the stored entries of rowu. - For each neighbour
vwhose distance is still zero, set it todistance[u] + 1. The distance of the source starts at zero, so this step also changes it when the search expands a neighbour of the source. - For each white neighbour
v, colour it grey, setdistance[v]todistance[u] + 1, setbranch[v]tou, and appendvtoQ. - Drop
ufromQand colour it black. Repeat from step 3 untilQis empty.
distance[source] does not stay 0. Step 4 changes it the first time that the search expands a neighbour of the source. On an undirected graph with no self-loop, the entry ends at 2. When the graph has a self-loop on the source, it ends at 1. The MATLAB original has the same behaviour. FindDisjoint, DirectHb and BubbleCluster8s call this function, and each writes 0 into the entry after the call.
Arguments
CIJ:N × Nbinary connection matrix of the graph. A non-zero entry is an edge. Rowuholds the out-neighbours of vertexu.source: Index of the vertex where the search starts.
Returns
distance::VecNum:N × 1vector of the shortest path distance from the source to each vertex. Its element type isfloat_if_integer(eltype(CIJ)), so an integer orBoolmatrix gives a floating-point vector.Infmarks a vertex that no path reaches. The entry of the source is not0, as the warning states.branch::Vector{Int}:N × 1vector of the predecessor of each vertex in the search tree. It is-1at the source and0at an unreachable vertex.
Related
References
- [302] M. Rubinov and O. Sporns. Complex network measures of brain connectivity: Uses and interpretations. NeuroImage 52(3), 1059–1069 (2010). Page 1065, for the toolbox that holds
breadth. The original source of this formulation was not found. The formulation follows this work and is not checked against the original.
References
- [302]
- M. Rubinov and O. Sporns. Complex network measures of brain connectivity: Uses and interpretations. NeuroImage 52, 1059–1069 (2010).
- [303]
- E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959).