Classificare un grafico per rendere come molte frecce indicano avanti possibile

Question

devo ordinare i nodi di un grafo orientato in modo tale che il numero di frecce che scorre all'indietro (contro l'ordinamento) è minimo.

mi viene in mente di algoritmi (ad esempio tenere scambiando i nodi fino a quando non sarà di swap migliorare le cose), ma io non sono sicuro di come veloce che corrono o se arrivare alla soluzione migliore.

Qual è il nome e la complessità di questo problema?

Answer 1

Dopo un certo pensiero mi sono reso conto che il problema può essere suddiviso in due parti:

1. determinano una grande sottografo aciclico di un grafo (che è NP-hard )
2. topologicamente sorta di esso (che è molto più facile )

Answer 2

Ordinamento nodi in ordine di profondità può essere fatto con un topologico. Tuttavia, questo funziona solo con grafici che non contengono cicli. Il tuo problema sembra che ci sono cicli nel grafico. Una possibilità sarebbe quella di trovare i cicli (vedere la Tortoise and Hare algoritmo per un metodo di fare questo) e rompere il ciclo, la registrazione in cui si spezzò. Poi ordinare i nodi e ri-collegamento.

Se si sta facendo questo per scopi di visualizzazione c'è una libreria di rendering grafico chiamato GraphViz che fa qualcosa di molto simile a quello che si sta descrivendo e quindi delinea i nodi. E 'facile da integrare e utilizzare e renderà a schermo o una varietà di diversi formati di output.