Simplificación de gráfico/celosía

Question

Estoy trabajando en la estructura de datos para el algoritmo de corte de gráfico. 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.

Definir siguiente nodo N (n) de nodo n como un conjunto de nodos b para el que un < b y no hay c con un < 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 no hay 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 crear nuevo enrejado con el mapeo:

• sub-red a un nodo
• si se encuentra partición superior de crear bordes número de cardinalidad partición ()

En simple, algoritmo de 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 a nuevos celosías. 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

Antecedentes:

que tuvo la idea de utilizar la red Caudal máximo problema de interdicción en la materia 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 las rutas más cortas desde source hasta sink. Para hacer eso 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 hasta 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 son agradables (paralelos, de propagación, ...), lo que es más fácil en el enrejado (muy estructurado).

Los cortes nativos son 'ondas', p. un buen corte C también produce N(C) que es bueno.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 se utilizan en el mapeo: - conjunto de nodos de onda paralela. Si C es una onda, entonces N(C) es otra. - franja: 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. 

Asignación de mapas de franja 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 la franja que comparte la última ola con la que comparte la primera ola.

Dado que el mapeo produce un nuevo enrejado con las mismas propiedades, el procedimiento se puede repetir hasta que haya un enrejado con un solo 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 el nodo mínimo M y N(M) están en la misma franja y eso reduce el diámetro del enrejado.

Ahora, realizar o buscar cortes es una tarea recursiva, comenzar con celosía uno antes que el último con un solo nodo, y cortar 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 del 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 correctamente su pseudocódigo, no: lleva un orden lineal -node n a un orden lineal -node n.

Describiría su código como si aceptara una orden parcial y encontrara un series-parallel partial order en el cual tenga una incrustación razonablemente "fiel".

Si solo está interesado en encontrar los cortes máximos de caudales/minutos en los gráficos planos, hay un O(n log n) algorithm para eso.