org.rollerjm.graph
Class PathFinder

java.lang.Object
  |
  +--org.rollerjm.graph.PathFinder

public class PathFinder

extends java.lang.Object

Title: graphs

Description: contains all the search methods.

Copyright: Copyright (c) 2002

Company:

Version:

1.0

Author:

Jean-Michel Garnier

Field Summary

private java.lang.Object	destination Where we gonna go now ?
private Dijkstra	dijkstra We need our favourite algorithm
private IGraph	graph the graph we are gonna to explore
private int	maxDistance The total distance.
private int	maxLength The lenght of a path is different from its distance.
private java.util.ArrayList	solutionsList list of Path

Constructor Summary

PathFinder(IGraph graph)

Method Summary

private void	findPaths(java.lang.Object start, java.lang.Object destination, int maxLength) Explore the graph from a start vertex to a destination vertex and find all the paths which have a length <= maxLength.
java.util.List	findPathsWithExactLength(java.lang.Object start, java.lang.Object destination, int exactLength)
java.util.List	findPathsWithMaximumDistance(java.lang.Object start, java.lang.Object destination, int maxDistance) Explore the graph from a start vertex to a destination vertex and find all the paths which have a total distance <= maxDistance.
java.util.List	findPathsWithMaximumLength(java.lang.Object start, java.lang.Object destination, int maxLength)
Path	getShortestPath(java.lang.Object start, java.lang.Object destination) wrapper around Dijkstra method
int	getShortestWeightDistance(java.lang.Object start, java.lang.Object destination) wrapper around Dijkstra method
private void	searchDistance(Path path) Recursive method.
private void	searchLength(Path path) Recursive method.

Methods inherited from class java.lang.Object

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

Field Detail

graph

private IGraph graph

the graph we are gonna to explore

dijkstra

private Dijkstra dijkstra

We need our favourite algorithm

destination

private java.lang.Object destination

Where we gonna go now ?

maxLength

private int maxLength

The lenght of a path is different from its distance. i.e. : lenght(A-B-C) = 2 !

maxDistance

private int maxDistance

The total distance. distance(A-B-C) = distance(A-B) + distance(B-C)

solutionsList

private java.util.ArrayList solutionsList

list of Path

Constructor Detail

PathFinder

public PathFinder(IGraph graph)

Parameters:

graph -

Method Detail

getShortestWeightDistance

public int getShortestWeightDistance(java.lang.Object start,
                                     java.lang.Object destination)

wrapper around Dijkstra method

Parameters:

start -

destination -

Returns:

getShortestPath

public Path getShortestPath(java.lang.Object start,
                            java.lang.Object destination)

wrapper around Dijkstra method

Parameters:

start -

destination -

Returns:

findPathsWithMaximumLength

public java.util.List findPathsWithMaximumLength(java.lang.Object start,
                                                 java.lang.Object destination,
                                                 int maxLength)

Parameters:

start -

destination -

maxLength -

Returns:

list of paths

findPathsWithExactLength

public java.util.List findPathsWithExactLength(java.lang.Object start,
                                               java.lang.Object destination,
                                               int exactLength)

Parameters:

start -

destination -

exactLength -

Returns:

list of paths

findPathsWithMaximumDistance

public java.util.List findPathsWithMaximumDistance(java.lang.Object start,
                                                   java.lang.Object destination,
                                                   int maxDistance)

Explore the graph from a start vertex to a destination vertex and find all the paths which have a total distance <= maxDistance. If the destination is reached, its never mind ! continue again and again until the stop condition.

Parameters:

start -

destination -

maxDistance -

Returns:

findPaths

private void findPaths(java.lang.Object start,
                       java.lang.Object destination,
                       int maxLength)

Explore the graph from a start vertex to a destination vertex and find all the paths which have a length <= maxLength. If the destination is reached, its never mind ! continue again and again until the stop condition.

Parameters:

start -

destination -

maxLength -

searchLength

private void searchLength(Path path)

Recursive method. Explore the graph from one starting path and store all the paths that reach the destination Stop its exploration it a path length is > maxLenght

Parameters:

path -

searchDistance

private void searchDistance(Path path)

Recursive method. Explore the graph from one starting path and store all the paths that reach the destination Stop its exploration it a the path distance is > maxDistance

Parameters:

path -