Writing an R code to create an adjacency matrix for a random graph and count the number of self-loop-CodePudding

I am trying to write the code which creates a random graph by forming a random number of half-edges for each vertex, then randomly pairing the half-edges to create an adjacency matrix. The code I have written for this is as following.

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

I believe this code is correct, however I am having problems counting the number of parallel edges and self-loops. I understand the number of self-loops will be the number of entries in the diagonal, and the number of parallel edges will be the number of values greater than 1 in the adjacency matrix. I have attempted to write the code to compute this however the output does not seem to be correct. Please can anyone help me correct the following code to correctly calculate these values.

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

The code keeps displaying self-loops as 0 and the number of parallel edges is far too high for what the true value must be. Observing the adjacency matrix I can see there are values for self-loops and parallel edges however these are not being counted correctly. Any help would be greatly appreciated.

CodePudding user response：

This is much easier and more efficient to do using igraph:

library(igraph)

g <- graph_from_adjacency_matrix(adj_matrix)

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

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

CodePudding user response：

Here's how I would modify the code to really pair the half-edges and also do it in a more efficient way.

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

Filling the adjacency matrix edge by edge is rather slow so here I do it by more edges at once, specifically all first (i.e. all unique edges and first copies of duplicated edges), second (second copies of duplicated edges), ... copies of edges together. Since the graph should be undirected, we only work with the upper triangle of the matrix and copy it into the lower triangle afterwards.

# 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

And this way you can compute the numbers of self-loops and parallel edges (although I am not completely sure how you define the latter):

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