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:
java.util.Iterator<Path<N,​E>>
public class PathFinder<N,​E>
extends java.lang.Object
implements java.util.Iterator<Path<N,​E>>
Поиск путей в графе.

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

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

Author:
gocha

  • Field Summary

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

  • Constructor Summary

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

  • Method Summary

    Modifier and Type Method Description
    protected Path<N,​E> append​(Path<N,​E> path, Edge<N,​E> e)
    Добавляет ребро в конец пути
    protected java.util.Comparator<Path<N,​E>> createComparatorFrom​(java.util.function.Function<Edge<N,​E>,​java.lang.Double> getWeight)
    Создание Comparator для пути
    protected Path<N,​E> createPath()
    Создаает путь
    protected java.util.List<Path<N,​E>> createPathsList()
    Создает список путей
    protected double getIntWeightOf​(Path<N,​E> path, java.util.function.Function<Edge<N,​E>,​java.lang.Double> getWeight)
    Полчение веса пути
    protected java.lang.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 Details

    • graph

      protected SingleDirectedGraph<N,​E> graph
      Граф в котором производится поиск

    • direction

      protected Path.Direction direction
      Направление движения

    • paths

      protected java.util.List<Path<N,​E>> paths
      Список путей используемых в поиске. Используются их конечные вершины.

    • comparator

      protected java.util.Comparator<Path<N,​E>> comparator

  • Constructor Details

    • PathFinder

      public PathFinder​(SingleDirectedGraph<N,​E> graph, N start, Path.Direction direction, java.util.function.Function<Edge<N,​E>,​java.lang.Double> getWeight)
      Конструктор
      Parameters:
      graph - Одно направленный граф
      start - Начальная вершина пути
      direction - Направление движения
      getWeight - Получение веса ребра, вес должен быть положительным или равен нулю

    • PathFinder

      public PathFinder​(SingleDirectedGraph<N,​E> graph, N start, Path.Direction direction, java.util.Comparator<Path<N,​E>> comparator)
      Конструктор
      Parameters:
      graph - Одно направленный граф
      start - Начальная вершина пути
      direction - Направление движения
      comparator - Сравнение длины путей

  • Method Details

    • getIntWeightOf

      protected double getIntWeightOf​(Path<N,​E> path, java.util.function.Function<Edge<N,​E>,​java.lang.Double> getWeight)
      Полчение веса пути
      Parameters:
      path - Путь
      getWeight - Получение веса ребра
      Returns:
      Вес пути

    • createComparatorFrom

      protected java.util.Comparator<Path<N,​E>> createComparatorFrom​(java.util.function.Function<Edge<N,​E>,​java.lang.Double> getWeight)
      Создание Comparator для пути
      Parameters:
      getWeight - Получение веса ребра
      Returns:
      Comparator

    • createPathsList

      protected java.util.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 java.lang.Iterable<Edge<N,​E>> getNextEdges​(N n)
      Извлекает исходящие ребра/дуги из вершины n в соот. движению.
      Parameters:
      n - Вершина
      Returns:
      Ребра/дуги направления движения.

    • hasNext

      public boolean hasNext()
      Specified by:
      hasNext in interface java.util.Iterator<N>

    • next

      public Path<N,​E> next()
      Specified by:
      next in interface java.util.Iterator<N>

    • remove

      public void remove()
      Specified by:
      remove in interface java.util.Iterator<N>