O título completo do artigo deveria ter sido “Classificação“ topológica ”sustentável de um gráfico com ciclos em
O(|V| + |e| log |e|) no tempo e
O(|V|) na memória sem recursão”, mas me disseram o que é um exagero.
Isenção de responsabilidade: sou um programador, não um matemático, por isso é possível uma linguagem imprecisa em alguns lugares, para os quais você pode e deve chutar.
Essência da tarefa
Analisarei a redação do problema, cuja solução quero compartilhar, em partes.
Classificação topológica é a ordenação dos vértices de um gráfico acíclico direcionado no qual cada um dos vértices de onde a aresta sai sai mais cedo que o vértice no qual essa aresta entra. Existem duas nuances importantes aqui: um gráfico pode ter
mais de um desses pedidos e é aplicável apenas a gráficos
acíclicos . Os matemáticos não se importam, mas os programadores às vezes querem determinismo e um pouco mais do que "desculpe, você tem um ciclo aqui, não será resolvido".
Portanto, adicionamos o requisito de
estabilidade : um par de vértices, cuja ordem não é especificada pelas bordas do gráfico, deve ser determinado pela ordem em que esses vértices chegaram à entrada do algoritmo. Como resultado, ordenações repetidas não alteram a ordem dos vértices.
Com a falta de
recursão, tudo é simples, o computador é significativamente mais fraco do que a máquina de Turing e a memória (e principalmente a pilha) é limitada. Portanto, na programação aplicada, geralmente algoritmos iterativos são preferíveis aos recursivos.
E, finalmente, definirei o que chamo de classificação "topológica" se houver
ciclos no gráfico. Essa é a ordem dos vértices, que coincide com a verdadeira classificação topológica, se cada um dos ciclos for substituído por um vértice, e os vértices do próprio ciclo, de acordo com o requisito de estabilidade, estiverem localizados um em relação ao outro na ordem original.
E agora,
com todo esse lixo, tentaremos decolar. Farei tudo isso dentro da estrutura das restrições de tempo e memória indicadas no início da postagem.
Procure uma solução
Se você olhar para os algoritmos existentes para classificação topológica (
algoritmo Kahn ,
pesquisa profunda ), verifica-se que todos, se houver um ciclo, digam "não posso" e parem de funcionar.
Portanto, vamos por outro lado, com algoritmos que podem fazer algo inteligível com ciclos. Por exemplo,
encontre- os. Entre os
algoritmos listados na Wikipedia
para encontrar ciclos em gráficos , chamou a atenção
o algoritmo de Taryan . Ele contém uma observação interessante de que, como subproduto, o algoritmo produz a classificação topológica
inversa do gráfico:
Embora não haja nada de especial na ordem dos nós em cada componente fortemente conectado, uma propriedade útil do algoritmo é que nenhum componente fortemente conectado será identificado antes de qualquer um de seus sucessores. Portanto, a ordem na qual os componentes fortemente conectados são identificados constitui um tipo topológico reverso do DAG formado pelos componentes fortemente conectados .
É verdade que o algoritmo é recursivo e não está claro o que tem com estabilidade, mas esse é claramente um movimento na direção certa. Uma leitura mais detalhada da Wikipedia revela uma referência ao artigo
Um algoritmo com eficiência de espaço para encontrar componentes fortemente conectados pelo camarada David Pearce, no qual não apenas existe um algoritmo imperativo, mas também reduz os requisitos de memória em comparação com o clássico Algoritmo de Tarjan. O bônus é a
implementação do algoritmo em Java . Deve levar!
Algoritmo PEA_FIND_SCC3 (V, E) do artigo de Pierce Portanto, temos uma lista de vértices na entrada e (graças a Pierce) um certo índice do componente de forte conectividade ao qual esse vértice na saída pertence. O próximo passo é classificar de forma estável os vértices de acordo com o número de série do componente. Existe um algoritmo para essa tarefa, chamado de
contagem de contagem , que executa isso em
O(n) tempo.
No processo de reunir o algoritmo em uma pilha, verificou-se que o fato de ser natural fornecer a classificação topológica
oposta está saindo muito de Taryan - então os ramos vizinhos do gráfico (sem uma relação de ordem entre eles) serão numerados para trás, então as partes do gráfico não serão tendo qualquer conexão entre si, acabam na ordem inversa ...
A resposta
Então a solução final:
- Nós numeramos os vértices da lista original.
O(|V|) - Classificamos as arestas de cada vértice de acordo com o número do vértice ao qual a aresta vai.
O(|e| log |e|) - Usando o algoritmo Pierce, encontramos e numeramos os componentes de uma conexão forte.
O(|V|) - Usando a classificação por contagem, classificamos os vértices com base nos números dos componentes fortemente conectados que eles receberam.
O(|V|)
Código GitHub, Java, domínio público . Pode-se notar que, para garantir a estabilidade da classificação, o algoritmo Pierce é ligeiramente modificado e ignora os vértices na ordem inversa.
Mas por que ???
E agora o pano de fundo, por que tudo isso era necessário. Ao carregar / descarregar bibliotecas dinâmicas (.so), a glibc precisa decidir em qual ordem inicializar as variáveis estáticas. Variáveis dependem umas das outras, dependem de diferentes funções, etc. Em geral, tudo isso forma o próprio gráfico no qual existem ciclos e os quais devem ser classificados.
Era uma vez, um código bastante abaixo do ideal que executava a tarefa para
O(n^2) estava envolvido nessa tarefa. E, em geral, isso realmente não incomodou ninguém, até que em 2012 foi
descoberto que o código não estava funcionando corretamente e, em alguns casos, estava errado.
Os homens severos da RedHat pensaram, pensaram e estragaram mais alguns ciclos lá de cima. Os casos de problemas foram reparados, mas o algoritmo começou a funcionar para
O(n^3) , e isso já se tornou perceptível e, em alguns aplicativos, levou várias dezenas de segundos, o que foi um
erro em 2013. Além disso, o autor do bug descobriu casos em que o algoritmo com
O(n^3) também O(n^3) errado . Ele sugeriu o uso do algoritmo Taryan, embora o patch com correções nunca tenha sido projetado.
E o tempo passou, a glibc desacelerou sem piedade e em 2015 houve
outra tentativa de reparar o algoritmo . Infelizmente, sem sucesso, o algoritmo foi escolhido
O(n^2) , além de confundir os ramos do gráfico, entre os quais a ordem não é definida.
Hoje é o ano de 2019, a glibc ainda está desacelerando. A julgar por quanto tempo levei para resolver o problema, as chances de trazê-lo ao fim são significativamente inferiores a 100%. Isso é ainda mais agravado pelo fato de que as coisas estão acontecendo em C, sem suporte a IDE, no código de estilo de codificação GNU, corredor de teste louco (“se você quiser executar o teste novamente, exclua o arquivo .out correspondente”). E para que a glibc dê uma olhada no seu patch, você precisa seguir o procedimento de
atribuição de direitos autorais , emitir o patch corretamente e o diabo sabe o que mais. Portanto, para pelo menos remover a questão de inventar um algoritmo que resolva o problema, este post foi escrito.