Package dsa

Class DFSDiPaths

java.lang.Object

dsa.DFSDiPaths

All Implemented Interfaces:

Paths

public class DFSDiPaths
extends Object
implements Paths

An immutable data type to compute paths from a fixed source vertex to any other vertex in a directed graph.

Constructor Summary

Constructors

Constructor	Description
DFSDiPaths(DiGraph G, int s)	Computes paths from source vertex s to every other vertex in the digraph G.

Method Summary

Modifier and Type	Method	Description
double	distTo(int v)	Returns the shortest distance between a designated source vertex and vertex v, or infinity.
boolean	hasPathTo(int v)	Returns true if there is a path between a designated source vertex and vertex v, and false otherwise.
static void	main(String[] args)	Unit tests the data type.
Iterable<Integer>	pathTo(int v)	Returns a path between a designated source vertex and vertex v, or null.

Methods inherited from class java.lang.Object

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

Constructor Detail

DFSDiPaths

public DFSDiPaths(DiGraph G,
                  int s)

Computes paths from source vertex s to every other vertex in the digraph G.

Parameters:

G - the digraph.

s - the source vertex.

Method Detail

hasPathTo

public boolean hasPathTo(int v)

Description copied from interface: Paths

Returns true if there is a path between a designated source vertex and vertex v, and false otherwise.

Specified by:

hasPathTo in interface Paths

Parameters:

v - the vertex.

Returns:

true if there is a path between a designated source vertex and vertex v, and false otherwise.

pathTo

public Iterable<Integer> pathTo(int v)

Description copied from interface: Paths

Returns a path between a designated source vertex and vertex v, or null.

Specified by:

pathTo in interface Paths

Parameters:

v - the vertex.

Returns:

a path between a designated source vertex and vertex v, or null.

distTo

public double distTo(int v)

Description copied from interface: Paths

Returns the shortest distance between a designated source vertex and vertex v, or infinity.

Specified by:

distTo in interface Paths

Parameters:

v - the vertex.

Returns:

the shortest distance between a designated source vertex and vertex v, or infinity.

main

public static void main(String[] args)

Unit tests the data type.

Parameters:

args - the command-line arguments.