R: Optimally Sharing Cookies Within Groups of Friends

I am working with the R programming language.

Suppose there are 100 people - each person is denoted with an ID from 1:100. Each person can be friends with other people. The dataset can be represented in graph/network format and looks something like this:

# Set the seed for reproducibility
set.seed(123)

# Generate a vector of ID's from 1 to 100
ids <- 1:100

# Initialize an empty data frame to store the "from" and "to" values
edges <- data.frame(from=integer(), to=integer(), stringsAsFactors=FALSE)

# Iterate through the ID's
for(id in ids) {
    # Randomly select a minimum of 1 and a maximum of 8 neighbors for the current ID
    neighbors <- sample(ids[ids != id], size=sample(1:8, size=1))
    
    # Add a new row to the data frame for each "to" value
    for(neighbor in neighbors) {
        edges <- rbind(edges, data.frame(from=id, to=neighbor))
    }
}

As we can see, the data can be visualized to reveal the graph/network format:

library(igraph)
library(visNetwork)


# Convert the data frame to an igraph object
g <- graph_from_data_frame(edges, directed=FALSE)

# Plot the graph
plot(g)

# Optional visualization
#visIgraph(g)

Now, suppose each person in this dataset has has a certain number of cookies. This looks something like this:

set.seed(123)

cookies = data.frame(id = 1:100, number_of_cookies = c(abs(as.integer(rnorm(25, 15, 5))), abs(as.integer(rnorm(75, 5, 5)))))

Here is my question:

I want to make sure that no person in this dataset has less than 12 cookies - that is, if someone has less than 12 cookies, they can "pool" together their cookies with their neighbors (e.g. first-degree neighbors, second-degree neighbors, ... n-th degree neighbors ... until this condition is satisfied) and see if they now have more than 12 cookies
However, I also want to make sure that during this pooling process, no pooled group of friends has more than 20 cookies (i.e. this might require having to "un-pool" neighbors that were previously pooled together)
And finally, if someone is in a group with some other people - this person can not be then placed into another group (i.e. no "double dipping")

I wrote a function that takes an ID as an input and then returns the total number of cookies for this ID and all of this ID's neighbors:

library(data.table)
library(dplyr)


sum_cookies_for_id <- function(id) {
    
    # Get the connected IDs for the given ID
    connected_ids <- c(id, edges[edges$from == id | edges$to == id, "to"])
    
    # Sum the number of cookies for all connected IDs
    sum(cookies[cookies$id %in% connected_ids, "number_of_cookies"])
}

# Test the function
sum_cookies_for_id(23)

But beyond this, I am not sure how to continue.

Can someone please show me how I might be able to continue writing the code for this problem? Can Dynamic Programming be used in such an example?

Thanks!

Notes:

I think that this problem might have a "stochastic" nature - that is, depending on which ID you begin with and which other ID's you group this specific ID with ... might eventually lead to fewer or more people with less than 12 cookies
I think that writing a "greedy" algorithm that performs random groupings might be the easiest option for such a problem?
In the future, I would be interested in seeing how more "sophisticated algorithms" (e.g. Genetic Algorithm) could be used to make groupings such that the fewest number of people with less than 12 cookies are left behind.
Food for Thought: Is it possible that perhaps some pre-existing graph/network clustering algorithm could be used for this problem while taking into consideration these total/sum constraints (e.g. Louvain Community Detection)?

Recommended topics

Hot tags