similarity_metrics: Metrics for spanning tree comparisson.

In jakobbossek/rmoco: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem

Metrics for spanning tree comparisson.

Description

Functions which expect two (spanning) trees and return a measure of similiarity between those. Function getNumberOfCommonEdges returns the (normalized) number of shared edges and function getSizeOfLargestCommonSubtree returns the (normalized) size of the largest connected subtree which is located in both trees.

Usage

getNumberOfCommonEdges(x, y, n = NULL, normalize = TRUE)

getSizeOfLargestCommonSubtree(x, y, n = NULL, normalize = TRUE)

Arguments

x	[matrix(2, n)] First spanning tree represented as a list of edges.
y	[matrix(2, n)] Second spanning tree represented as a list of edges.
n	[integer(1) | NULL] Number of nodes of the graph. Defaults to length(x).
normalize	[logical(1)] Should measure be normalized to [0, 1] by devision through the number of edges? Default is TRUE.

Value

[numeric(1)] Measure

Examples

# Here we generate two random spanning trees of a complete
# graph with 10 nodes
set.seed(1)
st1 = prueferToEdgeList(sample(1:10, size = 8, replace = TRUE))
st2 = prueferToEdgeList(sample(1:10, size = 8, replace = TRUE))
# Now check the number of common edges
NCE = getNumberOfCommonEdges(st1, st2)
# And the size of the largest common subtree
SLS = getSizeOfLargestCommonSubtree(st1, st2)

jakobbossek/rmoco documentation built on March 21, 2023, 9:09 p.m.