R代码生成随机图邻接矩阵及自环、平行边计数修正求助

问题背景 #

我通过R代码生成随机图邻接矩阵：为每个顶点生成随机数量的半边，再随机配对半边构建矩阵。生成代码可正常运行，但统计自环和平行边的代码结果错误——自环数显示为0，平行边数远高于实际值。

原生成代码 #

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

原统计代码（存在错误） #

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

错误原因分析 #

1. 自环统计错误：生成代码中，当顶点i连接到自身时，会同时执行adj_matrix[i,i] +=1和adj_matrix[i,i] +=1，导致对角线值为偶数。原代码仅判断adj_matrix[i,j] ==1，永远无法匹配到自环，所以统计结果为0。
2. 平行边统计错误：原代码遍历所有i≠j的条目，会重复统计同一顶点对（比如i=1,j=2和i=2,j=1都会被计数），且直接累加次数，导致结果远高于实际值。

修正后的统计代码 #

统计总自环数与总平行边数量（所有重复边的总数） #

# 初始化统计值
self_loops_total <- 0
parallel_edges_total <- 0

for (i in 1:n) {
  # 每个自环对应对角线值加2，所以自环数量为值除以2
  self_loops_total <- self_loops_total + (adj_matrix[i, i] %/% 2)
  
  # 遍历上三角区域，避免重复统计顶点对
  for (j in (i+1):n) {
    # 矩阵值即为该顶点对的平行边数量
    parallel_edges_total <- parallel_edges_total + adj_matrix[i, j]
  }
}

print(paste("总自环数:", self_loops_total))
print(paste("总平行边数量（所有重复边总数）:", parallel_edges_total))

统计有自环的顶点数与存在平行边的顶点对数量 #

# 初始化统计值
self_loop_vertices <- 0
parallel_edge_pairs <- 0

for (i in 1:n) {
  # 对角线值>0说明该顶点存在自环
  if (adj_matrix[i, i] > 0) {
    self_loop_vertices <- self_loop_vertices + 1
  }
  
  # 遍历上三角区域，避免重复统计顶点对
  for (j in (i+1):n) {
    # 值>1说明该顶点对存在平行边
    if (adj_matrix[i, j] > 1) {
      parallel_edge_pairs <- parallel_edge_pairs + 1
    }
  }
}

print(paste("有自环的顶点数:", self_loop_vertices))
print(paste("存在平行边的顶点对数量:", parallel_edge_pairs))

内容的提问来源于stack exchange，提问作者scily09