Ну, это очень хорошая проблема, но вы можете сделать несколько очень хороших трюков там. Вы можете представить график в виде квадратной матрицы 0 и 1, где количество строк и столбцов - это число вершин. Каждый 1 представляет ребро от вершины в строке до вершины в столбце. Тогда каждый возможный граф - это одно большое двоичное число с N ^ 2 битами, то есть существует 2 ^ (N ^ 2) возможных графов, сделанных из N вершин. Теперь вы можете разделить вашу проблему на две части.
- Генерация всех возможных графиков из
S - каждый график представляет собой всего одно N ^ 2-битное число.
- Затем для каждого этого графика вы расширяете матрицу на
V строк и столбцов и умножаете возможности на комбинации, где ровно один 1 в каждой V строке и столбце.
Мне нужно одно разъяснение от вас. Вы написали ... и каждая вершина из S может иметь любое количество входов и выходов Включено ли 0 в любое число ? Тогда я не понимаю, результат должен содержать ровно все вершины от V и от S Ограничение до S не имеет смысла, поскольку каждый S включается в каждое решение как вершина с ноль в и из краев. В противном случае это не все N ^ 2-битные числа, а только те, которые имеют по крайней мере один 1 в каждой строке и столбце, и тогда вы не сможете разделить свою проблему на две части, и вам придется решать S и V вместе , Тогда может быть легче сначала удовлетворить V строк и столбцов (ровно одну 1 в строке и столбце), а затем умножить каждое это решение на матричные решения S x S, которые удовлетворяют ограничению S, когда необходимо иметь по крайней мере один 1 в строке и столбце.
Вы можете экспериментировать с различными представлениями в виде списка списков для небольшого числа вершин. Вы можете попробовать array модуль, когда вы будете вычислять индекс как R+C*N, или вы можете попробовать массив массива. Для большего числа вершин можно использовать массив двоичных файлов. Вы даже можете попробовать digraph модуль здесь. Подобный подход хорошо работал для генерации графов полного замыкания в Perl, где бинарные манипуляции с использованием vec отстой. Но здесь это не так, потому что это совсем другой вопрос. Вы можете найти некоторые лучше оптимизированные презентации, но я сомневаюсь, что Erlang - лучший инструмент для такого рода вычислений очень эффективно. В любом случае число возможностей здесь растет довольно быстро, O (2 ^ (N ^ 2)), поэтому вам не нужно беспокоиться об эффективном хранении больших матриц; -)
Edit:
Посмотрите на проблему с этой точки зрения. Если у вас есть 10 вершин и предполагается, что это V и S пусто. Тогда есть 10! возможных графиков, то есть 3628800. Если это будет S, есть приблизительно 2^100, то есть 1.2677e + 30 графиков (4.0197e + 13 лет, если вы будете генерировать 1e + 09 графиков в секунду). Это означает, что для любого числа вершин, больших, чем очень мало, у вас есть очень большое количество возможных графов. Поэтому самый большой вопрос здесь, что вы будете делать с ними. Вы не можете хранить их, но если да, то вы должны хранить их очень эффективно. Двоичное поле является наиболее эффективным способом хранения графиков, сделанных из S. Вы можете найти более эффективный способ для ребер с V вершинами. Я бы сохранил его в виде массива или списка, где позиция - это вершина, из которой идет ребро, а значение - это вершина, в которую идет ребро.
Так что ваше решение сильно зависит от того, что вы будете делать с результатом. Я думаю, что вы будете каким-то образом отфильтровывать результаты, потому что я не могу представить, что вы будете делать с таким большим количеством графиков ;-) Мой совет - постарайтесь отфильтровать значимые графики как можно раньше во время генерации графиков. Это означает, что ваш подход должен определяться целью, позволяющей задействовать фильтрацию результатов в алгоритме генерации.
А по поводу эффективности Erlang для этой проблемы, если вы имеете дело с таким огромным количеством сущностей (возможных графиков), вам нужно очень осторожно управлять памятью и использованием процессора. Вы можете использовать Erlang, но для некоторых критически важных частей вы должны использовать C в NIF. Вы также должны использовать более дружественные для памяти структуры данных в виде двоичных файлов или bignums вместо списков или кортежей Вы также можете найти другие языки, такие как C, C ++, OCaml, Haskell, ... более подходящие для таких задач, требующих большого объема памяти и вычислений.