Class YenKShortestPaths

java.lang.Object

org.unibl.etf.pj2.app.pathfinding.yen.YenKShortestPaths

public class YenKShortestPaths
extends Object

Klasa rukovatelj Jenovim algoritmom za K najkracih putanja izmedju dva zadata cvora usmjerenog grafa. Jenov algoritam koristi Dajkstrin algoritam za najkracu putanju izmedju dva cvora kao podalgoritam kojim otkriva K najkracih putanja.

Author:

Nikola Markovic

Field Summary

Fields

Modifier and Type	Field	Description
private final Map<String,List<GraphEdge>>	adjacency
private final String	source
private final String	target

Constructor Summary

Constructors

Constructor	Description
YenKShortestPaths(org.graphstream.graph.Graph graph, String source, String target)

Method Summary

Modifier and Type	Method	Description
private Map<String,List<GraphEdge>>	buildAdjacencyMap(org.graphstream.graph.Graph graph)	Metoda koja kreira listu susjednosti (u obliku mape) cvorova polaznog GraphStream grafa.
private PathObject	dijkstra(String start, Set<String> bannedNodes, Set<String> bannedEdges)	Implementacija Dajkstrinog podalgoritma kao driver algoritma za Jenov.
private double	findEdgeCost(String from, String to)	Metoda za brzi pronalazak tezine izmedju dva cvora.
List<PathObject>	yen(int K)	Glavna metoda Jenovog algoritma ciji rezultat se dalje primjenjuje.

Methods inherited from class java.lang.Object

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

Field Details

adjacency

private final Map<String,List<GraphEdge>> adjacency

source

private final String source

target

private final String target

Constructor Details

YenKShortestPaths

public YenKShortestPaths(org.graphstream.graph.Graph graph,
 String source,
 String target)

Parameters:

graph - Graf objekat (interfejs koji polimorfno reprezentuje npr. SingleGraph ili MultiGraph tipove)

source - ID cvora polaska

target - ID cvora destinacije

Method Details

buildAdjacencyMap

private Map<String,List<GraphEdge>> buildAdjacencyMap(org.graphstream.graph.Graph graph)

Metoda koja kreira listu susjednosti (u obliku mape) cvorova polaznog GraphStream grafa.

Parameters:

graph - Graf objekat

Returns:

HashMap objekat sa Stringovima kao kljucevima i listom GraphEdge objekata kao vrijednostima

dijkstra

private PathObject dijkstra(String start,
 Set<String> bannedNodes,
 Set<String> bannedEdges)

Implementacija Dajkstrinog podalgoritma kao driver algoritma za Jenov. Implementacija koristi prioritetni red umjesto nizova kako bi se postigla veca efikasnost za ogromne grafove.

Parameters:

start - Pocetni cvor

bannedNodes - Skup ID-jeva zabranjenih (ranije navedenih kao nevalidnih) cvorova

bannedEdges - Skup ID-jeva zabranjenih (ranije navedenih kao nevalidnih) grana

Returns:

PathObject objekat koji reprezentuje datu optimalnu putanju

yen

public List<PathObject> yen(int K)

Glavna metoda Jenovog algoritma ciji rezultat se dalje primjenjuje.

Parameters:

K - Broj najoptimalnijih putanji koje zelimo kao rezultat izvrsavanja algoritma

Returns:

Lista od tacno K PathObject objekata koji reprezentuju K najoptimalnijih putanji izmedju dva zadana cvora.

findEdgeCost

private double findEdgeCost(String from,
 String to)

Metoda za brzi pronalazak tezine izmedju dva cvora.

Parameters:

from - ID cvora polaska

to - ID cvora dolaska

Returns:

U zavisnosti od uspjesnosti:

• [tezina] - veza izmedju from i to postoji
• Double.POSITIVE_INFINITY - veza izmedju from i to ne postoji (sa odgovarajucim usmjerenjem)