Eu tenho um DAG de dependências que contém muitas bordas redundantes (veja o exemplo abaixo). Eu quero um algoritmo "rápido" (ou seja, pode manipular um gráfico com vários milhares de nós / arestas) que encontre um sub-gráfico mínimo.
Por exemplo:
A -> B -> C
A -> C
nas palavras A é pré-requisito para B, e B é pré-requisito para C, e também A é pré-requisito para C. Nesse caso, A -> C é redundante (já que B já é necessário para atingir C e A é necessário para alcançar B) .
Já faz um tempo desde que estudei algoritmos e não sei por onde começar.
A propósito, não é crítico que o algoritmo encontre o mínimo global, o mínimo local seja bom (a redução de borda é apenas uma otimização do tempo de execução para o próximo estágio do processamento).
Além disso, percebo que este é um controle de qualidade da CS e não de programação, mas meu programa é escrito em Python, portanto, ficaria muito feliz em aprender sobre um módulo python ou código-fonte aberto para fazer essa redução, caso você saiba.
desde já, obrigado!
Respostas:
A redução transitiva de um gráfico direcionado AV Aho, MR Garey e JD Ullman
De acordo com a wikipedia , esse algoritmo é usado pela
tred
ferramenta de redução transitiva disponível no pacote GraphViz. Você pode executá-lo no seu gráfico e obter um gráfico reduzido.Esta pergunta é duplicada desta questão de stackoverflow .
código aqui
graphviz/tools/src/tred.c
faz uso DFS. ;-)fonte
tred
, obrigado.Acabei resolvendo assim:
Minha estrutura de dados é composta de
dependends
dicionário, de um ID de nó a uma lista de nós que dependem dele (ou seja, seus seguidores no DAG).Não calculei a complexidade exata, mas engoliu meu gráfico de vários milhares em uma fração de segundo.
fonte