The Pathfinder algorithm was proposed in the eighties \citep{PF88,PF90} for
the simplification of weighted networks - it removes from the network all links that do
not satisfy the triangle inequality - if for a weighted link there exists a shorter
path connecting its endnodes then the link is removed.
The basic idea of the Pathfinder algorithm is simple. It produces
a network PFnet(**W**,r,q) = (V,L_{PF}) determined by the following scheme
of procedure

computeW^{(q)}; L_{PF}← ∅; for e(u,v) ∈ L: ifW^{(q)}[u,v] =W[u,v]: L_{PF}← L_{PF}⋃ {e} endfor

where **W** is a network **dissimilarity** matrix and
**W**^{(q)} = ⊕{i∈1:q : **W**^{i} } =
(**1** ⊕ **W**)^{q} is the matrix of the values of all walks of length
at most q computed over the **Pathfinder** semiring
(ℝ^{*}, ⊕, ⊛, ∞, 0) with a ⊛ b = ^{r}√(a^{r}+b^{r}) and
a ⊕ b = min(a,b). The value of w_{uv}(q) in the matrix **W**^{(q)}
is equal to the value of all walks of length at most q from the node u to the node v.

The scheme of Pathfinder is implemented as the function `pathFinder`

.
The temporal version of the statement

ifW^{(q)}[u,v] =W[u,v]: L_{PF}← L_{PF}⋃ {e}

is implemented in the function `PFcheck`

using the merging scheme.

The function `MatPower`

(A,k) computes the k-th power of the matrix **A**.

The time complexity of the Pathfinder algorithm is O(L ∙ n^{3} ∙ log q) \citep{PFc}.

**Pathfinder example.**

The bottom network in the figure presents the Pathfinder skeleton PFnet(N,1,∞) of a network N presented in the top part of the same figure. Because r=1 a link e is removed if there exists a path, connecting its initial node to its terminal node, with the value (sum of link values) smaller than the value of the link e. The arc (1,2) is removed because 3 = v(1,2) > v(1,3)+v(3,2) = 2. The arc (1,6) is removed in the time interval [5,9) because in this interval 5 = v(1,6) > v(1,3)+v(3,4)+v(4,5) +v(5,6) = 4, etc.

TQ User guide <<< >>>

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported