jsondiscoverer.util

Class DijkstraSolver

java.lang.Object

jsondiscoverer.util.DijkstraSolver

public class DijkstraSolver
extends java.lang.Object

This class applies the Dijkstra algorithm to get the shortest path between two nodes.

Applied to EMF models, nodes are EClass elements and links are EReference elements. We consider the distance between two nodes as the number of EReferences existing between such nodes (or infinite if there is not a path).

This code has been adapted from the one published by Lars Vogel published here

Author:

Javier Canovas (me@jlcanovas.es)

Field Summary

Fields

Modifier and Type	Field and Description
private java.util.Map<org.eclipse.emf.ecore.EClass,java.lang.Integer>	distance Distance matrix between each pair of nodes
private java.util.List<org.eclipse.emf.ecore.EReference>	edges The list of edges of the graph
private java.util.List<org.eclipse.emf.ecore.EClass>	nodes The list of nodes of the graph
private java.util.Map<org.eclipse.emf.ecore.EClass,org.eclipse.emf.ecore.EClass>	predecessors The list of predecesors in the set of calculated paths
private java.util.Set<org.eclipse.emf.ecore.EClass>	settledNodes Visited nodes
private java.util.Set<org.eclipse.emf.ecore.EClass>	unSettledNodes Unvisited nodes

Constructor Summary

Constructors

Constructor and Description
DijkstraSolver(org.eclipse.emf.ecore.EPackage ePackage) Constructs a new Dijkstra solver taking all the EClass elements as nodes and their EReferences as references/links between the nodes.

Method Summary

Modifier and Type	Method and Description
void	execute(org.eclipse.emf.ecore.EClass source) Executes the algorithm to create the auciliar table with all the possible shortest paths
private void	findMinimalDistances(org.eclipse.emf.ecore.EClass node) Looks for the minimal distance between two nodes given a source node (as EClass elements)
private int	getDistance(org.eclipse.emf.ecore.EClass node, org.eclipse.emf.ecore.EClass target) Returns the distance between two nodes (as EClass elements)
private org.eclipse.emf.ecore.EClass	getMinimum(java.util.Set<org.eclipse.emf.ecore.EClass> vertexes) Obtained the nearest node of a set of nodes (as EClasses)
private java.util.List<org.eclipse.emf.ecore.EClass>	getNeighbors(org.eclipse.emf.ecore.EClass node) Returns the list of neighbors for a given node.
java.util.LinkedList<org.eclipse.emf.ecore.EClass>	getPath(org.eclipse.emf.ecore.EClass target) Gets the path to a node as a list of EClass elements to be crossed.
private int	getShortestDistance(org.eclipse.emf.ecore.EClass destination) Calculates the shortest distance with regard to a ndoe (as EClass)
private boolean	isSettled(org.eclipse.emf.ecore.EClass vertex) Checks if a node has already been visited by the algorithm

Methods inherited from class java.lang.Object

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

Field Detail

nodes

private final java.util.List<org.eclipse.emf.ecore.EClass> nodes

The list of nodes of the graph

edges

private final java.util.List<org.eclipse.emf.ecore.EReference> edges

The list of edges of the graph

settledNodes

private java.util.Set<org.eclipse.emf.ecore.EClass> settledNodes

Visited nodes

unSettledNodes

private java.util.Set<org.eclipse.emf.ecore.EClass> unSettledNodes

Unvisited nodes

predecessors

private java.util.Map<org.eclipse.emf.ecore.EClass,org.eclipse.emf.ecore.EClass> predecessors

The list of predecesors in the set of calculated paths

distance

private java.util.Map<org.eclipse.emf.ecore.EClass,java.lang.Integer> distance

Distance matrix between each pair of nodes

Constructor Detail

DijkstraSolver

public DijkstraSolver(org.eclipse.emf.ecore.EPackage ePackage)

Constructs a new Dijkstra solver taking all the EClass elements as nodes and their EReferences as references/links between the nodes.

Parameters:

ePackage - The metamodel (as EPackage)

Method Detail

execute

public void execute(org.eclipse.emf.ecore.EClass source)

Executes the algorithm to create the auciliar table with all the possible shortest paths

Parameters:

source - The source element of the path (as EClass)

findMinimalDistances

private void findMinimalDistances(org.eclipse.emf.ecore.EClass node)

Looks for the minimal distance between two nodes given a source node (as EClass elements)

Parameters:

node - The source node to start the calculation (as EClass)

getDistance

private int getDistance(org.eclipse.emf.ecore.EClass node,
                        org.eclipse.emf.ecore.EClass target)

Returns the distance between two nodes (as EClass elements)

Parameters:

node - The sourcce node (as EClass)

target - The target node (as EClass)

Returns:

The distance between the two nodes (a value between 1 and Integer.MAX_VALUE)

getNeighbors

private java.util.List<org.eclipse.emf.ecore.EClass> getNeighbors(org.eclipse.emf.ecore.EClass node)

Returns the list of neighbors for a given node.

As we deal with EClass elements, the neighbors of an EClass are all the EClass elements linked with at least one EReference.

Parameters:

node - The target node

Returns:

The list of neighbors (as EClass elements)

getMinimum

private org.eclipse.emf.ecore.EClass getMinimum(java.util.Set<org.eclipse.emf.ecore.EClass> vertexes)

Obtained the nearest node of a set of nodes (as EClasses)

Parameters:

vertexes - The set of nodes (as EClass)

Returns:

The nearest node (as EClass)

isSettled

private boolean isSettled(org.eclipse.emf.ecore.EClass vertex)

Checks if a node has already been visited by the algorithm

Parameters:

vertex - The node (as EClass)

Returns:

True if the node has already been visited

getShortestDistance

private int getShortestDistance(org.eclipse.emf.ecore.EClass destination)

Calculates the shortest distance with regard to a ndoe (as EClass)

Parameters:

destination - The target node (as EClass)

Returns:

The distance (a value between 1 and Integer.MAX_VALUE)

getPath

public java.util.LinkedList<org.eclipse.emf.ecore.EClass> getPath(org.eclipse.emf.ecore.EClass target)

Gets the path to a node as a list of EClass elements to be crossed.

Parameters:

target - The target element to visit (as EClass)

Returns:

List of EClass elements