Distance
Erdos.jl includes the following distance measurements:
Erdos.center
— Methodcenter(g, distmx=weights(g))
center(all_ecc)
Returns the set of all vertices whose eccentricity is equal to the graph's radius (that is, the set of vertices with the smallest eccentricity).
Eventually a vector all_ecc
contain the eccentricity of each node can be passed as argument.
See eccentricities
.
Erdos.diameter
— Functiondiameter(g, distmx=weights(g))
Returns the maximum distance between any two vertices in g
. Distances between two adjacent nodes are given by distmx
.
See also eccentricities
, radius
.
Erdos.eccentricities
— Functioneccentricities(g, distmx=weights(g))
eccentricities(g, vs, distmx=weights(g))
Returns [eccentricity(g,v,distmx) for v in vs]
. When vs
it is not supplied, considers all node in the graph.
See also eccentricity
.
Note: the eccentricity vector returned by eccentricity
may be eventually used as input in some eccentricity related measures (periphery
, center
).
Erdos.eccentricity
— Functioneccentricity(g, v, distmx=weights(g))
Calculates the eccentricity[ies] of a vertex v
, An optional matrix of edge distances may be supplied.
The eccentricity of a vertex is the maximum shortest-path distance between it and all other vertices in the graph.
Erdos.periphery
— Methodperiphery(g, distmx=weights(g))
periphery(all_ecc)
Returns the set of all vertices whose eccentricity is equal to the graph's diameter (that is, the set of vertices with the largest eccentricity).
Eventually a vector all_ecc
contain the eccentricity of each node can be passed as argument.
See eccentricities
.
Erdos.radius
— Functionradius(g, distmx=weights(g))
Returns the minimum distance between any two vertices in g
. Distances between two adjacent nodes are given by distmx
.
See eccentricities
, diameter
.
Erdos.BoundedMinkowskiCost
— MethodSimilar to MinkowskiCost, but ensures costs smaller than 2τ.
Erdos.MinkowskiCost
— MethodFor 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₂.
Erdos.edit_distance
— Methodedit_distance(G₁, G₂;
insert_cost::Function=v->1.0,
delete_cost::Function=u->1.0,
subst_cost::Function=(u,v)->0.5,
heuristic::Function=DefaultEditHeuristic)
Computes the edit distance between graphs G₁ and G₂.
Returns 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₂
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(μ₁, μ₂))
A custom heuristic can be provided to the A* search in case the default heuristic is not satisfactory. Performance tips: ––––––––-
- 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 symmetric
.
- The use of simple Minkowski costs can improve performance considerably.
- Exploit vertex attributes when designing operation costs.
For further details, please refer to:
RIESEN, K., 2015. Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications. (Chapter 2)
Author: Júlio Hoffimann Mendes (juliohm@stanford.edu)