编写一个R代码来创建一个随机图的邻接矩阵并计算自环和平行边的数目

dgtucam1 于 2022-12-30 发布在其他

关注(0)|答案(2)|浏览(104)

我正在尝试编写一段代码，通过为每个顶点生成随机数量的半边，然后随机地将半边配对以创建邻接矩阵，从而创建一个随机图，我为此编写的代码如下。

# Set the number of vertices
n <- 100

# Generate the number of half-edges randomly
half_edges <- sample(0:n, n, replace = TRUE)

# Create an empty adjacency matrix
adj_matrix <- matrix(0, n, n)

# Loop through the vertices and pair their half-edges randomly
for (i in 1:n) {
  connections <- sample(1:n, half_edges[i], replace = TRUE)
  
  # Update the adjacency matrix by adding 1 to the corresponding entries
  for (j in connections) {
    adj_matrix[i, j] <- adj_matrix[i, j] + 1
    adj_matrix[j, i] <- adj_matrix[j, i] + 1
  }
}

我相信这段代码是正确的，但是我在计算平行边和自循环的数量时遇到了问题。我知道自循环的数量是对角线上的条目数，而平行边的数量将是邻接矩阵中大于1的值的数量。我试图写代码来计算这个，但是输出似乎不正确。请任何人都可以帮助我纠正下面的代码，以正确计算这些值.

#Initiate values
self_loops <- 0
parallel_edges <- 0

# Loop through the rows and columns of the adjacency matrix
for (i in 1:n) {
  for (j in 1:n) {
    # Check for self-loops
    if (i == j && adj_matrix[i, j] == 1) {
      self_loops <- self_loops + 1
    }
    # Check for parallel edges
    if (i != j && adj_matrix[i, j] > 1 && adj_matrix[j, i] > 1) {
      parallel_edges <- parallel_edges + 1
    }
  }
}
# Print the number of self-loops and parallel edges
print(paste("Number of self-loops:", self_loops))
print(paste("Number of parallel edges:", parallel_edges))

代码一直显示自循环为0，平行边的数量对于真实值来说太多了。观察邻接矩阵，我可以看到自循环和平行边的值，但是这些值没有被正确计数。任何帮助都将非常感谢。

来源：https://stackoverflow.com/questions/74950773/writing-an-r-code-to-create-an-adjacency-matrix-for-a-random-graph-and-count-the

2条答案

按热度按时间

slsn1g291#

使用igraph可以更容易、更高效地完成此操作：

library(igraph)

g <- graph_from_adjacency_matrix(adj_matrix)

sum(which_loop(g))
#> [1] 122

sum(which_multiple(g))
#> [1] 4352

赞(0）回复(0）举报 2022-12-30

k10s72fa2#

下面是我将如何修改代码以真正配对半边，并以更有效的方式完成。

set.seed(1)
n <- 5

half_edges <- sample(0:n, n, replace=T)

# make sure the total number of half-edges is even
if (sum(half_edges) %% 2) {
  
  i <- sample(n, 1)
  half_edges[i] <- half_edges[i] + 1
}

# random pairs of half-edges (i.e. edges)
he_pairs <- matrix(sample(rep(seq_len(n), half_edges)), ncol=2)
# sort the pairs so that we will only fill the upper triangle of 
#   the adjacency matrix
he_pairs <- t(apply(he_pairs, 1, sort))
#      [,1] [,2]
# [1,]    5    5
# [2,]    2    4
# [3,]    2    5
# [4,]    2    5

逐边填充邻接矩阵是相当慢的，所以我在这里一次填充更多的边，特别是所有的 * 第一个 （即所有唯一边和复制边的第一个副本）， 第二个 *（复制边的第二个副本），...边的副本在一起。由于图应该是无向的，我们只处理矩阵的上三角形，然后将其复制到下三角形中。

# Create an empty adjacency matrix
adj_matrix <- matrix(0, n, n)

# make a copy to work with
hep <- he_pairs
i <- 1
while (nrow(hep) > 0) {  # as long as there are unprocessed edges
  
  dup <- duplicated(hep)
  # process only first instances of each edge at this step
  pairs_now <- hep[!dup, , drop=F]
  adj_matrix[pairs_now] <- i
  # keep only duplicated edges for next loop (i.e. remove 
  #   those processed in this step)
  hep <- hep[dup, , drop=F]
  i <- i + 1
}

# copy the upper triangle of the adjacency matrix to its lower triangle
#   (make it symmetric)
adj_matrix[lower.tri(adj_matrix)] <- t(adj_matrix)[lower.tri(adj_matrix)]
#      [,1] [,2] [,3] [,4] [,5]
# [1,]    0    0    0    0    0
# [2,]    0    0    0    1    2
# [3,]    0    0    0    0    0
# [4,]    0    1    0    0    0
# [5,]    0    2    0    0    1

这样你就可以计算出自循环和平行边的数量（虽然我不完全确定你是如何定义后者的）：

## From the adjacency matrix:
# number of self-loops
sum(diag(adj_matrix))
# [1] 1
# number of parallel edges
sum((adj_matrix - as.logical(adj_matrix))[upper.tri(adj_matrix, diag=T)])
# [1] 1

## OR using edges:
# number of self-loops
sum(he_pairs[, 1] == he_pairs[, 2])
# number of parallel edges
sum(duplicated(he_pairs))

赞(0）回复(0）举报 2022-12-30

我来回答

编写一个R代码来创建一个随机图的邻接矩阵并计算自环和平行边的数目

2条答案

相关问题

热门标签

最新问答