main.R

library(igraph)


generate_graph <- function(num_nodes, del_probability) {
  # Make sure the igraph package is available
  if (!requireNamespace("igraph", quietly = TRUE)) {
    stop("Please install the 'igraph' package.")
  }
  

  # Create a list of nodes
  nodes <- 1:num_nodes

  # Create all possible directed edges between different nodes
  # (This creates a complete directed graph, i.e. for every pair (i,j), i != j, we have an edge.)
  edge_list <- expand.grid(from = nodes, to = nodes)
  edge_list <- edge_list[edge_list$from != edge_list$to, ]

  # Shuffle the edge list so that removals happen in random order
  edge_list <- edge_list[sample(nrow(edge_list)), ]

  # Initially, all edges are present.
  keep <- rep(TRUE, nrow(edge_list))

  # Each node in a complete directed graph (without self-loops) has:
  #   - (num_nodes - 1) outgoing edges and
  #   - (num_nodes - 1) incoming edges,
  # so the total (undirected) degree is 2 * (num_nodes - 1)
  degrees <- rep(2 * (num_nodes - 1), num_nodes)

  # Process each edge: with probability del_probability, try to remove the edge
  for (i in 1:nrow(edge_list)) {
    if (runif(1) < del_probability) {
      source_node <- edge_list$from[i]
      target_node <- edge_list$to[i]

      # Removing the edge would reduce the degree (connection count) of both nodes by 1.
      # We only remove the edge if both nodes will still have at least one connection.
      if (degrees[source_node] > 1 && degrees[target_node] > 1) {
        keep[i] <- FALSE         # Mark the edge as removed
        degrees[source_node] <- degrees[source_node] - 1
        degrees[target_node] <- degrees[target_node] - 1
      }
    }
  }

  # Keep only the edges that were not removed
  final_edges <- edge_list[keep, ]

  # Build the igraph object using the final edge list.
  # We convert the nodes to characters for naming.
  g <- graph_from_data_frame(final_edges, directed = TRUE,
                             vertices = data.frame(name = as.character(nodes)))

  return(g)
}


plot(generate_graph(500, 0.4))