Como posso encontrar todos os caminhos através de um conjunto de dados nós em um DAG?

Question

Eu tenho uma lista de itens (nós azuis abaixo) que são categorizados pelos usuários do meu aplicativo. As próprias categorias podem ser agrupados e categorizados-se.

A estrutura resultante pode ser representado como um Directed acíclico Gráfico (DAG) onde os itens são pias na parte inferior da topologia do gráfico e as principais categorias são fontes. Note-se que, enquanto algumas das categorias pode ser bem definido, um monte vai ser definido pelo usuário e pode ser muito confuso.

Exemplo:

_{(fonte: theuprightape.net )}

Nessa estrutura, eu quero realizar as seguintes operações:

• encontrar todos os itens (pias) abaixo de um determinado nó (todos os itens na Europa)
• encontrar todos os caminhos (se houver) que passar por tudo de um conjunto de n nós (todos os itens enviados via SMTP de example.com)
• encontrar todos os nós que se encontram abaixo de todos um conjunto de nós (intersecção: alimentos marrom gói)

O primeiro parece bastante simples: iniciar no nó, siga todos os caminhos possíveis para o fundo e recolher os itens lá. No entanto, há uma abordagem mais rápida? Lembrando os nós que já passaram, provavelmente, ajuda a evitar repetições desnecessárias, mas há mais otimizações?

Como faço para ir sobre o segundo? Parece que o primeiro passo seria para determinar a altura de cada nó no conjunto, a fim de determinar em que uma (s) para iniciar e, em seguida, localizar todos os caminhos que abaixo que incluem o resto do conjunto. Mas esta é a abordagem melhor (ou mesmo um bom)?

O gráfico travessia algoritmos listados na Wikipedia todos parecem se preocupar com qualquer um encontrar um determinado nó ou o mais curto ou percurso de outra forma mais eficaz entre dois nós. Eu acho que ambos não é o que eu quero, ou eu simplesmente não consigo ver como isso se aplica ao meu problema? Onde mais eu deveria ler?

Answer 1

Parece-me que a sua essencialmente a mesma operação para todas as 3 perguntas. Você está sempre perguntando "Encontrar todas as X abaixo nó (s) Y, onde X é do tipo Z". Tudo que você precisa é um mecanismo genérico para 'localizar todos os nós abaixo do nó', (resolve Q3) e, em seguida, você pode filtrar os resultados para 'nodetype = sink' (resolve Q1). Para Q2, você tem o ponto de partida (o conjunto de nós) e seu ponto final (qualquer pia abaixo do ponto de partida) para que o seu conjunto solução é todos os caminhos sejam iniciados nó especificado para a pia. Assim, gostaria de sugerir que o que você tem basicamente uma é uma árvore, e algoritmos básicos árvore-de travessia seria o caminho a percorrer.

Answer 2

Apesar do fato de que seu gráfico é acíclico, as operações que você cita lembrar-me de aspectos semelhantes de análise de gráfico de controle de fluxo. Há um rico conjunto de algoritmos baseados em domínio que podem ser aplicáveis. Por exemplo, a sua terceira operação faz-me lembrar od computação fronteiras de dominância; Eu acredito que o algoritmo iria trabalhar diretamente se você introduzir temporariamente "entrada" e nós "Exit". O nó de entrada conecta o "conjunto dado de nós" e os nós de saída conecta as pias.

Veja também algoritmos básicos de rel="nofollow noreferrer"> Robert Tarjan.