com.dpgil.pathlinker.path_linker.internal.util

Class Algorithms

java.lang.Object

com.dpgil.pathlinker.path_linker.internal.util.Algorithms

public class Algorithms
extends Object

// ------------------------------------------------------------------------- /** Algorithms class for the PathLinker plugin. Contains all the algorithms (Dijkstra's, Yen's KSP) used in PathLinker.

Version:

Apr 23, 2015

Author:

Daniel Gil

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Algorithms.PathWay Represents a pathway.

Constructor Summary

Constructors

Constructor and Description
Algorithms()

Method Summary

Modifier and Type	Method and Description
static ArrayList<org.cytoscape.model.CyNode>	constructNodeList(HashMap<org.cytoscape.model.CyNode,org.cytoscape.model.CyNode> previous, org.cytoscape.model.CyNode source, org.cytoscape.model.CyNode target) Finds a path from a source to a sink using a supplied previous node list
static Algorithms.PathWay	dijkstra(org.cytoscape.model.CyNetwork network, Map<org.cytoscape.model.CyNode,String> cyNodeToId, org.cytoscape.model.CyNode source, org.cytoscape.model.CyNode target) Computes the shortest path from a source to a sink in the supplied network
static org.cytoscape.model.CyEdge	getEdge(org.cytoscape.model.CyNetwork network, org.cytoscape.model.CyNode source, org.cytoscape.model.CyNode target) Returns an edge that connects source to target if it exists, null otherwise
static double	getWeight(org.cytoscape.model.CyNetwork network, org.cytoscape.model.CyEdge edge) Returns the weight of an edge in the network
static void	initializeHiddenEdges(Set<org.cytoscape.model.CyEdge> edges) Initializes the set of hidden edges.
static ArrayList<Algorithms.PathWay>	ksp(org.cytoscape.model.CyNetwork network, Map<org.cytoscape.model.CyNode,String> cyNodeToId, org.cytoscape.model.CyNode source, org.cytoscape.model.CyNode target, int maxK, boolean includePathScoreTies) Computes the k shortest acyclic paths in the supplied network using Yen's algorithm.
static HashMap<org.cytoscape.model.CyNode,Double>	reverseSingleSourceDijkstra(org.cytoscape.model.CyNetwork network, org.cytoscape.model.CyNode source) Computes the shortest distance from a source to every node in the graph
static void	setEdgeWeights(Map<org.cytoscape.model.CyEdge,Double> weights) Initializes our local copy of the edge weights
static void	setWeight(org.cytoscape.model.CyEdge edge, double value) Sets the weight of an edge in the network.
static Algorithms.PathWay	shortestPathAStar(org.cytoscape.model.CyNetwork network, Map<org.cytoscape.model.CyNode,String> cyNodeToId, org.cytoscape.model.CyNode source, org.cytoscape.model.CyNode target, HashMap<org.cytoscape.model.CyNode,Double> minDists) An implementation of the A* algorithm.
static HashMap<org.cytoscape.model.CyNode,Double>	singleSourceDijkstra(org.cytoscape.model.CyNetwork network, org.cytoscape.model.CyNode source) Computes the shortest distance from a source to every node in the graph
static void	sortResult(ArrayList<Algorithms.PathWay> result) Sort the list of the paths using its custom compareTo method

Methods inherited from class java.lang.Object

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

Constructor Detail

Algorithms

public Algorithms()

Method Detail

ksp

public static ArrayList<Algorithms.PathWay> ksp(org.cytoscape.model.CyNetwork network,
                                                Map<org.cytoscape.model.CyNode,String> cyNodeToId,
                                                org.cytoscape.model.CyNode source,
                                                org.cytoscape.model.CyNode target,
                                                int maxK,
                                                boolean includePathScoreTies)

Computes the k shortest acyclic paths in the supplied network using Yen's algorithm. Assumes that this is NOT a multigraph (there is at most one edge between any two nodes). A* is used as the pathfinding subroutine, with the distances in the input graph as a heuristic. Because the algorithm computes paths over subsets of the initial heuristic is valid and effective. If the graph contains n less than k paths, n paths will be returned.

Parameters:

network - the supplied network

cyNodeToId - the map that maps CyNode object to its string name

source - the source node

target - the target node

maxK - the number of shortest paths

includePathScoreTies - the option to include all paths of equal length

Returns:

a list of k-shortest paths in sorted order by cost

shortestPathAStar

public static Algorithms.PathWay shortestPathAStar(org.cytoscape.model.CyNetwork network,
                                                   Map<org.cytoscape.model.CyNode,String> cyNodeToId,
                                                   org.cytoscape.model.CyNode source,
                                                   org.cytoscape.model.CyNode target,
                                                   HashMap<org.cytoscape.model.CyNode,Double> minDists)

An implementation of the A* algorithm. Computes exact shortest paths in the network, utilizing the fact that the heuristic function is monotonic

Parameters:

network - the supplied network

cyNodeToId - the map that maps CyNode object to its string name

source - the source node

target - the target node

minDists - the map of nodes to their minimum distance from the target

Returns:

a path from source to target and its weight

reverseSingleSourceDijkstra

public static HashMap<org.cytoscape.model.CyNode,Double> reverseSingleSourceDijkstra(org.cytoscape.model.CyNetwork network,
                                                                                     org.cytoscape.model.CyNode source)

Computes the shortest distance from a source to every node in the graph

Parameters:

network - the supplied network

source - the source

Returns:

a map of nodes and their distances from the source

singleSourceDijkstra

public static HashMap<org.cytoscape.model.CyNode,Double> singleSourceDijkstra(org.cytoscape.model.CyNetwork network,
                                                                              org.cytoscape.model.CyNode source)

Computes the shortest distance from a source to every node in the graph

Parameters:

network - the supplied network

source - the source

Returns:

a map of nodes and their distances from the source

dijkstra

public static Algorithms.PathWay dijkstra(org.cytoscape.model.CyNetwork network,
                                          Map<org.cytoscape.model.CyNode,String> cyNodeToId,
                                          org.cytoscape.model.CyNode source,
                                          org.cytoscape.model.CyNode target)

Computes the shortest path from a source to a sink in the supplied network

Parameters:

network - the network

cyNodeToId - the map that maps CyNode object to its string name

source - the source node of the graph

target - the target node of the graph

Returns:

the path from source to target

setEdgeWeights

public static void setEdgeWeights(Map<org.cytoscape.model.CyEdge,Double> weights)

Initializes our local copy of the edge weights

Parameters:

weights - a map of the edge to its value

getWeight

public static double getWeight(org.cytoscape.model.CyNetwork network,
                               org.cytoscape.model.CyEdge edge)

Returns the weight of an edge in the network

Parameters:

network - the supplied network

edge - the edge to find the weight of

Returns:

double the weight of the edge. returns a very noticeable and obscure number if the weight is not in the network

setWeight

public static void setWeight(org.cytoscape.model.CyEdge edge,
                             double value)

Sets the weight of an edge in the network. Doesn't actually set the edge weight as an attribute, as that takes too much time. Instead, stores the edge weight in our copy of the weights local to the algorithm.

Parameters:

edge - the edge to set the weight of

value - the new weight of the edge

getEdge

public static org.cytoscape.model.CyEdge getEdge(org.cytoscape.model.CyNetwork network,
                                                 org.cytoscape.model.CyNode source,
                                                 org.cytoscape.model.CyNode target)

Returns an edge that connects source to target if it exists, null otherwise

Parameters:

network - the network

source - the source of the edge

target - the target of the edge

Returns:

the edge connecting source and target, null otherwise

constructNodeList

public static ArrayList<org.cytoscape.model.CyNode> constructNodeList(HashMap<org.cytoscape.model.CyNode,org.cytoscape.model.CyNode> previous,
                                                                      org.cytoscape.model.CyNode source,
                                                                      org.cytoscape.model.CyNode target)

Finds a path from a source to a sink using a supplied previous node list

Parameters:

previous - a map of node predecessors

source - the source node of the graph

target - the target node of the graph

Returns:

list of nodes in the path

initializeHiddenEdges

public static void initializeHiddenEdges(Set<org.cytoscape.model.CyEdge> edges)

Initializes the set of hidden edges. Used to start out the algorithm hiding all source in edges and target out edges.

Parameters:

edges - the initial hidden edges

sortResult

public static void sortResult(ArrayList<Algorithms.PathWay> result)

Sort the list of the paths using its custom compareTo method

Parameters:

result - the sorted list of pathss