La génération aléatoire DAG

La réponse à https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs s'applique: si vous avez une matrice de contiguïté de la représentation de la bords de votre graphe, si la matrice est triangulaire inférieure, c'est un groupe de nécessité.

Une approche similaire serait de prendre un arbitraire de la commande de vos nœuds, et d'examiner ensuite les bords de nœud x à y uniquement lorsque x < y. Cette contrainte devrait également obtenir votre DAGness par construction. Mémoire de comparaison, ce serait une façon arbitraire pour commander votre nœuds si vous êtes en utilisant des structures pour représenter les nœuds.

Fondamentalement, le pseudocode serait quelque chose comme:

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

où N est le nombre de nœuds dans votre graphique.

Le pseudocode suggère que le nombre potentiel de DAGs, étant donné N nœuds, est

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

puisqu'il y a

n*(n-1)/2

paires commandées ("N choisir 2"), et l'on peut choisir soit de prendre la tête entre eux ou pas.

Donc, pour essayer de mettre tous ces des réponses raisonnables ensemble:

(Dans la suite, j'ai utilisé V pour le nombre de sommets dans le graphique généré, et E pour le nombre d'arêtes, et nous supposons que E ≤ V(V-1)/2.)

Personnellement, je pense que le plus utile de la réponse est dans un commentaire, par Flavius, qui indique le code à http://condor.depaul.edu/rjohnson/source/graph_ge.c. Ce code est très simple, et il est idéalement décrite par un commentaire, que je reproduis:

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.

En fait, ce que fait le code est de générer de la demande de nombre d'arêtes de façon répétée en procédant de la manière suivante:

1. générer deux nombres dans l'intervalle [0, V);
2. les rejeter si elles sont équivalentes;
3. swap si la première est plus grande;
4. les rejeter si elle a généré avant.

Le problème avec cette solution est que comme E est ferme pour le nombre maximum d'arêtes V(V-1)/2, alors l'algorithme devient plus lent et plus lent, car il a à rejeter de plus en plus et les bords. Une meilleure solution serait de faire un vecteur de V(V-1)/2 arêtes; de façon aléatoire shuffle, et sélectionnez le premier (demandé bords) les bords de la mélangées liste.

La réservoir algorithme d'échantillonnage nous permet de faire cela dans l'espace de O(E), puisque nous pouvons en déduire les points de terminaison de la k^ème de bord à partir de la valeur de k. Par conséquent, nous n'ont pas réellement de créer le vecteur source. Cependant, il faut O(V²) temps.

Sinon, on peut faire un De Fisher-Yates shuffle (ou Knuth shuffle, si vous préférez), en s'arrêtant après E itérations. Dans la version de l'EXERCICE shuffle présenté dans Wikipedia, cela permettra de produire de la fuite des entrées, mais l'algorithme fonctionne tout aussi bien à l'envers:

//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);

Cela nécessite seulement O(E) temps, mais elle nécessite O(N²) de l'espace. En fait, ce qui peut être amélioré à O(E) l'espace avec quelques astuces, mais une SORTE de fragment de code est trop petit pour contenir le résultat, je vais donc donner une plus simple en O(E) l'espace et O(E log E) de temps. Je suppose qu'il y a une classe de DAG avec au moins:

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);
};

Maintenant, va ici:

//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;
}

Créer un graphique avec n nœuds et une arête entre chaque paire de nœuds n1 et n2 si n1 != n2 et n2 % n1 == 0.