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.
getDistance
(self, node u, node v)Returns the length of the shortest path from source ‘u’ to target v.
getDistances
(self)Returns a vector of vectors of distances between each node pair.
networkit.distance.
AdamicAdarDistance
Bases: object
Calculate the adamic adar similarity.
getAttribute
(self)preprocess
(self)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)networkit.distance.
AllSimplePaths
Bases: object
AllSimplePaths(G, source, target, cutoff=none)
Create AllSimplePaths for G, source node source, target node ‘target’ and cutoff ‘cutoff’.
forAllSimplePaths
(self, callback)More efficient path iterator. Iterates over all the simple paths.
getAllSimplePaths
(self)Returns all the simple paths from source to target.
numberOfSimplePaths
(self)Returns the number of simple paths.
run
(self)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.
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.
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
networkit.distance.
Diameter
Bases: _NetworKit.Algorithm
getDiameter
(self)networkit.distance.
DiameterAlgo
alias of _DiameterAlgo
networkit.distance.
Dijkstra
Bases: _NetworKit.SSSP
Dijkstra(G, source, [storePaths], [storeNodesSortedByDistance], target)
Creates Dijkstra for G and source node source.
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
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.
networkit.distance.
DynBFS
Bases: _NetworKit.DynSSSP
Dynamic version of BFS.
DynBFS(G, source)
Create DynBFS for G and source node source.
networkit.distance.
DynDijkstra
Bases: _NetworKit.DynSSSP
Dynamic version of Dijkstra.
DynDijkstra(G, source)
Create DynDijkstra for G and source node source.
networkit.distance.
Eccentricity
Bases: object
TODO: docstring
getValue
(Graph G, v)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.
getEffectiveDiameter
(self)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
getEffectiveDiameter
(self)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
getHopPlot
(self)networkit.distance.
JaccardDistance
Bases: object
The Jaccard distance measure assigns to each edge the jaccard coefficient of the neighborhoods of the two adjacent nodes.
getAttribute
(self)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.
getNeighborhoodFunction
(self)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
getNeighborhoodFunction
(self)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”.
RANDOM
= 0SPLIT
= 1getNeighborhoodFunction
(self)