Graph Traversal: private API

distance_wei(L::MatNum)

Compute the shortest weighted path lengths between all node pairs in a network.

This function computes the distance matrix containing the lengths of the shortest paths between all node pairs in a (possibly weighted) network, using Dijkstra's algorithm. An entry [u, v] represents the length of the shortest path from node u to node v. The average shortest path length is the characteristic path length of the network.

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

1. Set every entry of D to typemax, its diagonal to zero, and every entry of B to zero.
2. For each source u, mark every vertex temporary in S, copy L into L1, and set the frontier V to [u].
3. Make the frontier permanent in S, and zero the columns of L1 at V, so no edge re-enters a settled vertex.
4. For each vertex v of the frontier, read its remaining neighbours T and take, entry by entry, the smaller of D[u, T] and D[u, v] + L1[v, T].
5. Where the second of the two won, set B[u, T] to B[u, v] + 1, so the edge count follows the path that won.
6. Take minD, the smallest entry of D[u, :] over the temporary vertices. Stop when no temporary vertex remains, and stop when minD is infinite, which leaves every unreachable vertex at typemax.
7. Set the new frontier V to every vertex at distance minD, and repeat from step 3.

Arguments

• L: N × N directed or undirected connection-length matrix.

  • Lengths between disconnected nodes should be set to Inf.
  • Lengths on the main diagonal should be set to 0.

Returns

• D::Matrix{<:Number}: N × N shortest weighted path length matrix. D[u, v] is the length of the shortest path from vertex u to vertex v.
• B::Matrix{Int}: N × N matrix of the edge count of each shortest weighted path.

Related

• PMFG_T2s
• CliqHierarchyTree2s
• DBHT

breadth(CIJ::MatNum, source::Integer)

Breadth-first search.

This function performs a breadth-first search (BFS) on a binary (directed or undirected) connection matrix, starting from a specified source vertex. It computes the shortest path distances from the source to all other vertices and records the predecessor (branch) for each node in the BFS tree. The tree holds one shortest path per reachable vertex, and not every shortest path, so branch reconstructs one route of minimum length rather than all of them.

Algorithm

1. Colour every vertex white, set every entry of distance to Inf, and set every entry of branch to zero.
2. Colour source grey, set its distance to zero and its branch to -1, and put it in the queue Q.
3. Take the head u of Q, and read its out-neighbours ns from the stored entries of row u.
4. For each neighbour v whose distance is still zero, set it to distance[u] + 1. The source starts at zero, so this arm also fires on the source itself as soon as one of its own neighbours is expanded.
5. For each white neighbour v, colour it grey, set distance[v] to distance[u] + 1, set branch[v] to u, and append v to Q.
6. Drop u from Q and colour it black. Repeat from step 3 until Q is empty.

Arguments

• CIJ: N × N binary (0/1) connection matrix representing the graph. Row u holds the out-neighbours of vertex u.
• source: Index of the source vertex from which to start the search.

Returns

• distance::VecNum: N × 1 vector of shortest path distances from the source to each vertex, in the type a division of CIJ's entries lands in. Inf marks a vertex no path reaches. The source's own entry is not 0; see the warning above.
• branch::Vector{Int}: N × 1 vector of predecessor indices for each vertex in the BFS tree (-1 for the source, 0 for an unreachable vertex).

Related

• FindDisjoint
• CliqHierarchyTree2s