Problema Con Grafos

[ethernet]

 En el juego que estoy preparando me encuentro con un problema que he resuelto de una forma un poco extraña y que no me da mucha seguridad.

Tengo una lista de nodos numerados en orden creciente desde 0 a N-1 siendo N el número de nodos. Cada nodo contiene información que no importa en este caso. Luego tengo información acerca de las conexiones entre nodos. Cada conexión tiene dos índices, que indican los dos nodos conectados. Hasta ahora la cosa es simple, pongo un poco de código para aclarar:

Código [Seleccionar] Expand


class Nodo
{
//info
public:
};

class Cox
{
Cox(int i1,int i2): _idx1(i1),_idx2(i2) {}
int _idx1,idx2;
}

class Grafo
{
enum {N = 10}; //número de ejemplo, puede ser otro
Nodo nodos[N];
std::vector<Cox*> coxs;

void GrafoDeEjemplo()
{

coxs.push_back(new Cox(0,1));
coxs.push_back(new Cox(1,2));
coxs.push_back(new Cox(0,3));
coxs.push_back(new Cox(4,0));
}
};


Imaginaos que ahora desaparece un enlace, puede darse el caso de que el grafo se rompa en dos, pues lo que yo quiero calcular es qué nodos pertenecen a una isla y qué nodos a otra. Nótese que al desaparecer un enlace solo es posible que se parta en dos islas. Otro dato que pudiera interesar es que el número de nodos no varía durante toda la ejecución, ni se añaden ni se quitan.

Mi Solución es la siguiente:

- asigno un id a cada nodo diferente.
- empiezo con el nodo 0 (id = 0)
- comparo con todos los nodos a los que está conectado. Pongo el id menor de los dos a los dos nodos.
- sigo con el resto de nodos.
- volver a hacer la operación una vez más.

De esta forma al final tendré al final una lista con el número de isla al que pertenece cada nodo, por ejemplo

[0,0,0,4,0,0,4] -> los nodos 0,1,2,5 y 6 isla 1, 5 y 7 isla 2.

Sorry por el tocho. Espero que alguien que haga informática tenga más idea de grafos, porque yo no doy con la palabra de búsqueda exacta para encontrar los algortimos.

un saludo

[Warchief]

 Yo hace poco tuve que hacer algo parecido, pero sólo necesitaba saber si estaban o no conectados desde el nodo 0, es decir, si estaban aislados o no (no qué número de isla). Lo que has hecho está bastante bien.

Creo que estos algoritmos son los de Flood Fill:
http://www.comp.nus.edu.sg/~stevenha/progr...rog_graph3.html

Un ejemplo de mi ejecución:

Código [Seleccionar] Expand


// Used internally to repair boards. Mark linked nodes to one passed as parameter (=zone)
void BoardBuilder::markZone(Board* board, int row, int col, int zoneNum)
{
Node* actualNode = board->getNodeAt(row, col);

// If it is not a visited node
if(actualNode->getZone() == 0) {
 actualNode->setZone(zoneNum); // Mark zone of the node

 // Find the neighbours and ask them to join the zone!  
 TNeighbour direction;
 int nextRow, nextCol;
 // For every candidate neighbour
 for(int i=0; i<board->getConnectivity(); i++) {
  direction = (TNeighbour)(1 << i);
  // If its neighbour
  if (actualNode->hasNeighbourAt(direction)) {    
   // Join to the zone
   board->getNeighbourCoords(row, col, direction, &nextRow, &nextCol, NULL);
   markZone(board, nextRow, nextCol, zoneNum);
  }
 }
}
}


Donde lo único que hay que hacer es llamar a:

Código [Seleccionar] Expand


markZone(board, 0, 0, 1);  // Enlazar en el tablero, con el nodo 0,0 y marcar como zona 1
// La zona 1 es verde, la zona 0 es roja.





Lo que me parece chungo es la representación que has cogido. Yo hice una matriz de nodos, donde cada nodo guarda sus vecinos en un "short".

Código [Seleccionar] Expand


/// Enumeration to easily handle neighbourhood of the nodes
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
};

// Y luego
Node::unsigned short int neighbours; // Comparando a nivel de bit

/* Claro que esto no permite conectividad mayor que 8. */


[manko]

 Recuerdo que en los algoritmos de Visión Artificial, una de las fases consistia en segmentar los elementos de la imagen según su afinidad, son los llamados algoritmos de Cluistering (agrupamiento).

Son relativamente sencillos y repidos y en este caso tu deberias agrupar las conexiones, separando las conexiones en grupos con un criterio de umbral de distancia 1, es decir cuando la conexión mas cercana a una es de mas de un nodo -> estamos ante otra isla.

Puede que no me haya explicado muy bien ... XD (recien levantado)

Estaban de clustering, el CHAIN_MAP, MAX-MIN y K-MEDIAS (son sencillos si quieres te pongo el pseudocodigo)

[Vicente]

 Hola,

hay un algoritmo basado en la búsqueda en profundidad que te busca las componentes fuertemente conexas de un grafo y sus puntos de articulación. Puede que te sirva (no recuerdo el psc de cabeza, pero lo puedo buscar cuando llegue a casa). Lo que pasa que se basaba en que un nodo es punto de articulación si al desaparecer el grafo se parte en 2 grafos (no en aristas). Un saludo!

Vicente

[ethernet]

 muchas gracias. Warchief, ese es jústamente el link que necesitaba :)

He elegido esa representación porque es la más simple para el resto de cosas y es la que menos memoria me ocupaba.  

[ethernet]

 Ya funciona perfectamente :))

Warchief, ya que estás podrías decir para qué juego es esa imagen. Me viene a la cabeza el típico juego en isométrica de ir pasando habitaciones.

[Warchief]

 

Warchief, ya que estás podrías decir para qué juego es esa imagen. Me viene a la cabeza el típico juego en isométrica de ir pasando habitaciones.

Es una pequeña prueba que hice hace unos meses. El grafo es el tablero de un juego (sin más detalles porque es confindencial ;)) Como es de imaginar, el grafo se crea aleatoriamente al iniciar una partida, de forma que cambia el tablero.

La vista de zonas para saber nodos no alcanzables del tablero.


Grafo reparado, donde no hay nodos con cardinalidad menor que 2.


Con las piezas colocadas.



Suerte con tu grafo  :)