algorithm - graphs - Simplificación de gráfico/celosía

graph representations

Question

Estoy trabajando en la estructura de datos para el algoritmo de corte de gráficos. El problema es hacer diferentes cortes en los caminos más cortos. Creé una estructura de datos para la que no estoy seguro de las propiedades.

La entrada es un gráfico dirigido de las rutas más cortas, que es un enrejado delimitado, un conjunto ordenado parcialmente con un mínimo y máximo elemento.

Defina el siguiente nodo N (n) del nodo n como un conjunto de nodos b para los cuales a <b y no hay c con a <c <b. Similar define nodo anterior P (n) . Amplíe las definiciones en los conjuntos, N (S) unión de N (n) para n en S, similar para P (S).

Es fácil hacer diferentes cortes en la lista del conjunto de nodos L, N (L), N (N (L)), ... donde para cada par de conjuntos vecinos A, N (A) = B sostiene que hay sin particiones:

A = A_1 union A_2
B = B_1 union B_2
with B_i = N(A_i), A_i = P(B_i) for i=1,2.

Con esta propiedad crea un nuevo enrejado con mapeo:

• subred a un nodo
• si se encuentra una partición superior que crear bordes (número de cardinalidad de la partición).

En simple, algoritmo para celosía -> mapeo de celosía es:

A = {minimum node}
new_node = [A]
1:
while A, N(A) don''t have partitions
append N(A) to new_node
A = N(A)
for each partition $B_i$
last_new_node = new_node
create new_node = [B_i]
create edge last_new_node to new_node
go to 1
At the end fix maximum node in new lattice if needed

Este algoritmo se puede llamar repetidamente en nuevas redes. Me preocupa:

• ¿Hay garantía de alcanzar el enrejado de un nodo?
• ¿Hay alguna medida del número de iteraciones para alcanzar el enrejado de un nodo? Me parece que el límite es el diámetro del gráfico de entrada.

Agradezco el enlace a cualquier estructura de datos similar.

Tnx

Fondo:

Tuve la idea de utilizar el problema de interdicción de red de flujo máximo en las cosas en las que estaba trabajando. Estaba pensando en la versión de interdicción de vértices donde se puede eliminar una determinada cantidad de vértices de la red para minimizar el flujo máximo. La red en la que estaba trabajando era un gráfico planar muy regular (plano dividido en hexágonos, cada vértice está conectado a 6 vértices). Quería cortar (interceptar) solo los caminos más cortos de la source al sink . Para hacer que utilicé la simplificación del gráfico dirigido, el borde (a,b) está en un gráfico simplificado si está en el camino más corto desde a al sink . Si el peso del borde es positivo, entonces el gráfico dirigido simplificado es el enrejado. Esto es lo que llamé "gráfico dirigido de los caminos más cortos".

Quería tener cortes en los vértices que sean agradables (paralelos, de propagación, ...), lo que es más fácil en el enrejado (muy estructurado).

Los cortes nativos son ''ondas'', por ejemplo, un buen corte C también produce N(C) cual es agradable. Por eso traté de enrejado simplificado con las operaciones descritas anteriormente. Traté de describir 2 subconjuntos de vértices que son interesantes para los cortes y que se utilizan en el mapeo: - ola - conjunto paralelo de nodos. Si C es una onda, entonces N(C) es otra. - stripe - serie de ondas sin intersección con otras bandas. C, N(C), N(N(C)) .

 B1--C1--D1 ...
/ / / / /
A X X
/ / / / /
B2--C2--D2
Waves: {A}, {B1,B2}, {C1,C2}, {D1,D2}
Stripe is made of these 4 waves.

El mapeo de la franja de mapas desde el enrejado inicial al nodo del nuevo enrejado. Los nodos en el nuevo enrejado están conectados si comparten onda. La dirección del borde es de una franja que comparte la última ola con la que comparte la primera ola.

Debido a que el mapeo produce un nuevo enrejado con las mismas propiedades, el procedimiento puede repetirse hasta que exista un enrejado con solo un nodo. Eso se puede mostrar porque el diámetro de la red es menor, al menos por 1, con cada iteración. Esto se debe a que los nodos mínimo M y N(M) están en la misma franja y eso reduce el diámetro de la red.

Ahora, realizar o buscar cortes es una tarea recursiva, comenzar con celosía uno antes del último con un solo nodo y hacer corte en una onda completa o en ondas vecinas en forma de escalera. Para los nodos en corte, tome la subred que está mapeada en ella, y haga corte en esa subred. Lo mismo se hace hasta alcanzar el enrejado inicial.

Esta estructura es de algún tipo sobre la compresión de celosía. Creo que se puede usar para buscar dinámicamente cortes de celosía.

En mi caso, no lo estoy usando ya que algunas otras restricciones de proyecto. Resolví el problema inicial muy simple con solo unas pocas líneas de código, pero no me di cuenta de que se puede hacer así antes :-)

Answer 1

¿Hay alguna garantía de alcanzar un enrejado de un nodo?

Si entiendo tu pseudocódigo correctamente, no: lleva una orden lineal n- nodo a un orden lineal n- nodo.

Yo describiría su código como si aceptara una orden parcial y encontrara una orden parcial en serie paralela en la cual tiene una incrustación razonablemente "fiel".

Si solo está interesado en encontrar los cortes de máximo flujo / min en los gráficos planos, existe un algoritmo O (n log n) para eso.