如何将图形转换为其等效的线图/边图/R中的交换图？

Question

我有一个图 G 及其邻接矩阵。我想将其转换为线图 L(G)，使得图 G 的节点成为 L(G) 中的边，反之亦然。
R 中是否有任何包可以执行从节点到边和边到节点的这种交换？

Answer 1

我写了一个小函数来计算折线图的邻接矩阵：

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
>