Como posso encontrar todos os caminhos através de um conjunto de dados nós em um DAG?
-
11-07-2019 - |
Pergunta
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?
Solução
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.
Outras dicas
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.