Distance

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.

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.

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 Graphs

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

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

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 Graphs

julia> diameter(star_graph(5))
2

julia> diameter(path_graph(5))
4

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

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

• 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)])

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 Graphs

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

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 Graphs

julia> radius(star_graph(5))
1

julia> radius(path_graph(5))
2

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 Graphs

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

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

julia> collect(edges(barbell))
13-element Array{Graphs.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{Graphs.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

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.