Algoritmo para agrupar todos los Ciclos Juntos

I tienen una gran cantidad de ciclos (indicado por valores numéricos, por ejemplo, 1-2-3-4 corresponde a un ciclo, con 4 bordes, borde 1 es {1:2}, borde 2 es {2:3}, borde 3 es {3,4}, el borde 4 es {4,1}, y así sucesivamente).Algoritmo para agrupar todos los Ciclos Juntos

Se dice que un ciclo está conectado a otro ciclo si comparten uno y solo un borde.

Por ejemplo, supongamos que tengo dos ciclos 1-2-3-4 y 5-6-7-8, luego hay dos grupos de ciclos porque estos dos ciclos no se conectan entre sí. Si tengo dos ciclos 1-2-3-4 y 3-4-5-6, entonces tengo solo un grupo de ciclos porque estos dos ciclos comparten el mismo borde.

La figura a continuación debe ser capaz de ilustrar mi punto:

alt text http://lh5.ggpht.com/_SDci0Pf3tzU/SuBhd07xbWI/AAAAAAAAFMs/9OlMhN8uzzQ/s640/mst.jpg

El R1, R2 a R7 son lo que yo llamo "ciclo". En la figura anterior, solo hay un grupo de ciclo que abarca todos los R1 a R7.

¿Cuál es la forma más eficiente de encontrar todos los grupos de ciclos?

Fuente

2010-04-03 Graviton

¿Cómo se da su opinión? Al igual que en sus ejemplos o se le da un gráfico o algo así? – IVlad

Esta pregunta puede ser más adecuada para el desbordamiento matemático. –

Quizás deba explicar lo que intenta lograr, que pueda dar una pista de por qué lo llama "ciclos" y por qué tiene "bordes", y lo que significa. – Guffa

Primero encuentre todos los ciclos en el gráfico y etiquételos, por ejemplo, A, B, C, etc. Ahora haga un nuevo gráfico donde cada ciclo encontrado en el gráfico se convierta a un solo nodo en el nuevo gráfico. Únase a los nodos con un borde en el nuevo gráfico si los ciclos correspondientes están "conectados" en el gráfico anterior, usando su definición (bastante inusual) de conectado.

El número de "grupos de ciclos" es entonces el número de connected components en el nuevo gráfico.

Fuente

2010-04-03 12:57:18

@Gracias Marque, pero ¿hay alguna forma de recuperar todos los ciclos dentro de cada grupo de ciclos? – Graviton

@Mark, también me pregunto sobre cómo saber si los ciclos están conectados, pero en su respuesta usted dice que necesito unirme a los nodos, ¿puede ser más explícito sobre esto? – Graviton

@Ngu: Dejaré que los ciclos de detección sean parte de otra persona. Para determinar si dos ciclos están conectados, cuente el número de bordes que comparten. Una vez que haya detectado los ciclos, puede crear un nuevo gráfico, G '. En su ejemplo, G 'contendría 7 nodos, uno para cada ciclo que haya detectado. Llame a estos nuevos nodos R1, R2, ..., R7. Si hay dos ciclos conectados, cree un borde entre ellos en G '. R1 debe tener una ventaja para R6 y R7. R2 debe tener una ventaja para R3 y R7, etc ... Cuente los componentes conectados de ese gráfico usando cualquier algoritmo estándar de Wikipedia - la respuesta es 1. –

Estoy bastante seguro de que esta no es la forma más eficiente, pero esto sería mi primer intento:

Primer intercambio bordes con vértices: Así, por ejemplo, sus ciclos 1-2-3-4, 3-4-5-6 y 5-6-7-8, se 'll necesidad:

"12" => "A" 
"23" => "B" 
"34" => "C" 
"45" => "D" 
"56" => "E" 
"67" => "F" 
"78" => "G" 
"41" => "H" 
"63" => "I" 
"85" => "J"

Esto le da hasta (v * (v-1))/2 vértices, pero está bien - todavía puede ser lo suficientemente bueno para un O (v^2) algoritmo.

Entonces representar los ciclos como campos de bits: "1-2-3-4" se convierte en ABCH

ABCDEFGHIJ 
1110000100

y "3-4-5-6" se convierte en CDEI

ABCDEFGHIJ 
0011100010

Así tienen exactamente un bit en común, lo que significa que en el gráfico original, tenían exactamente una ventaja en común. Esto podría verificarse bit a bit con O (v^2), o con búsqueda binaria (primero compruebe con ANDing, si tienen algún bit en común, luego marque la primera mitad de bits, etc.)

Fuente

2010-04-03 12:40:44

No creo que su solución funcione, ¿qué pasa si dos ciclos que no se conectan directamente, sin embargo, todavía pertenecen al mismo grupo de ciclo? – Graviton

@Ngu: Mi intención era probar dos ciclos primero, y combinarlos en uno, si están conectados (la combinación se puede hacer fácilmente mediante una operación OR). Luego continúa con el siguiente ciclo. ¡Espero que entienda la agrupación correctamente, ya que se usa aquí! –

Si desea mejorar el rendimiento, también puede intentar experimentar con tres o cuatro ciclos a la vez al ANDing (dependiendo de la probabilidad de que los ciclos estén en un grupo, puede ajustar el rendimiento de esta manera). Luego, "profundizar" en pares de ciclos solo, si se produjo una coincidencia. Incluso puede ser posible comenzar con ANDir la mitad de los ciclos y "perforar" recursivamente ... –

Algoritmo para agrupar todos los Ciclos Juntos

Respuesta

Cuestiones relacionadas