Algoritmo para encontrar bordes redundantes en un gráfico o árbol

Question

¿Existe un algoritmo establecido para encontrar bordes redundantes en un gráfico?

Por ejemplo, me gustaría encontrar que a-> dy a-> e son redundantes, y luego deshacerse de ellos, así:

=>

Edición: 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.

Answer 1

Desea calcular el gráfico más pequeño que mantiene el alcance de los vértices.

Esto se llama transitive reduction de un gráfico. El artículo de wikipedia debe ayudarlo a comenzar por el camino correcto.

Answer 2

Un sub-gráfico de un gráfico dado que no contiene "bordes redundantes" se llama 'spanning tree' de ese gráfico. Para cualquier gráfico dado, son posibles múltiples árboles de expansión.

Por lo tanto, para deshacerse de los bordes redundantes, todo lo que necesita hacer es encontrar cualquier árbol de expansión de su gráfico. Puede usar cualquier algoritmo depth-first-search o breadth-first-search y continuar buscando hasta que haya visitado todos los vértices en el gráfico.

Answer 3

Comprobar esto: Minimum Spanning Tree

Answer 4

Varias maneras de atacar esto, pero primero vamos a necesitar para definir el problema un poco más de precisión. 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 G = < V, E> un grafo, con V el conjunto de vértices y E ⊆ V × V el conjunto de aristas. Se ve un poco como estás definiendo todos los bordes de _{v i} a _{v j} más corto que el borde más largo como "redundante". 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.

No puedo imaginar para qué lo quieres. ¿Puedes decir?

Answer 5

Creo que la forma más sencilla de hacerlo, en realidad imaginar cómo se vería en el trabajo real, imagínese si usted tiene articulaciones, igual que

(A-> B) (B-> C) (A- > C), imagínese si la distancia entre cerca de gráficos es igual a 1, por lo

(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 iba a pensar al principio. Hay varios artículos y fuentes en la red, puede verlos y profundizar.

Recursos, que le ayudará a:

Algorithm for Removing Redundant Edges in the Dual Graph of a Non-Binary CSP

Graph Data Structure and Basic Graph Algorithms

Google Books, On finding minimal two connected Subgraphs

Graph Reduction

Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs

Answer 6

que tenía un problema similar y terminó resolviendo de esta manera:

Mi estructura de datos se hace de dependends diccionario, de un identificador de nodo a una lista de nodos que dependen de él (es decir, sus seguidores en el. TROZO DE CUERO). 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áfico 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)]