如何将图形转换为 R 中的等效线图/边图/交换图?
How to convert graph to its equivalent Line Graph/ Edge Graph/ Interchange graph in R?
我有一个图 G 及其邻接矩阵。我想将它转换为折线图 L(G),以便图 G 的节点成为 L(G) 中的边,反之亦然。
R 中是否有任何包可以执行从节点到边缘和边缘到节点的这种交换?
我写了一个小函数来计算折线图的邻接矩阵:
LineGraph <- function(A) # A: adjacency matrix
{
n <- nrow(A)
m <- sum(A)/2 # m: number of edges
X <- lower.tri(A)*A # X: still the adjacency matrix,
X[which(X!=0)] <- 1:m # but edges are numbered
p <- which(X!=0)-1
edgeNames <- apply(matrix(c((p %% n)+1,p %/% n+1),m),1,
function(v){paste(sort(v),collapse=".")}) # names of the edges
X <- X + upper.tri(X)*t(X)
A.line <- matrix(0,m,m) # A.line will become the adjacency matrix of the line graph
rownames(A.line) <- edgeNames
colnames(A.line) <- edgeNames
apply(X,1,
function(x)
{
p <- which(x!=0)
q <- outer(x[p],m*(x[p]-1),"+")
A.line[c(q)] <<- 1
} )
A.line[(1:m)+m*(0:(m-1))] <- 0
return(A.line)
}
示例:
> A <- matrix( c(0,1,1,1,0,
+ 1,0,0,0,1,
+ 1,0,0,1,0,
+ 1,0,1,0,1,
+ 0,1,0,1,0), 5, 5 )
> LineGraph(A)
1.2 1.3 1.4 2.5 3.4 4.5
1.2 0 1 1 1 0 0
1.3 1 0 1 0 1 0
1.4 1 1 0 0 1 1
2.5 1 0 0 0 0 1
3.4 0 1 1 0 0 1
4.5 0 0 1 1 1 0
>
igraph
包中的 make_line_graph
将图形转换为其对应的折线图。
所以使用上面的邻接矩阵
library(igraph)
m <- make_line_graph(graph_from_adjacency_matrix(A, mode="undirected"))
as_adjacency_matrix(m, sparse=FALSE)
# [,1] [,2] [,3] [,4] [,5] [,6]
#[1,] 0 1 1 1 0 0
#[2,] 1 0 1 0 1 0
#[3,] 1 1 0 0 1 1
#[4,] 1 0 0 0 0 1
#[5,] 0 1 1 0 0 1
#[6,] 0 0 1 1 1 0
R 中是否有任何包可以执行从节点到边缘和边缘到节点的这种交换?
我写了一个小函数来计算折线图的邻接矩阵:
LineGraph <- function(A) # A: adjacency matrix
{
n <- nrow(A)
m <- sum(A)/2 # m: number of edges
X <- lower.tri(A)*A # X: still the adjacency matrix,
X[which(X!=0)] <- 1:m # but edges are numbered
p <- which(X!=0)-1
edgeNames <- apply(matrix(c((p %% n)+1,p %/% n+1),m),1,
function(v){paste(sort(v),collapse=".")}) # names of the edges
X <- X + upper.tri(X)*t(X)
A.line <- matrix(0,m,m) # A.line will become the adjacency matrix of the line graph
rownames(A.line) <- edgeNames
colnames(A.line) <- edgeNames
apply(X,1,
function(x)
{
p <- which(x!=0)
q <- outer(x[p],m*(x[p]-1),"+")
A.line[c(q)] <<- 1
} )
A.line[(1:m)+m*(0:(m-1))] <- 0
return(A.line)
}
示例:
> A <- matrix( c(0,1,1,1,0,
+ 1,0,0,0,1,
+ 1,0,0,1,0,
+ 1,0,1,0,1,
+ 0,1,0,1,0), 5, 5 )
> LineGraph(A)
1.2 1.3 1.4 2.5 3.4 4.5
1.2 0 1 1 1 0 0
1.3 1 0 1 0 1 0
1.4 1 1 0 0 1 1
2.5 1 0 0 0 0 1
3.4 0 1 1 0 0 1
4.5 0 0 1 1 1 0
>
igraph
包中的 make_line_graph
将图形转换为其对应的折线图。
所以使用上面的邻接矩阵
library(igraph)
m <- make_line_graph(graph_from_adjacency_matrix(A, mode="undirected"))
as_adjacency_matrix(m, sparse=FALSE)
# [,1] [,2] [,3] [,4] [,5] [,6]
#[1,] 0 1 1 1 0 0
#[2,] 1 0 1 0 1 0
#[3,] 1 1 0 0 1 1
#[4,] 1 0 0 0 0 1
#[5,] 0 1 1 0 0 1
#[6,] 0 0 1 1 1 0