Distance
Страница в процессе перевода. |
LightGraphs.jl includes the following distance measurements:
Full Docs
#
LightGraphs.BoundedMinkowskiCost
— Method
BoundedMinkowskiCost(μ₁, μ₂)
Return value similar to MinkowskiCost
, but ensure costs smaller than 2τ.
Optional Arguments
p=1
: the p value for p-norm calculation. τ=1
: value specifying half of the upper limit of the Minkowski cost.
#
LightGraphs.MinkowskiCost
— Method
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.
#
LightGraphs.center
— Method
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
#
LightGraphs.diameter
— Method
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
#
LightGraphs.eccentricity
— Method
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
#
LightGraphs.edit_distance
— Method
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₂
representing vertex operations:. An edit path consists of a sequence of pairs of vertices
(u,v) ∈ [0,|G₁|] × [0,|G₂|]`
-
: insertion of vertex
-
: deletion of vertex
-
: substitution of vertex by vertex
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 ,
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
-
Júlio Hoffimann Mendes (juliohm@stanford.edu)
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)])
#
LightGraphs.periphery
— Method
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
#
LightGraphs.radius
— Method
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
#
LightGraphs.transitiveclosure
— Function
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 .
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
#
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 .
Implementation Notes
This version of the function modifies the original graph.