Classificando um gráfico para fazer tantas setas apontam para a frente possível

Question

I necessidade de classificar os nodos de um grafo orientado de tal modo que o número de setas que fluem para trás (contra a ordem de classificação) é mínimo.

Não consigo pensar em algoritmos (por exemplo, manter trocando nós até não swap irá melhorar as coisas), mas eu não tenho certeza o quão rápido eles correm ou se chegar à melhor solução.

O que é o nome e complexidade deste problema?

Answer 1

Depois de algum pensei que eu percebi que o problema pode ser dividido em dois:

1. determinar uma maior subgráfico acíclico de um gráfico (que é NP-hard )
2. topologicamente classificá-lo (que é muito mais fácil )

Answer 2

Classificando nós, a fim de profundidade pode ser feito com um topológica tipo. No entanto, este só vai trabalhar com gráficos que não contêm ciclos. Seus sons problema como há ciclos no gráfico. Uma opção seria encontrar os ciclos (ver tartaruga e da lebre algoritmo para um método de fazer este) e quebrar o ciclo, gravação onde você quebrou. Em seguida, classificar a nós e re-ligação.

Se você está fazendo isso para fins de visualização há uma biblioteca de renderização gráfico chamado GraphViz que faz algo muito semelhante ao que você está descrevendo e, em seguida, estabelece os nós. É fácil de integrar e usar e retribuirá a tela ou uma variedade de diferentes formatos de saída.