Ordenar una gráfica para hacer tantas flechas apuntan hacia adelante como sea posible

Question

Necesito para ordenar los nodos de un grafo dirigido de tal manera que el número de flechas que fluya hacia atrás (en contra de la orden de clasificación) es mínima.

No puedo pensar en algoritmos (por ejemplo, mantener el intercambio de nodos de intercambio hasta que no mejorará las cosas), pero no estoy seguro de la velocidad de éstos o si llegan a la mejor solución.

¿Cuál es el nombre y la complejidad de este problema?

Answer 1

Después de pensarlo me di cuenta de que el problema se puede dividir en dos:

1. determinar una más grande subgrafo acíclico de un gráfico (que es NP-duro )
2. topológicamente tipo (lo cual es mucho más fácil )

Answer 2

Clasificar los nodos en orden de profundidad se puede hacer con un topológico. Sin embargo, esta sólo funcionará con gráficos que no contienen ciclos. Su problema parece que hay ciclos en la gráfica. Una opción sería encontrar los ciclos (véase el tortuga y la liebre algoritmo para un método de hacer este) y romper el ciclo, la grabación en la que la rompió. A continuación, ordenar los nodos y re-enlace.

Si usted está haciendo esto para fines de visualización hay una biblioteca de representación gráfica llamada GraphViz que hace algo muy similar a lo que usted está describiendo a continuación, establece los nodos. Es fácil de integrar y usar y pagará a la pantalla o una variedad de diferentes formatos de salida.