Module xyz.cofe.ecolls

Package xyz.cofe.collection.graph

Class PathFinder<N,E>

java.lang.Object

xyz.cofe.collection.graph.PathFinder<N,E>

Type Parameters:

N - Тип вершины

E - Тип ребра

All Implemented Interfaces:

Iterator<Path<N,E>>

public class PathFinder<N,E>
extends Object
implements Iterator<Path<N,E>>

Поиск путей в графе.

Производит обход графа формируя возможные пути. Обход производится по крайчащим путям. Конечная вершина поиска определяется пользователем данного класса.

За один вызов next() выдает один возможный путь из указанной точки.

Author:

gocha

Field Summary

Fields

Modifier and Type	Field	Description
protected Comparator<Path<N,E>>	comparator
protected Path.Direction	direction	Направление движения
protected SingleDirectedGraph<N,E>	graph	Граф в котором производится поиск
protected List<Path<N,E>>	paths	Список путей используемых в поиске.

Constructor Summary

Constructors

Constructor	Description
PathFinder(SingleDirectedGraph<N,E> graph, N start, Path.Direction direction, Comparator<Path<N,E>> comparator)	Конструктор
PathFinder(SingleDirectedGraph<N,E> graph, N start, Path.Direction direction, Function<Edge<N,E>,Double> getWeight)	Конструктор

Method Summary

Modifier and Type	Method	Description
protected Path<N,E>	append(Path<N,E> path, Edge<N,E> e)	Добавляет ребро в конец пути
protected Comparator<Path<N,E>>	createComparatorFrom(Function<Edge<N,E>,Double> getWeight)	Создание Comparator для пути
protected Path<N,E>	createPath()	Создаает путь
protected List<Path<N,E>>	createPathsList()	Создает список путей
protected double	getIntWeightOf(Path<N,E> path, Function<Edge<N,E>,Double> getWeight)	Полчение веса пути
protected Iterable<Edge<N,E>>	getNextEdges(N n)	Извлекает исходящие ребра/дуги из вершины n в соот. движению.
boolean	hasNext()
Path<N,E>	next()
void	remove()

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Iterator

forEachRemaining

Field Detail

graph

protected SingleDirectedGraph<N,E> graph

Граф в котором производится поиск

direction

protected Path.Direction direction

Направление движения

paths

protected List<Path<N,E>> paths

Список путей используемых в поиске. Используются их конечные вершины.

comparator

protected Comparator<Path<N,E>> comparator

Constructor Detail

PathFinder

public PathFinder(SingleDirectedGraph<N,E> graph,
                  N start,
                  Path.Direction direction,
                  Function<Edge<N,E>,Double> getWeight)

Конструктор

Parameters:

graph - Одно направленный граф

start - Начальная вершина пути

direction - Направление движения

getWeight - Получение веса ребра, вес должен быть положительным или равен нулю

PathFinder

public PathFinder(SingleDirectedGraph<N,E> graph,
                  N start,
                  Path.Direction direction,
                  Comparator<Path<N,E>> comparator)

Конструктор

Parameters:

graph - Одно направленный граф

start - Начальная вершина пути

direction - Направление движения

comparator - Сравнение длины путей

Method Detail

getIntWeightOf

protected double getIntWeightOf(Path<N,E> path,
                                Function<Edge<N,E>,Double> getWeight)

Полчение веса пути

Parameters:

path - Путь

getWeight - Получение веса ребра

Returns:

Вес пути

createComparatorFrom

protected Comparator<Path<N,E>> createComparatorFrom(Function<Edge<N,E>,Double> getWeight)

Создание Comparator для пути

Parameters:

getWeight - Получение веса ребра

Returns:

Comparator

createPathsList

protected List<Path<N,E>> createPathsList()

Создает список путей

Returns:

Список путей

createPath

protected Path<N,E> createPath()

Создаает путь

Returns:

Путь

append

protected Path<N,E> append(Path<N,E> path,
                                 Edge<N,E> e)

Добавляет ребро в конец пути

Parameters:

path - Путь

e - Ребро

Returns:

Новый путь

getNextEdges

protected Iterable<Edge<N,E>> getNextEdges(N n)

Извлекает исходящие ребра/дуги из вершины n в соот. движению.

Parameters:

n - Вершина

Returns:

Ребра/дуги направления движения.

hasNext

public boolean hasNext()

Specified by:

hasNext in interface Iterator<N>

next

public Path<N,E> next()

Specified by:

next in interface Iterator<N>

remove

public void remove()

Specified by:

remove in interface Iterator<N>