Class AcyclicLP

java.lang.Object

AcyclicLP

public class AcyclicLP
extends java.lang.Object

Esta classe implementa um ADT para resolver o problema dos caminhos de peso máximo em um dag (digrafo acíclico) com pesos nos arcos. (O sufixo "LP" é uma abreviatura de "Longest Path".) Todos os caminhos começam num dado vértice s. Os pesos dos arcos são números reais arbitrários (positivos, negativos ou nulos).

Esta implementação usa um algoritmo de ordenação topológica para realizar a tarefa. O construtor consome tempo proporcional a V + E, sendo V o número de vértices e E o número de arcos do digrafo. Depois, os métodos distTo() e hasPathTo() consomem tempo constante e o método pathTo() consome tempo proporcional ao número de arcos do caminho devolvido.

(Esta implementação depende das classes EdgeWeightedDigraph.java, DirectedEdge.java, Topological.java.)

Documentação adicional: veja Seção 4.4 do livro Algorithms, 4th Edition, de Robert Sedgewick e Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
AcyclicLP(EdgeWeightedDigraph G, int s) Calcula uma arborescência de caminhos de pseso máximo, com raiz s, no dag G.

Method Summary

Methods

Modifier and Type	Method and Description
double	distTo(int v) Devolve o comprimento de um caminho de peso máximo do vértice s ao vértice v.
boolean	hasPathTo(int v) Existe caminho do vértice s ao vértice v?
static void	main(java.lang.String[] args) Teste de unidade.
java.lang.Iterable<DirectedEdge>	pathTo(int v) Devolve a sequência de vértices de um caminho de peso máximo do vértice s ao vértice v.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AcyclicLP

public AcyclicLP(EdgeWeightedDigraph G,
         int s)

Calcula uma arborescência de caminhos de pseso máximo, com raiz s, no dag G. (Para cada vértice v, essa arborescência contém um caminho de peso máximo de s a v.)

Throws:

java.lang.IllegalArgumentException - se o digrafo G não for um dag.

java.lang.IllegalArgumentException - se s não for um vértice válido ou seja, se não estiver em 0..V-1.

Method Detail

distTo

public double distTo(int v)

Devolve o comprimento de um caminho de peso máximo do vértice s ao vértice v. Devolve -infinito se não existe caminho de s a v.

hasPathTo

public boolean hasPathTo(int v)

Existe caminho do vértice s ao vértice v?

pathTo

public java.lang.Iterable<DirectedEdge> pathTo(int v)

Devolve a sequência de vértices de um caminho de peso máximo do vértice s ao vértice v. O caminho é devolvido como um Iterable de arcos.

main

public static void main(java.lang.String[] args)

Teste de unidade. Testa o funcionamento da ADT AcyclicLP. Recebe, na linha de comando, um vértice s e o nome de arquivo que descreve um dag com pesos nos arcos. (A primeira linha do arquivo é o número de vértices do dag; a segunda linha é o número de arcos do dag; cada uma das linhas seguintes tem um par v w de inteiros seguido de um número real p arbitrário, o que representa um arco v-w com peso p.) Para cada vértice v, calcula e imprime um caminho de peso máximo de s a v. Como arquivo de entrada, você pode usar http://algs4.cs.princeton.edu/44sp/tinyEWDAG.txt.