Come convertire il grafico nel suo equivalente Grafico a linee / Grafico bordi / Grafico di interscambio in R? - r, grafico, nodi, adiacenza-matrice, spigoli

Ho un grafico G e la sua matrice di adiacenza. Voglio convertirlo in Line Graph L (G) in modo tale che i nodi del grafico G divengano bordi in L (G) e viceversa.
Esiste un pacchetto in R che può eseguire tale interscambio dai nodi ai bordi e ai bordi ai nodi?

risposte:

Ho scritto una piccola funzione che calcola la matrice di adiacenza del grafico a linee:

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)
}

Esempio:

> 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
>

make_line_graph dal igraph pacchetto converte il grafico nel grafico a linee corrispondente.

Quindi usando la matrice di adiacenza dall'alto

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