Foros - Stratos

 Saludos,

estoy trabajando en la generación de un grafo aleatorio. Todo parece ir correcto, ya lo había terminado, cuando me doy cuenta de que la probabilidad de creación de una arista y la densidad real del grafo construido así no cuadran nunca (normal, son sólo probabilidades); pero es que además, la real SIEMPRE es menor (bastante) que la probable (a pesar de que son muchos nodos).

Como muchas veces estos fallos suelen ser cosas que el propio programador no se da cuenta, a pesar de ser de lo más obvio, ¿podríais echar un vistazo a ver si conseguís descubrirme el porqué?

Por ejemplo:

Sea un tablero definido como una matriz de nodos con conectividad 8:
6390 nodos => 50158 vecinos => 25079 aristas
Los ejemplos son del tipo:
Probabilidad de que esté la arista
Densidad real de aristas
Vecinos que hay(V)
   P           DR           V
86,57%  80,76%  40508
43,14%  30,51%  15302
15,99%    9,60%    4814
74,72%  65,69%  32948
...
Siempre la densidad real es menor que la probabilidad de generación (que debería dar la densidad, no?)



Sólo pongo aquí el código interesante:

METODO PARA CREAR EL GRAFO ALEATORIO:


// probability = rand(); antes de llamar a este metodo

void createRandomGraph(Board* board, long probability) {
int i, j;

// Connectivity 4
if(board->getConnectivity() == 4) {
 // For every node
 for(i=0; i<board->getHeight(); i++) {
  for(j=0; j<board->getWidth(); j++) {
   // If the sum is even
   if(!((i+j) & 1)) {
    // Check cross
    if(rand() < probability) board->deleteConnection(i,j, north);
    if(rand() < probability) board->deleteConnection(i,j, south);    
    if(rand() < probability) board->deleteConnection(i,j, east);    
    if(rand() < probability) board->deleteConnection(i,j, west);    
   }
  }
 }
}
// Connectivity 8
else {
 // For every node
 for(i=0; i<board->getHeight(); i++) {
  for(j=0; j<board->getWidth(); j++) {
   // If the sum is even
   if(!((i+j) & 1)) {
    // Check diagonals only
    if(rand() < probability) board->deleteConnection(i,j, northeast);    
    if(rand() < probability) board->deleteConnection(i,j, southeast);    
    if(rand() < probability) board->deleteConnection(i,j, northwest);    
    if(rand() < probability) board->deleteConnection(i,j, southwest);    
   }
   // If its odd
   else {
    // Check cross
    if(rand() < probability) board->deleteConnection(i,j, north);
    if(rand() < probability) board->deleteConnection(i,j, south);    
    if(rand() < probability) board->deleteConnection(i,j, east);    
    if(rand() < probability) board->deleteConnection(i,j, west);    
    if(rand() < probability) board->deleteConnection(i,j, northeast);    
    if(rand() < probability) board->deleteConnection(i,j, southeast);    
    if(rand() < probability) board->deleteConnection(i,j, northwest);    
    if(rand() < probability) board->deleteConnection(i,j, southwest);
   }
  }
 }
}
...
}


METODO QUE CALCULA LA DENSIDAD:

float calculateDensity(Board* board) {
int i,j;
long num_neighbours=0, max_neighbours;
// Calculate density
max_neighbours = board->getConnectivity() * board->getWidth() * board->getHeight();
// substract not allowed neigbours (border)
if(board->getConnectivity() == 4)
 max_neighbours = max_neighbours - board->getWidth()*2 - board->getHeight()*2;
else
 max_neighbours = max_neighbours - board->getWidth()*6 - board->getHeight()*6 + 4;
// count real nodes
for( i=0; i<board->getHeight(); i++) {
 for( j=0; j<board->getWidth(); j++) {
  num_neighbours += board->getNodeAt(i,j)->getNeighboursNumber();
 }
}
// et voilá
return (((float)num_neighbours/max_neighbours)*100);
}


El invocador sería:

...
p = rand();
createRandomGraph(board, p);

real = calculateDensity(board);
probable = 100-(((float)p/RAND_MAX)*100);

imprimir real y probable
...



Dónde tengo la confusión?

Gracias por echar el vistazo.

 No entiendo tu código al 100%, pero parece que lo que haces es borrar conexiones. ¿No deberían ser los if del tipo if(rand() > probability)..?

 Otra cosilla que he visto.

Calculas el número máximo de vecinos (aristas) como

max_neighbours = board->getConnectivity() * board->getWidth() * board->getHeight();

Sin embargo, luego sólo borras en casillas alternadas

// If the sum is even
  if(!((i+j) & 1)) {....

Lo que me hace sospechar que realmente el número de aristas debería ser la mitad ya que se comparte la sur de un nodo con la norte del otro, etc. <_<

max_neighbours = board->getConnectivity() * board->getWidth() * board->getHeight()/2;

 

QUOTE (gdl)

No entiendo tu código al 100%, pero parece que lo que haces es borrar conexiones. ¿No deberían ser los if del tipo if(rand() > probability)..? [/quote] Uhmmmmm, podría ser. Podría ser. Lo pruebo y comento. QUOTE (gdl) Otra cosilla que he visto. Calculas el número máximo de vecinos (aristas) como CODE max_neighbours = board->getConnectivity() * board->getWidth() * board->getHeight(); Sin embargo, luego sólo borras en casillas alternadas CODE // If the sum is even   if(!((i+j) & 1)) {.... Lo que me hace sospechar que realmente el número de aristas debería ser la mitad ya que se comparte la sur de un nodo con la norte del otro, etc. dry.gif CODE max_neighbours = board->getConnectivity() * board->getWidth() * board->getHeight()/2; [/quote] Es una buena idea; en el código de Board::deleteConnection se llama a node->deleteNeighbour(direction) y a opposite->deleteNeighbour(direction) Código [Seleccionar] Expand void deleteConnection(int row, int col, TNeighbour neighbour) {  Node* pN;  TNeighbour opposite;  // Need a valid cell  assert(row >= 0 && row < height && col >= 0 && col < width);  // delete this to neighbour connection  nodes[row][col].deleteNeighbour(neighbour);    // delete neighbour to this connection    pN = getNeighbourPointer(row, col, neighbour, &opposite);  if(pN != NULL) pN->deleteNeighbour(opposite);   } En realidad está todo pensado en función de vecinos, sin contar aristas, ya que la información de los vecinos está duplicada como dices. Código [Seleccionar] Expand enum TNeighbour { none      = 0, north   = 1, south   = 2, east   = 4, west   = 8, northeast = 16, northwest = 32, southeast = 64, southwest = 128, all    = 255 // Useful to init nodes }; Sólo borro casillas alternas por esa razón. El procedimiento sólo decide si borrar o dejar 1 arista 1 vez. Si hiciese todas las casillas en vez de alternas, la probabilidad de borrar/dejar una artista sería p+p*p, en vez de p, ya que miraría borrar(0,0, sur) y borrar(1,0,norte), que es la misma arista. Título: Probabilidad Y Realidad. Publicado por: Warchief en 02 de Abril de 2005, 02:35:50 PM  << No me deja editar el de antes, me sale el código html en el recuadro donde debería escribir el mensaje y no hay botones de enviar, etc :huh:>>   Añado a lo de antes. Los nodos devuelven el número de nodos vecinos, por lo que se cuenta cada arista dos veces. Código [Seleccionar] Expand // Return number of connected neighbours unsigned int getNeighboursNumber() const {  unsigned int number = 0;  for(int i=0; i<8; i++) number = number + ((neighbours >> i) & 1);  return number; } Así que en realidad la densidad es: aristas*2/aristas_maximas*2 * 100. Sobre si debe ser rand() > probability o rand() < probability. probability es la probabilidad de ser borrada, por lo que está bien con "<". Pensemos en una probability de RAND_MAX. Todas las aristas serán borradas. es por eso que al calcular la densidad esperada (probable) hago: Código [Seleccionar] Expand probable = 100-(((float)p/RAND_MAX)*100); // 100 - porcentaje de borrado = densidad Esto es correcto no? Gracias por tu tiempo y comentarios. Título: Probabilidad Y Realidad. Publicado por: Warchief en 02 de Abril de 2005, 02:54:58 PM  Ahhh, gdl, me diste la idea de donde buscar. Creo que el fallo está claramente en: Código [Seleccionar] Expand  // For every node  for(i=0; i<board->getHeight(); i++) {   for(j=0; j<board->getWidth(); j++) {    // If the sum is even    if(!((i+j) & 1)) {     // Check diagonals only     if(rand() < probability) board->deleteConnection(i,j, northeast);         if(rand() < probability) board->deleteConnection(i,j, southeast);         if(rand() < probability) board->deleteConnection(i,j, northwest);         if(rand() < probability) board->deleteConnection(i,j, southwest);        }    // If its odd    else {     // Check cross     if(rand() < probability) board->deleteConnection(i,j, north);     if(rand() < probability) board->deleteConnection(i,j, south);         if(rand() < probability) board->deleteConnection(i,j, east);         if(rand() < probability) board->deleteConnection(i,j, west);         if(rand() < probability) board->deleteConnection(i,j, northeast);         if(rand() < probability) board->deleteConnection(i,j, southeast);         if(rand() < probability) board->deleteConnection(i,j, northwest);         if(rand() < probability) board->deleteConnection(i,j, southwest);    }   }  } que debería ser algo como Código [Seleccionar] Expand  // For every node  for(i=0; i<board->getHeight(); i++) {   for(j=0; j<board->getWidth(); j++) {    // If the sum is even    if(!((i+j) & 1)) {                                         IF(i&1) {     // Check diagonals only     if(rand() < probability) board->deleteConnection(i,j, northeast);         if(rand() < probability) board->deleteConnection(i,j, southeast);         if(rand() < probability) board->deleteConnection(i,j, northwest);         if(rand() < probability) board->deleteConnection(i,j, southwest);                                            }                                        else {                                        // Check cross     if(rand() < probability) board->deleteConnection(i,j, north);     if(rand() < probability) board->deleteConnection(i,j, south);         if(rand() < probability) board->deleteConnection(i,j, east);         if(rand() < probability) board->deleteConnection(i,j, west);         if(rand() < probability) board->deleteConnection(i,j, northeast);         if(rand() < probability) board->deleteConnection(i,j, southeast);         if(rand() < probability) board->deleteConnection(i,j, northwest);         if(rand() < probability) board->deleteConnection(i,j, southwest);                                        }    }   }  } Probando. Título: Probabilidad Y Realidad. Publicado por: Warchief en 02 de Abril de 2005, 03:26:55 PM  CONSEGUIDOOOOOOOOOO. Joder q tonto estoy, por no pensar bien sobre el papel. Código [Seleccionar] Expand // Connectivity 8 else {  // For every node  for(i=0; i<board->getHeight(); i++) {   for(j=0; j<board->getWidth(); j++) {    // If the sum is even    if(!((i+j) & 1)) {     // If row is odd     if(i&1) {      // Check ****      if(rand() < probability) board->deleteConnection(i,j, north);      if(rand() < probability) board->deleteConnection(i,j, south);      if(rand() < probability) board->deleteConnection(i,j, east);      if(rand() < probability) board->deleteConnection(i,j, west);     }     // is even     else {      // Check all      if(rand() < probability) board->deleteConnection(i,j, north);      if(rand() < probability) board->deleteConnection(i,j, south);          if(rand() < probability) board->deleteConnection(i,j, east);          if(rand() < probability) board->deleteConnection(i,j, west);          if(rand() < probability) board->deleteConnection(i,j, northeast);          if(rand() < probability) board->deleteConnection(i,j, southeast);          if(rand() < probability) board->deleteConnection(i,j, northwest);          if(rand() < probability) board->deleteConnection(i,j, southwest);     }    }    // FALTABA ESTO!!!!!!!!    else IF (i&1) {     if(rand() < probability) board->deleteConnection(i,j, northeast);         if(rand() < probability) board->deleteConnection(i,j, southeast);         if(rand() < probability) board->deleteConnection(i,j, northwest);         if(rand() < probability) board->deleteConnection(i,j, southwest);    }   }  } } Gracias por las notas gdl, me guiaste ;) Título: Probabilidad Y Realidad. Publicado por: ethernet en 03 de Abril de 2005, 01:28:40 PM  Si quieres hacer algo medianamente serio con probabilidades no uses rand, tiene unas propiedades probabilísticas pésimas. Búscate por ahí un generador de números aleatorios decente. saludos Título: Probabilidad Y Realidad. Publicado por: Warchief en 03 de Abril de 2005, 02:43:17 PM Cita de: ethernetSi quieres hacer algo medianamente serio con probabilidades no uses rand, tiene unas propiedades probabilísticas pésimas. Búscate por ahí un generador de números aleatorios decente. saludos Gracias por la nota. De momento rand me vale (Después de hacer la probabilidad tengo que reparar el grafo hacerlo sin islas y 2-connected, osea que me cargo un poco lo aletorio del comienzo, aunque esta reparación se realice también de forma aleatoria). Con la mínima variación ya me sirve para obtener un grafo "suficientemente" distinto. Lo único que necesito es que cada vez que se ejecute createRandomGraph se genere un grafo distinto. Text only | Text with Images SMF 2.1.6 | SMF © 2013, Simple Machines