Ответ 1
Может кто-то порекомендовать мне схему высокого уровня, которая позволяет мне генерировать сильно связанные, равномерно распределенные случайные диаграфы?
У меня была аналогичная проблема, генерирующая деревья выражений для тестовых данных. Я обнаружил, что если вы узнаете, как подсчитывать уникальные деревья, проблема становится легкой. Я имею в виду, что я нашел для полных двоичных деревьев с N внутренними узлами число уникальных деревьев на основе N - это Каталонские числа. Тогда для двоичных деревьев, имеющих унарные ветки с N суммарными узлами, число уникальных деревьев на основе N есть Числа Моцкина.
Затем я нашел Онлайновая энциклопедия целых последовательностей. Поэтому, если вы знаете значение N, которое может однозначно идентифицировать граф, и вы знаете соответствующее количество уникальных графов для этого N и поместите эти подсчеты в поиск OEIS, вы должны вернуть страницу, которая поможет вам в вашем поиске. например Каталонские номера для полных двоичных деревьев или Номера Моцкина для регулярная двоичная структура. По пути я обнаружил, что одним из ключей к их созданию было отношение повторения.
Или вы можете использовать ключевые слова в поиске, но это может не получить точный хит. Я только нашел числа Моцкина, используя последовательность чисел, а не через ключевые слова.
Вот запрос OEIS для сильно связанного орграфа
Теперь, если вы знаете счетчик для данного N, и вы либо генерируете все графики для данного N, либо можете иметь один к одному соответствие между значением и графиком, тогда вы просто генерируете случайные целые числа и получаете/генерируете соответствующий граф, Если я правильно понимаю вашу проблему, это должно решить ее.
Мое лучшее предположение для последовательности OEIS для этого вопроса:
Число ациклических орграфов с n немаркированными узлами. A003087
Что имеет ссылку на Равномерная случайная генерация больших ациклических орграфов
TL; DR
Для некоторой связанной истории см. мой вопрос: Улучшение алгоритма для перечисления бинарных деревьев