ToposortDAGSolver

java.lang.Object
- graphs.shortestpaths.ToposortDAGSolver<V>

Type Parameters:

V - the type of vertices.

All Implemented Interfaces:

ShortestPathSolver<V>
```
public class ToposortDAGSolver<V>
extends Object
implements ShortestPathSolver<V>
```
Topological sorting implementation of the ShortestPathSolver interface for directed acyclic graphs.

See Also:

ShortestPathSolver

Nested Class Summary
- Nested classes/interfaces inherited from interface graphs.shortestpaths.ShortestPathSolver
  ShortestPathSolver.Constructor<V>

Field Summary

Fields
Modifier and Type Field Description

private Map<V,Double> distTo

private Map<V,Edge<V>> edgeTo

Constructor Summary

Constructors
Constructor	Description
`ToposortDAGSolver(Graph<V> graph, V start)`	Constructs a new instance by executing the toposort-DAG-shortest-paths algorithm on the graph from the start.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`private void`	`dfsPostOrder(Graph<V> graph, V start, Set<V> visited, List<V> result)`	Recursively adds nodes from the graph to the result in DFS postorder from the start vertex.
`List<V>`	`solution(V goal)`	Returns the single-pair shortest path from a start vertex to the goal.

Methods inherited from class java.lang.Object
clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - edgeTo
```
private final Map<V,Edge<V>> edgeTo
```
  - distTo
```
private final Map<V,Double> distTo
```
- Constructor Detail
  - ToposortDAGSolver
```
public ToposortDAGSolver(Graph<V> graph,
                         V start)
```
    Constructs a new instance by executing the toposort-DAG-shortest-paths algorithm on the graph from the start.
    
    Parameters:
    
    graph - the input graph.
    
    start - the start vertex.
- Method Detail
  - dfsPostOrder
```
private void dfsPostOrder(Graph<V> graph,
                          V start,
                          Set<V> visited,
                          List<V> result)
```
    Recursively adds nodes from the graph to the result in DFS postorder from the start vertex.
    
    Parameters:
    
    graph - the input graph.
    
    start - the start vertex.
    
    visited - the set of visited vertices.
    
    result - the destination for adding nodes.
  - solution
```
public List<V> solution(V goal)
```
    Description copied from interface: ShortestPathSolver
    
    Returns the single-pair shortest path from a start vertex to the goal.
    
    Specified by:
    
    solution in interface ShortestPathSolver<V>
    
    Parameters:
    
    goal - the goal vertex.
    
    Returns:
    
    a list of vertices representing the shortest path.