The Pathfinder algorithm: the original, binary, Fast and MSTvariants
The algorithm
A Pathfinder Network (or PFNET) is a scaled network (or graph, in the sense of the graph theory) in which weighted edges have been pruned in a specific way. Only those edges which do not violate the triangle inequality are kept. The triangle inequality states that the direct distance between a couple of nodes must be lesser than or equal to the distance between any other path linking these nodes. The corresponding algorithm, first devised by Schvaneveldt (1990) has two parameters: r, which define the Minkowski rmetric used to compute the mentioned distance, and q, which define the maximum length of the paths considered in the triangle inequality. Pathfinder Networks are very important in the field of social networks, in which it helps to exhibit a unique representation of the underlying structure of the domain. In this context, the weight of the edges often represents the similarity between the entities given by the nodes.
According to the litterature, the most used values for its parameters are r=∞, meaning that we keep the edges having a value higher that the maximum similarity given by all the other paths, and q=n1, meaning that we consider the paths having any kind of lengths, including the maximal one, n1.
MSTPathfinder, up to our knowledge, is the fastest algorithm to obtain Pathfinder Networks for r=∞ and q=n1.
Applications
These networks are used in a large variety of applications including:
Additional information on the Pathfinder Networks can be found on the corresponding Wikipedia webpage: http://en.wikipedia.org/wiki/Pathfinder_networks
The following table shows a comparison of the variants of the Pathfinder algorithm, along with their performance in terms of time and memory, took from the paper [3]. We also provide a link to the source code (written in C). Some ZIP files contain a Makefile to compile the code on Unixlike platforms, and Visual Studio 6 project files to compile the code on Windowslike platforms, but the code should compile on both platforms.
Name of the algorithm 
Application domain  Time complexity (for q=n1) 
Space complexity 
Approach in algorithm theory 
Download  Academic paper 
Original PF  Any valid values for q and r, (un)directed graphs 
O(q · n^{3}) = O(n^{4})  2 · q · n^{2} = 2 · n^{3}  2 · n^{2}  Dynamic programming  download link  
Binary PF  Any valid values for q and r, (un)directed graphs 
O(log(q) · n^{3}) = O(n^{3} · log(n)) 
4 · n^{2}  Dynamic programming  download link  
Fast PF  Any valid values for r, q=n1, (un)directed graphs 
O(n^{3})  2 · n^{2}  Dynamic programming  download link  
Fast PF  Any valid values for q and r, (un)directed graphs 
O(n^{3})  2 · n^{2}  Dynamic programming  download link  
MSTPF (theoretical) 
r=∞, q=n1, undirected graphs 
O(n^{2} · log(n))  3 · n^{2}+n  Greedy approach  download link  
MSTPF (practical) 
r=∞, q=n1, undirected graphs 
O(n^{3})  3 · n^{2}+n  Greedy approach  download link 
Description in Pajek format:

Description in Pajek format:

Description in Pajek format:

[1] R. W. Schvaneveldt
(Ed.); Pathfinder
Associative Networks: Studies in Knowledge Organization; Norwood, NJ:
Ablex (1990).
RECEIVED:
16/4/2007; REVI
[2] A.
Quirin, O. Cordon, J.
Santamaria, B. VargasQuesada, F. MoyaAnegon; A new Variant of the
Pathfinder Algorithm to Generate Large Visual Science Maps in Cubic
Time; Information, Processing & Management Journal, 44(4):
16111623
(2008).
RECEIVED:
16/4/2007; REVISED:
3/9/2007; ACCEPTED:
8/9/2007;
IMPACT
FACTOR
2007: 1.500.; CATEGORY: COMP.
SCI., INF. SYST; ORDER:
27/92; DOI:10.1016/j.ipm.2007.09.005
[4] E.
Serrano, A. Quirin, J. Botia, O. Cordon; Debugging Complex Software
Systems by Means of Pathfinder Networks; Information Sciences, 180(5):
561583 (2010).
NOTIFICATION
OF
ACCEPTANCE: 3/11/2009; IMPACT
FACTOR 2009: 3.291; DOI: 10.1016/j.ins.2009.11.007