Reducción de bordes redundantes de un gráfico de dependencia

8

Tengo un DAG de dependencias que contiene muchos bordes redundantes (ver ejemplo a continuación). Quiero un algoritmo "rápido" (es decir, puede manejar un gráfico con varios miles de nodos / bordes) que encuentre un gráfico secundario mínimo.

Por ejemplo:

A -> B -> C
A -> C

en palabras, A es prerrequisito para B, y B es prerrequisito para C, y también A es prerrequisito para C. En este caso, A -> C es redundante (ya que B ya es necesario para llegar a C y A es necesario para llegar a B) .

Ha pasado un tiempo desde que estudié algoritmos, y no estoy seguro de por dónde empezar.

Por cierto, no es crítico que el algoritmo encuentre el mínimo global, el mínimo local está bien (la reducción del borde es solo una optimización del tiempo de ejecución para la próxima etapa del procesamiento).

Además, me doy cuenta de que se trata de un control de calidad de CS y no de programación, pero mi programa está escrito en Python, por lo que me encantaría conocer un módulo de Python o código abierto para hacer esta reducción, en caso de que lo sepas.

¡gracias por adelantado!

ds.algorithms graph-algorithms transitive-reduction Iftah
fuente
Me preguntaba si DFS podría ayudar aquí.
Pratik Deoghare
3
Está buscando la "reducción transitiva" de su gráfico de dependencia.
Dave Clarke
Encuentra los componentes fuertemente conectados. Solo deje un borde entre cada par de componentes. Para cada componente fuertemente conectado, necesita encontrar un número mínimo de ciclos que lo cubran. Encontrar un número mínimo de ciclos parece ser NP-completo ya que decidirá la Hamiltonicidad, pero dado que solo necesita un mínimo local, simplemente elimine los bordes de cada componente hasta que pierda su fuerte conectividad.
Kaveh

Respuestas:

13

La reducción transitiva de un gráfico dirigido AV Aho, MR Garey y JD Ullman

De acuerdo con Wikipedia , este algoritmo es utilizado por treduna herramienta para la reducción transitiva disponible en el paquete GraphViz. Puede ejecutarlo en su gráfico y obtener un gráfico reducido.

Esta pregunta es un duplicado de esta pregunta de stackoverflow .

código aquí graphviz/tools/src/tred.c hace DFS uso. ;-)

Pratik Deoghare
fuente
2
No lo sabía tred, gracias.
Anthony Labarre
1
Gracias MachineCharmer. Estoy fuera de una universidad y no puedo descargar el documento sin pagar 25 $ ... ¿hay una fuente en línea gratuita que describa este algoritmo? La fuente tred es pequeña y legible, pero sin explicaciones.
Iftah
No. No hay un enlace de descarga gratuita para ese documento. Pero puede que tengas amigos en alguna universidad :)
Pratik Deoghare
-1

Terminé resolviéndolo de esta manera:

Mi estructura de datos está hecha de dependendsdiccionario, desde una identificación de nodo a una lista de nodos que dependen de él (es decir, sus seguidores en el DAG).

No he calculado la complejidad exacta, 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)]
Iftah
fuente