org.amino.alg.graph
Class GraphAlg

java.lang.Object
  org.amino.alg.graph.GraphAlg

public final class GraphAlg
extends java.lang.Object

Author:

Zhi Gan

Method Summary

static <E> java.util.Collection<java.util.Collection<Node<E>>>	getConnectedComponents(UndirectedGraph<E> graph, java.util.concurrent.ExecutorService threadPool) parallel Connected Component algorithm based on [Steve Goddard 1996].
static <E> Graph<E>	getMST(UndirectedGraph graph, java.util.concurrent.ExecutorService pool) parallel MST algorithm based on Boruvka's algorithm.
static <E> double	getShortestPath(Graph<E> graph, java.util.concurrent.ExecutorService exec, E source, E end) This is an implementation of a parallelization of Dijkstra's shortest path algorithm described by Crauser, Mehlhorn, Meyer and Sanders in their paper "A Parallelization of Dijkstra's Shortest Path Algorithm" in 23rd Symposium on Mathematical Foundations of Computer Science, 1998.
static <E> double	getShortestPath(Graph<E> graph, java.util.concurrent.ExecutorService exec, Node<E> source, Node<E> end) This is an implementation of a parallelization of Dijkstra's shortest path algorithm described by Crauser, Mehlhorn, Meyer and Sanders in their paper "A Parallelization of Dijkstra's Shortest Path Algorithm" in 23rd Symposium on Mathematical Foundations of Computer Science, 1998.
static <E> java.util.Collection<java.util.Collection<Node<E>>>	getStrongComponents(DirectedGraph<E> graph, java.util.concurrent.ExecutorService threadPool) Parallel Strong Connected Component algorithm based on [LK Fleischer2000].

Methods inherited from class java.lang.Object

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

Method Detail

getStrongComponents

public static <E> java.util.Collection<java.util.Collection<Node<E>>> getStrongComponents(DirectedGraph<E> graph,
                                                                                          java.util.concurrent.ExecutorService threadPool)

Parallel Strong Connected Component algorithm based on [LK Fleischer2000]. The targeted graph is supposed not to be modified while computing SCC. some parameters to be set based on experiments result: 1 the initial capacity of hashset used in BFS visting 2 the initial capacity of hashset for "remain" set 3 the initial capacity of vector for scc 4 the threshold of divide-and-conquer

Type Parameters:

E - value type of the node in the target graph

Parameters:

graph - directed graph to compute strong components. The graph will not be modified

threadPool - the thread pool used to do computation

Returns:

a collection of strong components, each of which in turn is a collection of graph nodes

getConnectedComponents

public static <E> java.util.Collection<java.util.Collection<Node<E>>> getConnectedComponents(UndirectedGraph<E> graph,
                                                                                             java.util.concurrent.ExecutorService threadPool)

parallel Connected Component algorithm based on [Steve Goddard 1996]. Only the initial presentation of the algorithm in the paper, namely A0, is implemented. A0 is for the CREW-PRAM model, and A1 & A2 are the adaptation of A0 to mesh-connected computer. Currently, this algorithm just compute an undirected graph with vertices V={1,2,...,n}, for simplicity

Type Parameters:

E - value type of the node in the target graph

Parameters:

graph - undirected graph to compute connected components. The graph will not be modified

threadPool - the thread pool used to do computation

Returns:

a collection of connected components, each of which in turn is a collection of graph nodes

getMST

public static <E> Graph<E> getMST(UndirectedGraph graph,
                                  java.util.concurrent.ExecutorService pool)
                       throws java.lang.InterruptedException,
                              java.util.concurrent.ExecutionException

parallel MST algorithm based on Boruvka's algorithm.

Type Parameters:

E - value type of the node in the target graph

Parameters:

graph - the graph to compute minimum spanning tree

pool - external thread pool

Returns:

a minimum spanning tree in the form of undirected graph

Throws:

java.lang.InterruptedException - thrown exception if be interrupted

java.util.concurrent.ExecutionException - Exception thrown when attempting to retrieve the result of a task that aborted by throwing an exception

getShortestPath

public static <E> double getShortestPath(Graph<E> graph,
                                         java.util.concurrent.ExecutorService exec,
                                         E source,
                                         E end)

This is an implementation of a parallelization of Dijkstra's shortest path algorithm described by Crauser, Mehlhorn, Meyer and Sanders in their paper "A Parallelization of Dijkstra's Shortest Path Algorithm" in 23rd Symposium on Mathematical Foundations of Computer Science, 1998. To gain a complete understanding of this data structure, please first read this paper, available at: http://citeseer.ist.psu.edu/crauser98parallelization.html This paper propose simple criteria which divide Dijkstra's sequential SSSP algorithm into a number of phases,such that the operations within a phase can be done in parallel. In the first variant (OUT-version) we compute a threshold defined via the weights of the outgoing edges:let L=min{tent(u) + c(u,z) : u is queued and (u,z) belongs E} and remove all nodes v from the queue then dist(v) = tent(v). The threshold for the OUT-criterion can either be computed via a second priority queue for o(v) = tent(v) + min(c(u,v) : (u,v) belongs to E} or even on the fly while while removing nodes. The second variant, the IN-version, is defined via the incoming edges: let M = min{tent(u) : u is queued} and i(v) = tent(v) - min{c(u,v) : (u,v) belongs to E} for any queued vertex v. Then v can be safely removed from the queue if i(v) <= M. Removable nodes of the IN-type can be found efficiently by using an additional priority queue for i(.). Finally, the INOUT-applies both criteria in conjunction. Sample performance results here.

Type Parameters:

E - type of element on node

Parameters:

graph - Graph

exec - Thread pool for executing task in parallel.

source - source node

end - end node

Returns:

the length of shortest path from source node to end node

getShortestPath

public static <E> double getShortestPath(Graph<E> graph,
                                         java.util.concurrent.ExecutorService exec,
                                         Node<E> source,
                                         Node<E> end)

This is an implementation of a parallelization of Dijkstra's shortest path algorithm described by Crauser, Mehlhorn, Meyer and Sanders in their paper "A Parallelization of Dijkstra's Shortest Path Algorithm" in 23rd Symposium on Mathematical Foundations of Computer Science, 1998. To gain a complete understanding of this data structure, please first read this paper, available at: http://citeseer.ist.psu.edu/crauser98parallelization.html This paper propose simple criteria which divide Dijkstra's sequential SSSP algorithm into a number of phases,such that the operations within a phase can be done in parallel. In the first variant (OUT-version) we compute a threshold defined via the weights of the outgoing edges:let L=min{tent(u) + c(u,z) : u is queued and (u,z) belongs E} and remove all nodes v from the queue then dist(v) = tent(v). The threshold for the OUT-criterion can either be computed via a second priority queue for o(v) = tent(v) + min(c(u,v) : (u,v) belongs to E} or even on the fly while while removing nodes. The second variant, the IN-version, is defined via the incoming edges: let M = min{tent(u) : u is queued} and i(v) = tent(v) - min{c(u,v) : (u,v) belongs to E} for any queued vertex v. Then v can be safely removed from the queue if i(v) <= M. Removable nodes of the IN-type can be found efficiently by using an additional priority queue for i(.). Finally, the INOUT-applies both criteria in conjunction. Sample performance results here.

Type Parameters:

E - type of element on node

Parameters:

graph - Graph

exec - Thread pool for executing task in parallel.

source - source node

end - end node

Returns:

the length of shortest path from source node to end node