mcMST (version 1.1.1)

similarity_metrics: 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)

Value

[numeric(1)] Measure

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.

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)