Sort a list of objects depending on a field used for relationship

Question

Given the list "data" below, how can we match each element in the list to its corresponding relationship to other elements in the list, each element can only be matched once.

For example:

data = [
    {"ID": "A", "RelationIDs": ["B", "C", "D","F", "E"]},
    {"ID": "B", "RelationIDs": ["A", "E"]},
    {"ID": "C", "RelationIDs": ["D"]},
    {"ID": "D", "RelationIDs": ["C"]},
    {"ID": "E", "RelationIDs": ["A", "B"]},
    {"ID": "F", "RelationIDs": ["A", "B", "C"]},
    {"ID": "G", "RelationIDs": []},
    {"ID": "H", "RelationIDs": []},
]

The output should be:

A is reserved with F
B is reserved with E
C is reserved with D
G is reserved with H

So RelationIDs is the list of ID's that the element is allowed to be matched with, once either of the element's have been matched it cannot be matched again for another element.

Most importantly ensuring every element has a match. For example we cannot match A with B (even though they are allowed by each other) because then F would not have anything to be matched with, as by the time we check F the elements would have been.

"G" is reserved with "H" as neither of them have any existing relationship, so they can create a new relationship together.

for explanation purposes I'm assuming the output above is a match/print(). The data list can get more longer, I've included only 8 elements here. The main issue is ensuring we are matching elements in the most optimal way, we don't want to match X element with Y element, if X element has other possible matches, and Y element is only Z elements match.

Answer 1

This is a graph problem. Your data defines a graph, with one vertex for each ID, and one edge between two vertices if these two IDs have a relationship.

You are looking for a maximum marriage in this graph.

I suggest using graph library networkx:

import networkx as nx
from networkx.algorithms.matching import max_weight_matching

data = [
    {"ID": "A", "RelationIDs": ["B", "C", "D","F", "E"]},
    {"ID": "B", "RelationIDs": ["A", "E"]},
    {"ID": "C", "RelationIDs": ["D"]},
    {"ID": "D", "RelationIDs": ["C"]},
    {"ID": "E", "RelationIDs": ["A", "B"]},
    {"ID": "F", "RelationIDs": ["A", "B", "C"]},
    {"ID": "G", "RelationIDs": []},
    {"ID": "H", "RelationIDs": []},
]

G = nx.Graph()
G.add_vertices_from(d['ID'] for d in data)
G.add_edges_from((d['ID'], v) for d in data for v in d['RelationIDs'])

m = max_weight_matching(G, maxcardinality=True)

print(m)
# {('D', 'C'), ('E', 'A'), ('F', 'B')}