pu.pi

Class DFSonDAGBottomTop<V>

java.lang.Object

pu.pi.ParIteratorAbstract<V>

pu.pi.DFSonDAGBottomTop<V>

All Implemented Interfaces:

java.util.Iterator<V>, ParIterator<V>

public class DFSonDAGBottomTop<V>
extends ParIteratorAbstract<V>

Date created: 16 July 2009 Last modified: 17 July 2009 This class represents a Parallel DFS Iterator which works on Directed Acyclic Graphs (DAGs). It returns nodes in DFS order from bottom to top (i.e. in case of a tree, leaves are returned before top level nodes).

Author:

Lama Akeila

Nested Class Summary

Nested classes/interfaces inherited from interface pu.pi.ParIterator

ParIterator.Schedule

Field Summary

Fields inherited from class pu.pi.ParIteratorAbstract

chunkSize, collection, data, exceptions, flags, ignoreBarrier, numOfThreads, reclaimedElements, threadID

Fields inherited from interface pu.pi.ParIterator

DEFAULT_CHUNKSIZE

Constructor Summary

Constructors

Constructor and Description
DFSonDAGBottomTop(GraphAdapterInterface tree, V root2, int numOfThreads)

Method Summary

Modifier and Type	Method and Description
void	forEachRemaining(java.util.function.Consumer<? super V> action)
void	globalBreak() Causes all threads to stop processing elements at the next iteration boundary.
boolean	hasNext() This method returns TRUE if there is still available vertex in the iterator (i.e.
boolean	localBreak() Attempts to excuse the current thread from continuing to iterate (and re-distribute all unprocessed elements to the other threads).
V	next() Returns an element for the current thread to process.

Methods inherited from class pu.pi.ParIteratorAbstract

allOtherThreadsHaveLocalBreaked, getAllExceptions, getID, register, register, remove, reset

Methods inherited from class java.lang.Object

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

Constructor Detail

DFSonDAGBottomTop

public DFSonDAGBottomTop(GraphAdapterInterface tree,
                         V root2,
                         int numOfThreads)

Method Detail

hasNext

public boolean hasNext()

This method returns TRUE if there is still available vertex in the iterator (i.e. unvisited vertex), else returns FALSE

Returns:

true if at least one element has been reserved for the calling thread (in which case it must follow up with a call to next()).
false otherwise (in such a case, the calling thread blocks until all the other threads have completed their iterations).

See Also:

ParIterator.next()

next

public V next()

Description copied from interface: ParIterator

Returns an element for the current thread to process. A thread must not call this method unless it has previously called hasNext() (and received true).

Note that calls to hasNext() (that return true) only allow for one corresponding and binding call to hasNext(). Therefore, multiple calls to hasNext() have no effect until the corresponding call to next() takes place.

See Also:

ParIterator.hasNext()

globalBreak

public void globalBreak()

Description copied from interface: ParIterator

Causes all threads to stop processing elements at the next iteration boundary. Therefore, even if there were any unprocessed elements, they will not be processed. In such a case, false is returned to every thread at the next call to hasNext(). Therefore, all the threads safely stop iterating when they call hasNext() (includes an implicit barrier to ensure all threads stop at the same time).

Specified by:

globalBreak in interface ParIterator<V>

Overrides:

globalBreak in class ParIteratorAbstract<V>

See Also:

ParIterator.localBreak()

localBreak

public boolean localBreak()

Description copied from interface: ParIterator

Attempts to excuse the current thread from continuing to iterate (and re-distribute all unprocessed elements to the other threads). This is only successful if the the elements previously assigned to this thread are successfully allocated to the other thread(s). If the elements cannot be assigned to another thread (because the other threads have already stopped processing), then this attempt to local break will fail.

Therefore, (as opposed to globalBreak()) this method guarantees that even if all threads attempt to localBreak(), at least one will fail and is left to traverse the remaining elements. Note that in many cases, calling localBreak() will break the original scheduling policy.

Returns:

true if the attempt is successful, false otherwise.

See Also:

ParIterator.globalBreak()

forEachRemaining

public void forEachRemaining(java.util.function.Consumer<? super V> action)