1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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) \}$. $\endgroup$
    – Steven
    Mar 25, 2022 at 13:38
  • $\begingroup$ @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. $\endgroup$
    – John L.
    Apr 21, 2022 at 12:52

2 Answers 2

2
$\begingroup$

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

$\endgroup$
0
0
$\begingroup$

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
```
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.