Создание случайной группы DAG

Ответ 1

Я приготовил программу 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;
}

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

Ответ 2

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

Аналогичным подходом было бы произвольное упорядочение ваших узлов, а затем рассматривать ребра из node x в y только тогда, когда x < у. Это ограничение также должно получить вашу 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" ), и мы можем выбрать либо иметь границу между ними, либо нет.

Ответ 3

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

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

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

Ответ 4

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

(В дальнейшем я использовал V для числа вершин в порожденном графе и E для числа ребер и предположим, что E & le; 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.

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

• порождать два числа в диапазоне [0, V);
• отклонять их, если они равны;
• замените их, если первое больше;
• отклонить их, если они сгенерировали их раньше.

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

алгоритм выборки коллектора позволяет нам делать это в пространстве O (E), поскольку мы можем вывести конечные точки k ^th от значения k. Следовательно, нам фактически не нужно создавать вектор-источник. Однако для этого все еще требуется время O (V ²).

В качестве альтернативы можно выполнить 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 ²). Фактически, это может быть улучшено до 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 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 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;
}

Ответ 5

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

Ответ 6

Недавно я попробовал повторить принятый ответ и обнаружил, что он индетерминирован. Если вы не применяете параметр 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
}

Ответ 7

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

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

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

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