graph.edit.distance: Calculate Graph Edit Distance (Pure R Implementation)

In dgraphs: Data-Derived Graph Construction Utilities

Calculate Graph Edit Distance (Pure R Implementation)

Description

Computes the graph edit distance between two weighted graphs with identical vertex sets using a pure R implementation. This function considers edge insertions, deletions, and weight modifications.

Usage

graph.edit.distance(
  graph1.adj.list,
  graph1.weights,
  graph2.adj.list,
  graph2.weights,
  edge.cost = 1,
  weight.cost.factor = 0.1
)

Arguments

graph1.adj.list	A list of integer vectors representing the adjacency list of the first graph. Each element contains the neighbors of the corresponding vertex.
graph1.weights	A list of numeric vectors representing the edge weights of the first graph. Must have the same structure as graph1.adj.list.
graph2.adj.list	A list of integer vectors representing the adjacency list of the second graph.
graph2.weights	A list of numeric vectors representing the edge weights of the second graph.
edge.cost	A positive numeric scalar representing the cost of adding or removing an edge (default: 1).
weight.cost.factor	A non-negative numeric scalar representing the factor to scale weight differences (default: 0.1).

Details

The graph edit distance is calculated as:

• For edges present in one graph but not the other: edge.cost

• For edges present in both graphs with different weights: abs(weight1 - weight2) * weight.cost.factor

Both graphs must have the same number of vertices. The function assumes undirected graphs.

Value

A non-negative numeric value representing the graph edit distance between the two input graphs.

Examples

# Create two simple graphs
graph1.adj <- list(c(2, 3), c(1, 3), c(1, 2))
graph1.wts <- list(c(1, 2), c(1, 3), c(2, 3))

graph2.adj <- list(c(2, 3), c(1, 3), c(1, 2))
graph2.wts <- list(c(1.5, 2), c(1.5, 2.5), c(2, 2.5))

# Calculate distance
dist <- graph.edit.distance(graph1.adj, graph1.wts,
                           graph2.adj, graph2.wts)
print(dist)  # Weight differences only

dgraphs documentation built on Aug. 21, 2026, 1:08 a.m.