Reduzindo arestas redundantes a partir de um gráfico de dependência

8

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!

Iftah
fonte
Fiquei me perguntando se DFS poderia ajudar aqui?
Pratik Deoghare
3
Você está procurando a "redução transitiva" do seu gráfico de dependência.
Dave Clarke
Encontre os componentes fortemente conectados. Deixe apenas uma aresta entre cada par de componentes. Para cada componente fortemente conectado, você precisa encontrar um número mínimo de ciclos que o cubram. Encontrar um número mínimo de ciclos parece estar completo como NP, uma vez que decidirá a Hamiltonicidade, mas como você só precisa de um mínimo local, basta remover as arestas de cada componente até perder sua forte conectividade.
Kaveh

Respostas:

13

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 tredferramenta 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. ;-)

Pratik Deoghare
fonte
2
Eu não sabia tred, obrigado.
Anthony Labarre
1
Obrigado MachineCharmer. Estou fora de uma universidade e não consigo fazer o download do artigo sem pagar US $ 25 ... existe alguma fonte on-line gratuita que descreva esse algoritmo? A fonte tred é pequena e legível, mas sem explicações.
Iftah 27/06
Não. Não há link para download gratuito para esse documento. Mas você pode ter amigos em alguma universidade :) #
Pratik Deoghare
-1

Acabei resolvendo assim:

Minha estrutura de dados é composta de dependendsdicioná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.

_transitive_closure_cache = {}
def transitive_closure(self, node_id):
    """returns a set of all the nodes (ids) reachable from given node(_id)"""
    global _transitive_closure_cache
    if node_id in _transitive_closure_cache:
        return _transitive_closure_cache[node_id]
    c = set(d.id for d in dependents[node_id])
    for d in dependents[node_id]:
        c.update(transitive_closure(d.id))  # for the non-pythonists - update is update self to Union result
    _transitive_closure_cache[node_id] = c
    return c

def can_reduce(self, source_id, dest_id):
    """returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
    for d in dependents[source_id]:
        if d.id == dest_id:
            continue
        if dest_id in transitive_closure(d.id):
            return True # the dest node can be reached in a less direct path, then this link is redundant
    return False

# Reduce redundant edges:
for node in nodes:      
    dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]
Iftah
fonte