# Generating combinations that fulfill certain restrictions for graphs

I am working with graphs, let's say I have 4 nodes, named A, B, C, D, each node has to be connected a certain number of times to the other nodes.

A: 3, B: 3, C: 2, D: 2

This means that A and B are connected three times and C and D two times. All the possibles pairs generated are the following:

(A, B), (A, C), (A, D), (B, C), (B, D), (C, D)

Now I need to generate all combinations of 5 pairs where A and B appear three times and C and D two.

This is an example of an acceptable combination: (A, B), (A, C), (A, D), (B, C), (B, D)

Here the set fulfills this condition: A: 3, B: 3, C: 2, D: 2 With A and B appearing three times and C and D only two.

This is an example of an unacceptable combination: (A, B), (A, C), (A, D), (B, C), (C, D) Here the set doesn't fulfill this condition: A: 3, B: 3, C: 2, D: 2 With A and C appearing three times and B and D only two.

Anyone know how I could create an algorithm that gets me only the combinations of pairs that fulfill this condition?

• Since you have just $4$ nodes you can just exhaustively check all $2^6 = 64$ subsets of $\{ (A, B), (A, C), (A, D), (B, C), (B, D), (C, D) \}$. Mar 25, 2022 at 13:38
• @Andreu Please do not update the question with answers. A question should be a question, especially when there is one or more answers. You can always post an answer if you want to. Apr 21, 2022 at 12:52

Your problem is addressed in Kim, Toroczkai, Miklós, Erdős and Székely, On realizing all simple graphs with a given degree sequence.

Here is an algorithm I've coded myself that does what I asked:

import numpy as np
from itertools import chain, repeat, count, islice
from collections import Counter

def unique_combinations(iterable, r):

def repeat_chain(values, counts):
return chain.from_iterable(map(repeat, values, counts))

def unique_combinations_from_value_counts(values, counts, r):
n = len(counts)
indices = list(islice(repeat_chain(count(), counts), r))
if len(indices) < r:
return
while True:
yield tuple(values[i] for i in indices)
for i, j in zip(reversed(range(r)), repeat_chain(reversed(range(n)), reversed(counts))):
if indices[i] != j:
break
else:
return
j = indices[i] + 1
for i, j in zip(range(i, r), repeat_chain(count(j), counts[j:])):
indices[i] = j

values, counts = zip(*Counter(iterable).items())
return unique_combinations_from_value_counts(values, counts, r)

def havel_hakimi(deg_sequence, edge_list=[], i=0):

node = deg_sequence.pop(0)
a = []
for j in range(len(deg_sequence)):
if deg_sequence[j] <= 2:
factor = deg_sequence[j]
else:
factor = 2
a += factor * [(i, j+i+1)]

i += 1
for combination in unique_combinations(a, node):
deg_sequence_copy = deg_sequence.copy()
edge_list_copy = edge_list.copy()
edge_list_copy += combination
subtract_vertices_list = [item[1]-i for item in combination]

for vertex in subtract_vertices_list:
deg_sequence_copy[vertex] -= 1

while deg_sequence_copy[-1] == 0 and len(deg_sequence_copy) > 1:
deg_sequence_copy.pop(-1)

if not all(v == 0 for v in deg_sequence_copy) and len(deg_sequence_copy) > 1:
havel_hakimi(deg_sequence_copy, edge_list_copy,  i)

if all(v == 0 for v in deg_sequence_copy):
print(edge_list_copy)
pass

else:
pass
$$$$
`