Генерация случайного DAG

Я решаю задачу на ориентированном ациклическом графе.

Но у меня возникают проблемы при тестировании моего кода на некоторых ориентированных ациклических графах. Графики теста должны быть большими, и (очевидноациклический.

Я много пытался написать код для генерации ациклических ориентированных графов. Но я терпел неудачу каждый раз.

Есть ли какой-нибудь существующий метод для генерации ациклических ориентированных графов, который я мог бы использовать?

21

Решение

Я приготовил C-программу, которая делает это. Ключ должен «ранжировать» узлы, и только рисовать ребра от узлов с более низким рейтингом до более высоких.

Программа, которую я написал, печатает в язык DOT.

Вот сам код с комментариями, объясняющими, что это значит:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MIN_PER_RANK 1 /* Nodes/Rank: How 'fat' the DAG should be.  */
#define MAX_PER_RANK 5
#define MIN_RANKS 3    /* Ranks: How 'tall' the DAG should be.  */
#define MAX_RANKS 5
#define PERCENT 30     /* Chance of having an Edge.  */

int main (void)
{
int i, j, k,nodes = 0;
srand (time (NULL));

int ranks = MIN_RANKS
+ (rand () % (MAX_RANKS - MIN_RANKS + 1));

printf ("digraph {\n");
for (i = 0; i < ranks; i++)
{
/* New nodes of 'higher' rank than all nodes generated till now.  */
int new_nodes = MIN_PER_RANK
+ (rand () % (MAX_PER_RANK - MIN_PER_RANK + 1));

/* Edges from old nodes ('nodes') to new ones ('new_nodes').  */
for (j = 0; j < nodes; j++)
for (k = 0; k < new_nodes; k++)
if ( (rand () % 100) < PERCENT)
printf ("  %d -> %d;\n", j, k + nodes); /* An Edge.  */

nodes += new_nodes; /* Accumulate into old node set.  */
}
printf ("}\n");
return 0;
}

И вот график, сгенерированный из тестового прогона:

Случайно сгенерированный DAG

46

Другие решения

Ответ на https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs применяется: если у вас есть матричное представление смежности ребер вашего графа, то, если матрица имеет нижнюю треугольную форму, это DAG по необходимости.

Аналогичным подходом было бы взять произвольный порядок ваших узлов, а затем рассмотреть ребра из узла Икс в Y только когда Икс < Y. Это ограничение также должно получить ваш DAGness по построению. Сравнение памяти будет одним из произвольных способов упорядочения узлов, если вы используете структуры для представления узлов.

По сути, псевдокод будет выглядеть примерно так:

for(i = 0; i < N; i++) {
for (j = i+1; j < N; j++) {
maybePutAnEdgeBetween(i, j);
}
}

где N это количество узлов в вашем графике.

Псевдокод предполагает, что число потенциальных DAG, заданных N узлами, равно

2^(n*(n-1)/2),

так как есть

n*(n-1)/2

упорядоченные пары («N выбирают 2»), и мы можем выбрать, иметь ли грань между ними или нет.

10

Вы можете сгенерировать случайный ориентированный граф, а затем выполнить цикл поиска в глубину. Когда вы найдете цикл, разбейте его, удалив ребро.

Я думаю, что это худший случай O (VE). Каждый DFS занимает O (V), и каждый удаляет по крайней мере одно ребро (так что макс. E)

Если вы генерируете ориентированный граф путем равномерного случайного выбора всех V ^ 2 возможных ребер, а DFS в случайном порядке и удаляете случайное ребро — это даст вам равномерное распределение (или, по крайней мере, близкое к нему) по всем возможным дагам.

3

Итак, чтобы попытаться соединить все эти разумные ответы:

(Далее я использовал V для числа вершин в сгенерированном графе и E для количества ребер, и мы предполагаем, что E ≤ V (V-1) / 2.)

Лично я думаю, что самый полезный ответ — в комментарии Флавиуса, который указывает на код на http://condor.depaul.edu/rjohnson/source/graph_ge.c. Этот код действительно прост, и его удобно описать комментарием, который я воспроизвожу:

To generate a directed acyclic graph, we first
generate a random permutation dag[0],...,dag[v-1].
(v = number of vertices.)
This random permutation serves as a topological
sort of the graph. We then generate random edges of the
form (dag[i],dag[j]) with i < j.

Фактически, код генерирует количество ребер запроса путем многократного выполнения следующего:

  1. генерировать два числа в диапазоне [0, V);
  2. отвергни их, если они равны;
  3. поменяйте местами, если первый больше;
  4. отвергнуть их, если они уже были созданы.

Проблема с этим решением состоит в том, что, когда E становится близким к максимальному числу ребер V (V-1) / 2, тогда алгоритм становится все медленнее и медленнее, потому что он должен отклонять все больше и больше ребер. Лучшим решением было бы сделать вектор всех V (V-1) / 2 возможных ребер; случайно перемешать это; и выберите первые (запрошенные ребра) ребра в перетасованном списке.

алгоритм отбора проб пласта давайте сделаем это в пространстве O (E), так как мы можем вывести конечные точки kго край от значения к. Следовательно, нам не нужно создавать исходный вектор. Тем не менее, он все еще требует O (V2Время

В качестве альтернативы можно сделать Fisher-Yates shuffle (или, если хотите, Knuth shuffle), останавливается после E итераций. В версии FY shuffle, представленной в Википедии, это даст конечные записи, но алгоритм работает так же хорошо в обратном направлении:

// At the end of this snippet, a consists of a random sample of the
// integers in the half-open range [0, V(V-1)/2). (They still need to be
// converted to pairs of endpoints).
vector<int> a;
int N = V * (V - 1) / 2;
for (int i = 0; i < N; ++i) a.push_back(i);
for (int i = 0; i < E; ++i) {
int j = i + rand(N - i);
swap(a[i], a[j]);
a.resize(E);

Это требует только O (E) времени, но это требует O (N)2) пространство. Фактически, это может быть улучшено до пространства O (E) с некоторыми хитростями, но фрагмент кода SO слишком мал, чтобы содержать результат, поэтому я предоставлю более простой в пространстве O (E) и O (E log E Время Я предполагаю, что есть класс DAG с хотя бы:

class DAG {
// Construct an empty DAG with v vertices
explicit DAG(int v);

// Add the directed edge i->j, where 0 <= i, j < v
void add(int i, int j);
};

Теперь здесь идет:

// Return a randomly-constructed DAG with V vertices and and E edges.
// It's required that 0 < E < V(V-1)/2.
template<typename PRNG>
DAG RandomDAG(int V, int E, PRNG& prng) {
using dist = std::uniform_int_distribution<int>;
// Make a random sample of size E
std::vector<int> sample;
sample.reserve(E);
int N = V * (V - 1) / 2;
dist d(0, N - E);  // uniform_int_distribution is closed range
// Random vector of integers in [0, N-E]
for (int i = 0; i < E; ++i) sample.push_back(dist(prng));
// Sort them, and make them unique
std::sort(sample.begin(), sample.end());
for (int i = 1; i < E; ++i) sample[i] += i;
// Now it's a unique sorted list of integers in [0, N-E+E-1]
// Randomly shuffle the endpoints, so the topological sort
// is different, too.
std::vector<int> endpoints;
endpoints.reserve(V);
for (i = 0; i < V; ++i) endpoints.push_back(i);
std::shuffle(endpoints.begin(), endpoints.end(), prng);
// Finally, create the dag
DAG rv;
for (auto& v : sample) {
int tail = int(0.5 + sqrt((v + 1) * 2));
int head = v - tail * (tail - 1) / 2;
rv.add(head, tail);
}
return rv;
}
3

Очень простой подход:

  1. Произвольно назначьте ребра путем итерации по индексам нижней диагональной матрицы (как предложено по ссылке выше: https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs)

  2. Это даст вам DAG, возможно, с более чем одним компонентом. Вы можете использовать структуру данных Disjoint-set, чтобы предоставить вам компоненты, которые затем могут быть объединены путем создания ребер между компонентами.

Непересекающиеся множества описаны здесь: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

2

Создать график с n узлы и ребро между каждой парой узлов n1 а также n2 если n1 != n2 а также n2 % n1 == 0,

1

Недавно я попытался повторно реализовать принятый ответ и обнаружил, что он является неопределенным. Если вы не применяете параметр min_per_rank, вы можете получить граф с 0 узлами.

Чтобы предотвратить это, я обернул циклы for в функцию, а затем проверил, чтобы после каждого ранга min_per_rank был доволен. Вот реализация JavaScript:

https://github.com/karissa/random-dag

И некоторый псевдо-C-код, который заменит основной цикл принятого ответа.

int pushed = 0

int addRank (void)
{
for (j = 0; j < nodes; j++)
for (k = 0; k < new_nodes; k++)
if ( (rand () % 100) < PERCENT)
printf ("  %d -> %d;\n", j, k + nodes); /* An Edge.  */

if (pushed < min_per_rank) return addRank()
else pushed = 0

return 0
}
1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector