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

getMST(UndirectedGraph graph,
java.util.concurrent.ExecutorService pool)
parallel MST algorithm based on Boruvka's algorithm. 
static

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

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 
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 divideandconquer
 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 modifiedthreadPool
 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 CREWPRAM model, and A1 & A2 are the
adaptation of A0 to meshconnected 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 modifiedthreadPool
 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 treepool
 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 (OUTversion) 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 OUTcriterion 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 INversion, 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 INtype can be found
efficiently by using an additional priority queue for i(.).
Finally, the INOUTapplies both criteria in conjunction.
Sample performance results here.
 Type Parameters:
E
 type of element on node Parameters:
graph
 Graphexec
 Thread pool for executing task in parallel.source
 source nodeend
 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 (OUTversion) 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 OUTcriterion 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 INversion, 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 INtype can be found
efficiently by using an additional priority queue for i(.).
Finally, the INOUTapplies both criteria in conjunction.
Sample performance results here.
 Type Parameters:
E
 type of element on node Parameters:
graph
 Graphexec
 Thread pool for executing task in parallel.source
 source nodeend
 end node
 Returns:
 the length of shortest path from source node to end node
Copyright © 2008. All Rights Reserved.