Эффективный способ генерации графов из исходных узлов

Question

Допустим, у меня есть график G, и вокруг каждого узла у меня есть несколько исходных узлов xs.Мне нужно создать новый график G' с использованием xs=[[a, b, c], [d, e], [f]] узлов, чтобы они не конфликтовали с серыми пончиками, как показано на рисунке ниже.

Ожидаемый результат G' равен [[a, d, f], [a, e, f], [b, e, f]];все остальные конфликтуют с серым пончиком.

В настоящее время я решил эту проблему, взяв все перестановки и комбинации узлов xs.Это работает для меньшего числа узлов, но, поскольку мое число узлов xs увеличивается с увеличением графика G, вскоре это становится комбинацией сотен тысяч комбинаций.

Я ищу эффективный алгоритм, которыйпоможет мне ускорить процесс и получить все неконфликтующие графики с минимальным количеством итераций.

Answer 1

У вас есть довольно очевидный минимальный набор ребер для каждого этапа вашего пути. Они оба необходимы и достаточны для вашего решения. Для удобства обозначения я обозначу исходный граф X - Y - Z. Ваши соответствующие узлы G '

X a b c
Y d f
Z f

Вы делаете это в два этапа:

Для каждого ребра в G вы должны проверить правильность каждого возможного ребра в G`. Это состоит из

X--Y   [a, b, c] X [d, e]
    a total of 6 edges; 3 qualify: set XY = [a--d, a--e, b--d]
Y--Z   [d, e] X [f]
    a total of 2 edges; 2 qualify: set YZ = [d--f, e--f]

Теперь вам нужно только сгенерировать все комбинации XY x YZ, где совпадают узлы Y. Если вы сортируете списки по «внутреннему» узлу, вы можете сделать это очень быстро, как

[a--d, b--d] x [d--f]
[a--e] x [e--f]

В большинстве современных языков есть модули для выполнения комбинаций, поэтому код будет достаточно коротким.

Это тебя заводит?