c++ - number - Generando un DAG aleatorio

random token c#

Question

Estoy resolviendo un problema en grafo acíclico dirigido.

Pero tengo problemas para probar mi código en algunos gráficos acíclicos dirigidos. Los gráficos de prueba deben ser grandes y ( obviamente ) acíclicos.

Intenté mucho escribir código para generar gráficos acíclicos dirigidos. Pero he fallado todas las veces.

¿Existe algún método existente para generar gráficos dirigidos acíclicos que pueda usar?

Answer 1

Cociné un programa de C que hace esto. La clave es ''clasificar'' los nodos, y solo dibujar bordes desde los nodos de clasificación inferior a los de clasificación superior.

El programa que escribí imprime en el lenguaje DOT .

Aquí está el código en sí, con comentarios que explican lo que significa:

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

Y aquí está el gráfico generado a partir de una ejecución de prueba:

Answer 2

Cree una gráfica con n nodos y un borde entre cada par de n1 y n2 si n1 != n2 y n2 % n1 == 0 .

Answer 3

Entonces, para tratar de poner todas estas respuestas razonables juntas:

(En lo siguiente, usé V para el número de vértices en el gráfico generado, y E para el número de bordes, y asumimos que E ≤ V (V-1) / 2).

Personalmente, creo que la respuesta más útil es en un comentario de Flavius, quien señala el código en condor.depaul.edu/rjohnson/source/graph_ge.c . Ese código es realmente simple, y está descrito convenientemente por un comentario, que reproduzco:

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.

De hecho, lo que hace el código es generar el número de solicitud de bordes haciendo repetidamente lo siguiente:

1. generar dos números en el rango [0, V);
2. recházalos si son iguales;
3. intercambiarlos si el primero es más grande;
4. Recházalos si los ha generado antes.

El problema con esta solución es que a medida que E se acerca al número máximo de bordes V (V-1) / 2, el algoritmo se vuelve más y más lento, porque tiene que rechazar más y más bordes. Una mejor solución sería hacer un vector de todos los posibles bordes V (V-1) / 2; mezclarlo al azar y seleccione los primeros bordes (bordes solicitados) en la lista aleatoria.

El algoritmo de muestreo de reservorio nos permite hacer esto en el espacio O (E), ya que podemos deducir los puntos finales del borde k desde el valor de k. En consecuencia, no tenemos que crear el vector de origen. Sin embargo, todavía requiere tiempo O (V ² ).

Alternativamente, uno puede hacer una mezcla aleatoria de Fisher-Yates (o una mezcla de Knuth, si lo prefiere), deteniéndose después de las iteraciones. En la versión de FY shuffle presentada en Wikipedia, esto producirá las entradas finales, pero el algoritmo funciona igual de bien:

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

Esto requiere solo tiempo O (E) pero requiere espacio O (N ² ). De hecho, esto puede mejorarse al espacio O (E) con algunos trucos, pero un fragmento de código SO es demasiado pequeño para contener el resultado, por lo que proporcionaré uno más simple en el espacio O (E) y O (E log E ) hora. Supongo que hay una clase DAG con al menos:

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

Ahora aquí va:

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

Answer 4

La respuesta a https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs aplica: si tiene una representación de matriz de adyacencia de los bordes de su gráfica, entonces si la matriz Es triangular inferior, es un DAG por necesidad.

Un enfoque similar sería tomar un orden arbitrario de los nodos y luego considerar los bordes del nodo x a y solo cuando x <y . Esa restricción también debe obtener su DAGness por construcción. La comparación de memoria sería una forma arbitraria de ordenar sus nodos si está usando estructuras para representar nodos.

Básicamente, el pseudocódigo sería algo así como:

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

donde N es el número de nodos en tu gráfica.

El pseudocódigo sugiere que el número de DAG potenciales, dados los nodos N, es

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

puesto que hay

n*(n-1)/2

pares ordenados ("N elige 2"), y podemos elegir tener el borde entre ellos o no.

Answer 5

Podría generar un gráfico dirigido al azar y, luego, realizar una búsqueda en profundidad de los ciclos. Cuando encuentre un ciclo, divídalo eliminando un borde.

Creo que este es el peor de los casos O (VE). Cada DFS toma O (V), y cada uno elimina al menos un borde (por lo tanto, máximo E)

Si genera el gráfico dirigido aleatoriamente seleccionando todos los V ^ 2 bordes posibles, y DFS en orden aleatorio y borra un borde aleatorio, esto le daría una distribución uniforme (o al menos cerca de él) sobre todos los dags posibles.

Answer 6

Recientemente intenté volver a implementar la respuesta aceptada y descubrí que es indeterminista. Si no aplica el parámetro min_per_rank, podría terminar con un gráfico con 0 nodos.

Para evitar esto, envolví los bucles for en una función y luego verifiqué para asegurarse de que, después de cada rango, ese min_per_rank estaba satisfecho. Aquí está la implementación de JavaScript:

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

Y algún código pseudo-C que reemplazaría el bucle principal de la respuesta aceptada.

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
}

Answer 7

Un enfoque muy simple es:

1. Asigne aleatoriamente bordes iterando sobre los índices de una matriz diagonal inferior (como lo sugiere un enlace arriba: https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs )

2. Esto le dará un DAG con posiblemente más de un componente. Puede utilizar una estructura de datos de conjunto disjunto para proporcionarle los componentes que luego pueden fusionarse creando bordes entre los componentes.

Los conjuntos disjuntos se describen aquí: https://en.wikipedia.org/wiki/Disjoint-set_data_structure