# Distance

LightGraphs.jl includes the following distance measurements:

## Full Docs

LightGraphs.MinkowskiCostMethod
MinkowskiCost(μ₁, μ₂; p::Real=1)

For labels μ₁ on the vertices of graph G₁ and labels μ₂ on the vertices of graph G₂, compute the p-norm cost of substituting vertex u ∈ G₁ by vertex v ∈ G₂.

Optional Arguments

p=1: the p value for p-norm calculation.

source
LightGraphs.centerMethod
center(eccentricities)
center(g, distmx=weights(g))

Given a graph and optional distance matrix, or a vector of precomputed eccentricities, return the set of all vertices whose eccentricity is equal to the graph's radius (that is, the set of vertices with the smallest eccentricity).

Examples

julia> using LightGraphs

julia> center(star_graph(5))
1-element Array{Int64,1}:
1

julia> center(path_graph(5))
1-element Array{Int64,1}:
3
source
LightGraphs.diameterMethod
diameter(eccentricities)
diameter(g, distmx=weights(g))

Given a graph and optional distance matrix, or a vector of precomputed eccentricities, return the maximum eccentricity of the graph.

Examples

julia> using LightGraphs

julia> diameter(star_graph(5))
2

julia> diameter(path_graph(5))
4
source
LightGraphs.eccentricityMethod
eccentricity(g[, v][, distmx])
eccentricity(g[, vs][, distmx])

Return the eccentricity[ies] of a vertex / vertex list v or a set of vertices vs defaulting to the entire graph. An optional matrix of edge distances may be supplied; if missing, edge distances default to 1.

The eccentricity of a vertex is the maximum shortest-path distance between it and all other vertices in the graph.

The output is either a single float (when a single vertex is provided) or a vector of floats corresponding to the vertex vector. If no vertex vector is provided, the vector returned corresponds to each vertex in the graph.

Performance

Because this function must calculate shortest paths for all vertices supplied in the argument list, it may take a long time.

Implementation Notes

The eccentricity vector returned by eccentricity() may be used as input for the rest of the distance measures below. If an eccentricity vector is provided, it will be used. Otherwise, an eccentricity vector will be calculated for each call to the function. It may therefore be more efficient to calculate, store, and pass the eccentricities if multiple distance measures are desired.

An infinite path length is represented by the typemax of the distance matrix.

Examples

julia> g = SimpleGraph([0 1 0; 1 0 1; 0 1 0]);

julia> eccentricity(g, 1)
2

julia> eccentricity(g, [1; 2])
2-element Array{Int64,1}:
2
1

julia> eccentricity(g, [1; 2], [0 2 0; 0.5 0 0.5; 0 2 0])
2-element Array{Float64,1}:
2.5
0.5
source
LightGraphs.edit_distanceMethod
edit_distance(G₁::AbstractGraph, G₂::AbstractGraph)

Compute the edit distance between graphs G₁ and G₂. Return the minimum edit cost and edit path to transform graph G₁ into graph G₂. An edit path consists of a sequence of pairs of vertices(u,v) ∈ [0,|G₁|] × [0,|G₂|] representing vertex operations:

• $(0,v)$: insertion of vertex $v ∈ G₂$
• $(u,0)$: deletion of vertex $u ∈ G₁$
• $(u>0,v>0)$: substitution of vertex $u ∈ G₁$ by vertex $v ∈ G₂$

Optional Arguments

• insert_cost::Function=v->1.0
• delete_cost::Function=u->1.0
• subst_cost::Function=(u,v)->0.5

By default, the algorithm uses constant operation costs. The user can provide classical Minkowski costs computed from vertex labels μ₁ (for G₁) and μ₂ (for G₂) in order to further guide the search, for example:

edit_distance(G₁, G₂, subst_cost=MinkowskiCost(μ₁, μ₂))
• heuristic::Function=DefaultEditHeuristic: a custom heuristic provided to the A*

search in case the default heuristic is not satisfactory.

Performance

• Given two graphs $|G₁| < |G₂|$, edit_distance(G₁, G₂) is faster to

compute than edit_distance(G₂, G₁). Consider swapping the arguments if involved costs are equivalent.

• The use of simple Minkowski costs can improve performance considerably.
• Exploit vertex attributes when designing operation costs.

References

• RIESEN, K., 2015. Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications. (Chapter 2)

Author

Examples

julia> g1 = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);

julia> g2 = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);

julia> edit_distance(g1, g2)
(3.5, Tuple[(1, 2), (2, 1), (3, 0), (4, 3), (5, 0)])
source
LightGraphs.peripheryMethod
periphery(eccentricities)
periphery(g, distmx=weights(g))

Given a graph and optional distance matrix, or a vector of precomputed eccentricities, return the set of all vertices whose eccentricity is equal to the graph's diameter (that is, the set of vertices with the largest eccentricity).

Examples

julia> using LightGraphs

julia> periphery(star_graph(5))
4-element Array{Int64,1}:
2
3
4
5

julia> periphery(path_graph(5))
2-element Array{Int64,1}:
1
5
source
LightGraphs.radiusMethod
radius(eccentricities)
radius(g, distmx=weights(g))

Given a graph and optional distance matrix, or a vector of precomputed eccentricities, return the minimum eccentricity of the graph.

Examples

julia> using LightGraphs

julia> radius(star_graph(5))
1

julia> radius(path_graph(5))
2
source
LightGraphs.transitiveclosureFunction
transitiveclosure(g, selflooped=false)

Compute the transitive closure of a directed graph, using DFS. Return a graph representing the transitive closure. If selflooped is true, add self loops to the graph.

Performance

Time complexity is $\mathcal{O}(|E||V|)$.

Examples

julia> using LightGraphs

julia> barbell = blockdiag(complete_digraph(3), complete_digraph(3));

julia> add_edge!(barbell, 1, 4);

julia> collect(edges(barbell))
13-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
Edge 1 => 2
Edge 1 => 3
Edge 1 => 4
Edge 2 => 1
Edge 2 => 3
Edge 3 => 1
Edge 3 => 2
Edge 4 => 5
Edge 4 => 6
Edge 5 => 4
Edge 5 => 6
Edge 6 => 4
Edge 6 => 5

julia> collect(edges(transitiveclosure(barbell)))
21-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
Edge 1 => 2
Edge 1 => 3
Edge 1 => 4
Edge 1 => 5
Edge 1 => 6
Edge 2 => 1
Edge 2 => 3
Edge 2 => 4
Edge 2 => 5
Edge 2 => 6
Edge 3 => 1
Edge 3 => 2
Edge 3 => 4
Edge 3 => 5
Edge 3 => 6
Edge 4 => 5
Edge 4 => 6
Edge 5 => 4
Edge 5 => 6
Edge 6 => 4
Edge 6 => 5
source
LightGraphs.transitiveclosure!Function
transitiveclosure!(g, selflooped=false)

Compute the transitive closure of a directed graph, using DFS. If selflooped` is true, add self loops to the graph.

Performance

Time complexity is $\mathcal{O}(|E||V|)$.

Implementation Notes

This version of the function modifies the original graph.

source