algorithm - explicacion - Algoritmo para encontrar bordes redundantes en un gráfico o árbol
deteccion de bordes canny python (6)
¿Existe un algoritmo establecido para encontrar bordes redundantes en un gráfico?
Por ejemplo, me gustaría encontrar que a-> d y a-> e son redundantes, y luego me deshago de ellos, así:
=>
Editar: Strilanc fue lo suficientemente bueno como para leer mi mente por mí. "Redundante" era una palabra demasiado fuerte, ya que en el ejemplo anterior, ni a-> b ni a-> c se consideran redundantes, pero a-> d sí lo es.
Creo que la manera más fácil de hacer eso, de hecho, imagina cómo se vería en el trabajo real, imagina si tienes articulaciones, Like
(A-> B) (B-> C) (A-> C), imagine si la distancia entre los gráficos cercanos es igual a 1, entonces
(A-> B) = 1, (B-> C) = 1, (A-> C) = 2.
Entonces puedes quitar la articulación (A-> C).
En otras palabras, minimizar.
Esta es solo mi idea de cómo pensaría al principio. Hay varios artículos y fuentes en la red, puede verlos y profundizar.
Recursos que te ayudarán a:
Algoritmo para eliminar bordes redundantes en el gráfico dual de un CSP no binario
Estructura de datos gráficos y Algoritmos básicos de gráficos
Google Books, al encontrar un mínimo de dos Subgrafos conectados
Desea calcular el gráfico más pequeño que mantiene la accesibilidad a los vértices.
Esto se llama reducción transitiva de un gráfico. El artículo de wikipedia debe ayudarlo a comenzar por el camino correcto.
Un sub-gráfico de un gráfico dado que no contiene "bordes redundantes" se llama un " árbol de expansión " de ese gráfico. Para cualquier gráfico dado, son posibles múltiples árboles de expansión.
Entonces, para deshacerse de los bordes redundantes, todo lo que necesita hacer es encontrar cualquier árbol de expansión de su gráfico. Puede utilizar cualquier algoritmo de búsqueda de profundidad o algoritmo de búsqueda de amplitud y continuar la búsqueda hasta que haya visitado todos los vértices en el gráfico.
Varias formas de atacar esto, pero primero vas a necesitar definir el problema un poco más precisamente. Primero, el gráfico que tienes aquí es acíclico y dirigido: ¿esto siempre será cierto?
A continuación, debe definir lo que quiere decir con un "borde redundante". En este caso, empiezas con un gráfico que tiene dos rutas a-> c: una a través de by una directa. De esto infiero que por "redundante" te refieres a algo como esto. Deje que G = <V, E> sea un gráfico, con V el conjunto de vértices y E ⊆ V × V el conjunto de aristas. Parece que define todos los bordes de v i a v j más cortos que el borde más largo como "redundantes". Por lo tanto, lo más fácil sería utilizar la primera búsqueda en profundidad, enumerar las rutas, y cuando encuentre una nueva que sea más larga, guárdela como el mejor candidato.
Sin embargo, no puedo imaginar para qué lo quieres. ¿Puedes decir?
Verifique esto: árbol de expansión mínimo
Tuve un problema similar y terminé resolviéndolo de esta manera:
Mi estructura de datos está hecha de dependends diccionario de dependends , desde un ID de nodo hasta una lista de nodos que dependen de él (es decir, sus seguidores en el DAG). Tenga en cuenta que funciona solo para un DAG, es decir, gráfico acíclico dirigido.
No he calculado la complejidad exacta de la misma, pero se tragó mi gráfica de varios miles en una fracción de segundo.
_transitive_closure_cache = {}
def transitive_closure(self, node_id):
"""returns a set of all the nodes (ids) reachable from given node(_id)"""
global _transitive_closure_cache
if node_id in _transitive_closure_cache:
return _transitive_closure_cache[node_id]
c = set(d.id for d in dependents[node_id])
for d in dependents[node_id]:
c.update(transitive_closure(d.id)) # for the non-pythonists - update is update self to Union result
_transitive_closure_cache[node_id] = c
return c
def can_reduce(self, source_id, dest_id):
"""returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
for d in dependents[source_id]:
if d.id == dest_id:
continue
if dest_id in transitive_closure(d.id):
return True # the dest node can be reached in a less direct path, then this link is redundant
return False
# Reduce redundant edges:
for node in nodes:
dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]