Dominadores de detección incremental en los DAG

Question

Supongamos que tenemos un DAG con una fuente. Me gustaría encontrar los nodos n de modo que cualquier ruta completa desde la fuente se ejecute a través de n (es decir, n domina todos los receptores). En otras palabras: si eliminamos todos los sucesivos de n, todas las rutas terminarían en n. El problema es que los nodos se marcan incrementalmente como eliminados en el DAG. Como los nodos están marcados como eliminados, otros nodos pueden comenzar a satisfacer la propiedad anterior. ¿Cómo puedo detectar esto de manera eficiente cuando sucede?

puntos de bonificación si la estructura de datos puede hacer esto con múltiples fuentes de una manera más eficiente que ejecutar el algoritmo para una sola fuente por separado en cada una de las fuentes.

Answer 1

Topológicamente clasifique este DAG para establecer un orden para sus nodos. Para cada nodo, su valor sería el número de bordes salientes de todos los nodos precedentes menos el número de bordes entrantes para todos los nodos precedentes y el nodo actual. El valor para el nodo "dominador" siempre es cero.

Después de que un nodo esté marcado como "eliminado", ponga sus predecesores y sucesores en la cola de prioridad. La prioridad está determinada por el orden de clasificación topológica. Actualice los valores para todos los nodos, siguiendo el nodo "eliminado" (agregue el número de nodos entrantes y reste la cantidad de nodos salientes para este nodo). Al mismo tiempo (en el mismo orden) el valor de decremento para cada nodo entre el nodo predecesor en la cola de prioridad y el nodo "eliminado" y el valor de incremento para cada nodo, comenzando desde el nodo sucesor en la cola de prioridad. Deténgase cuando el valor de algún nodo se reduzca a cero. Este es un nuevo nodo "dominador". Si se necesitan todos los nodos "dominator", continúe hasta el final del gráfico.

delete(delNode): 
    for each predecessor in delNode.predecessors: queue.add(predecessor) 
    for each successor in delNode.successors: queue.add(successor) 
    for each node in DAG: 
    if queue.top.priority == node.priority > delNode.priority: 
     ++accumulator 

    node.value += accumulator 
    if node.value == 0: dominatorDetected(node) 

    if node.priority == delNode.priority: 
     accumulator += (delNode.predecessors.size - delNode.successors.size) 
     node.value = -1 

    if queue.top.priority == node.priority: 
     queue.pop() 
     if node.priority < delNode.priority: 
     --accumulator 

    if queue.empty: stop 

Para el caso de múltiples fuentes, es posible utilizar el mismo algoritmo, pero mantener una lista de "valores" para cada nodo, un valor para cada fuente. La complejidad del algoritmo es O(Nodes * Sources), lo mismo que para la búsqueda independiente en cada una de las fuentes. Pero el programa puede hacerse más eficiente si se utiliza la vectorización. Los "valores" pueden procesarse en paralelo con las instrucciones SIMD. Los compiladores modernos pueden hacer una vectorización automática para lograr esto.