I'm having trouble conceptualizing my problem. But essentially if I have m nodes, and want to generate no more than n connections for each node. I also want to ensure that there is a always a path from each node to any other node. I don't care about cycles.
I don't have the proper vocabulary to find this problem already existing though I'm sure it has to exist somewhere.
Does anyone know of a place where this problem is explained, or know the answer themselves?
The simplest way is to construct a Spanning Tree to ensure that all nodes are connected, then add edges that don't violate the maximum number of edges per node until you have the target number of them. In pseudocode:
// nodes[] is a list of all m nodes in our graph
connected_nodes = nodes[0];
// add nodes one by one until all are in the spanning tree
for next_node = 1 to (m-1)
repeat
select node connected_nodes[k] // randomly, nearest, smallest degree, whatever
until degree(k) < n // make sure node to connect to does not violate max degree
add edge between nodes[next_node] and new node connected_nodes[k]
add nodes[next_node] to connected_nodes[]
end for
// the graph is now connected, add the desired number of edges
for e = m+1 to desired_edge_count
select 2 nodes i,j from connected_nodes, each with degree < n
add edge between nodes i and j
end for