# networkit.distance

class networkit.distance.APSP

Bases: _NetworKit.Algorithm

All-Pairs Shortest-Paths algorithm (implemented running Dijkstra’s algorithm from each node, or BFS if G is unweighted).

APSP(G)

Computes all pairwise shortest-path distances in G.

Parameters
G : Graph
The graph.
getDistance(self, node u, node v)

Returns the length of the shortest path from source ‘u’ to target v.

u : node
Source node.
v : node
Target node.
int or float
The distance from ‘u’ to ‘v’.
getDistances(self)

Returns a vector of vectors of distances between each node pair.

vector of vectors
The shortest-path distances from each node to any other node in the graph.
class networkit.distance.AdamicAdarDistance

Bases: object

G : Graph
The input graph.
getAttribute(self)
vector[double]
preprocess(self)
class networkit.distance.AlgebraicDistance

Bases: object

Algebraic distance assigns a distance value to pairs of nodes

according to their structural closeness in the graph. Algebraic distances will become small within dense subgraphs.

G : Graph
The graph to calculate Jaccard distances for.
numberSystems : count
Number of vectors/systems used for algebraic iteration.
numberIterations : count
Number of iterations in each system.
omega : double
attenuation factor in [0,1] influencing convergence speed.
norm : index
The norm factor of the extended algebraic distance.
withEdgeScores : bool
calculate array of scores for edges {u,v} that equal ad(u,v)
distance(self, node u, node v)
getEdgeScores(self)
preprocess(self)
class networkit.distance.AllSimplePaths

Bases: object

Algorithm to compute all existing simple paths from a source node to a target node. The maximum length of the paths can be fixed through ‘cutoff’.
CAUTION: This algorithm could take a lot of time on large networks (many edges), especially if the cutoff value is high or not specified.

AllSimplePaths(G, source, target, cutoff=none)

Create AllSimplePaths for G, source node source, target node ‘target’ and cutoff ‘cutoff’.

G : Graph
The graph.
source : node
The source node.
target : node
The target node.
cutoff : count
(optional) The maximum length of the simple paths.
forAllSimplePaths(self, callback)

More efficient path iterator. Iterates over all the simple paths.

callback : object
Any callable object that takes the parameter path
getAllSimplePaths(self)

Returns all the simple paths from source to target.

A vector of vectors.
A vector containing vectors which represent all simple paths.
numberOfSimplePaths(self)

Returns the number of simple paths.

count
The number of simple paths.
run(self)
class networkit.distance.BFS

Bases: _NetworKit.SSSP

Simple breadth-first search on a Graph from a given source

BFS(G, source, [storePaths], [storeNodesSortedByDistance], target)

Create BFS for G and source node source.

G : Graph
The graph.
source : node
The source node of the breadth-first search.
storePaths : bool
store paths and number of paths?
target: node
terminate search when the target has been reached
class networkit.distance.CommuteTimeDistance

Bases: object

Computes the Euclidean Commute Time Distance between each pair of nodes for an undirected unweighted graph.

CommuteTimeDistance(G)

Create CommuteTimeDistance for Graph G.

G : Graph
The graph.

tol: double

distance(self, u, v)

Returns the ECTD between node u and node v.

u : node v : node

run(self)

This method computes ECTD exactly.

runApproximation(self)

Computes approximation of the ECTD.

runParallelApproximation(self)

Computes approximation (in parallel) of the ECTD.

runSinglePair(self, u, v)

Returns the ECTD between node u and node v, without preprocessing.

u : node v : node

runSingleSource(self, u)

Returns the sum of the ECTDs from u, without preprocessing.

u : node

class networkit.distance.Diameter

Bases: _NetworKit.Algorithm

getDiameter(self)
networkit.distance.DiameterAlgo

alias of _DiameterAlgo

class networkit.distance.Dijkstra

Bases: _NetworKit.SSSP

Dijkstra’s SSSP algorithm.
Returns list of weighted distances from node source, i.e. the length of the shortest path from source to any other node.

Dijkstra(G, source, [storePaths], [storeNodesSortedByDistance], target)

Creates Dijkstra for G and source node source.

Parameters
G : Graph
The graph.
source : node
The source node.
storePaths : bool
Paths are reconstructable and the number of paths is stored.
storeNodesSortedByDistance: bool
Store a vector of nodes ordered in increasing distance from the source.
target : node
target node. Search ends when target node is reached. t is set to None by default.
class networkit.distance.DynAPSP(Graph G)

Bases: _NetworKit.APSP

All-Pairs Shortest-Paths algorithm for dynamic graphs.

DynAPSP(G)

Computes all pairwise shortest-path distances in G.

Parameters

G : Graph
The graph.
update(self, ev)

Updates shortest paths with the edge insertion.

ev : GraphEvent.

updateBatch(self, batch)

Updates shortest paths with the batch batch of edge insertions.

batch : list of GraphEvent.

class networkit.distance.DynBFS

Bases: _NetworKit.DynSSSP

Dynamic version of BFS.

DynBFS(G, source)

Create DynBFS for G and source node source.

G : Graph
The graph.
source : node
The source node of the breadth-first search.
storeStack : bool
maintain a stack of nodes in order of decreasing distance?
class networkit.distance.DynDijkstra

Bases: _NetworKit.DynSSSP

Dynamic version of Dijkstra.

DynDijkstra(G, source)

Create DynDijkstra for G and source node source.

G : Graph
The graph.
source : node
The source node of the breadth-first search.
class networkit.distance.Eccentricity

Bases: object

TODO: docstring

static getValue(Graph G, v)
class networkit.distance.EffectiveDiameter

Bases: _NetworKit.Algorithm

Calculates the effective diameter of a graph. The effective diameter is defined as the number of edges on average to reach a given ratio of all other nodes.

G : Graph
The graph.
ratio : double
The percentage of nodes that shall be within stepwidth; default = 0.9
getEffectiveDiameter(self)
double
the effective diameter
class networkit.distance.EffectiveDiameterApproximation

Bases: _NetworKit.Algorithm

Calculates the effective diameter of a graph. The effective diameter is defined as the number of edges on average to reach a given ratio of all other nodes.

Implementation after the ANF algorithm presented in the paper “A Fast and Scalable Tool for Data Mining in Massive Graphs”[1]

[1] by Palmer, Gibbons and Faloutsos which can be found here: http://www.cs.cmu.edu/~christos/PUBLICATIONS/kdd02-anf.pdf

G : Graph
The graph.
ratio : double
The percentage of nodes that shall be within stepwidth, default = 0.9
k : count
number of parallel approximations, bigger k -> longer runtime, more precise result; default = 64
r : count
number of additional bits, important in tiny graphs; default = 7
getEffectiveDiameter(self)
double
the approximated effective diameter
class networkit.distance.HopPlotApproximation

Bases: _NetworKit.Algorithm

Computes an approxmation of the hop-plot of a given graph. The hop-plot is the set of pairs (d, g(g)) for each natural number d and where g(d) is the fraction of connected node pairs whose shortest connecting path has length at most d.

Implementation after the ANF algorithm presented in the paper “A Fast and Scalable Tool for Data Mining in Massive Graphs”[1]

[1] by Palmer, Gibbons and Faloutsos which can be found here: http://www.cs.cmu.edu/~christos/PUBLICATIONS/kdd02-anf.pdf

G : Graph
The graph.
maxDistance : double
maximum distance between considered nodes set to 0 or negative to get the hop-plot for the entire graph so that each node can reach each other node
k : count
number of parallel approximations, bigger k -> longer runtime, more precise result; default = 64
r : count
number of additional bits, important in tiny graphs; default = 7
getHopPlot(self)
map
number of connected nodes for each distance
class networkit.distance.JaccardDistance

Bases: object

The Jaccard distance measure assigns to each edge the jaccard coefficient of the neighborhoods of the two adjacent nodes.

G : Graph
The graph to calculate Jaccard distances for.
triangles : vector[count]
Previously calculated edge triangle counts.
getAttribute(self)
class networkit.distance.NeighborhoodFunction

Bases: _NetworKit.Algorithm

Computes the neighborhood function exactly. The neighborhood function N of a graph G for a given distance t is defined as the number of node pairs (u,v) that can be reached within distance t.

G : Graph
The graph.
getNeighborhoodFunction(self)
list
the i-th element denotes the number of node pairs that have a distance at most (i+1)
class networkit.distance.NeighborhoodFunctionApproximation

Bases: _NetworKit.Algorithm

Computes an approximation of the neighborhood function. The neighborhood function N of a graph G for a given distance t is defined as the number of node pairs (u,v) that can be reached within distance t.

Implementation after the ANF algorithm presented in the paper “A Fast and Scalable Tool for Data Mining in Massive Graphs”[1]

[1] by Palmer, Gibbons and Faloutsos which can be found here: http://www.cs.cmu.edu/~christos/PUBLICATIONS/kdd02-anf.pdf

G : Graph
The graph.
k : count
number of approximations, bigger k -> longer runtime, more precise result; default = 64
r : count
number of additional bits, important in tiny graphs; default = 7
getNeighborhoodFunction(self)
list
the i-th element denotes the number of node pairs that have a distance at most (i+1)
class networkit.distance.NeighborhoodFunctionHeuristic

Bases: _NetworKit.Algorithm

Computes a heuristic of the neighborhood function. The algorithm runs nSamples breadth-first searches and scales the results up to the actual amount of nodes. Accepted strategies are “split” and “random”.

G : Graph
The graph.
nSamples : count
the amount of samples, set to zero for heuristic of max(sqrt(m), 0.15*n)
strategy : enum
the strategy to select the samples, accepts “random” or “split”
RANDOM = 0
SPLIT = 1
getNeighborhoodFunction(self)
list
the i-th element denotes the number of node pairs that have a distance at most (i+1)