kruskal: Given a weight matrix, generate its maximum weight forest

In BNSL: Bayesian Network Structure Learning

Description

The function lists the edges of an forest generated by Kruskal's algorithm given its weight matrix in which each weight should be symmetric but may be negative. The forest is a spanning tree if the elements of the matrix take positive values.

Usage

 kruskal(W)

Arguments

W

a matrix.

Value

A matrix object of size n x 2 for matrix size n x n in which each row expresses an edge when the vertexes are expressed by 1 through n.

Author(s)

Joe Suzuki and Jun Kawahara

References

[1] Suzuki. J. “The Bayesian Chow-Liu algorithms", In the sixth European workshop on Probabilistic Graphical Models, pp. 315-322, Granada, Spain, Sept.2012.

Examples

library(igraph)
library(bnlearn)
df=asia
mi.mat=mi_matrix(df)
edge.list=kruskal(mi.mat)
edge.list
g=graph_from_edgelist(edge.list, directed=FALSE)
V(g)$label=colnames(df)
plot(g)

Example output

Loading required package: bnlearn

Attaching package: 'bnlearn'

The following object is masked from 'package:stats':

    sigma

Loading required package: igraph

Attaching package: 'igraph'

The following objects are masked from 'package:bnlearn':

    compare, degree, path, subgraph

The following objects are masked from 'package:stats':

    decompose, spectrum

The following object is masked from 'package:base':

    union

     [,1] [,2]
[1,]    6    3
[2,]    2    4
[3,]    2    5
[4,]    4    6
[5,]    6    7
[6,]    5    8

BNSL documentation built on May 2, 2019, 7:58 a.m.