slib.graph.algo.traversal.classical

Class DFS

java.lang.Object

slib.graph.algo.traversal.classical.DFS

All Implemented Interfaces:

GraphTraversal

public class DFS
extends Object
implements GraphTraversal

Class used to perform traversal on a graph using Depth First Search Algorithm from a set of vertices and considering particular types of relationships. more about Note that contrary to BFS the traversal is performed at instance creation. The iteration is then made on the stored topological sort. The topological sort can also be retrieve.

Author:

Sébastien Harispe

Constructor Summary

Constructors

Constructor and Description
DFS(G g, Set<org.openrdf.model.URI> sources, WalkConstraint wc) Create a DFS iterator, note that DFS is performed at instance creation.
DFS(G g, org.openrdf.model.URI source, WalkConstraint wc)

Method Summary

Methods

Modifier and Type	Method and Description
List<org.openrdf.model.URI>	getTraversalOrder() Returns the traversal ordering resulting of the DFS i.e topological sort.
boolean	hasNext() Check if the traversal is finished.
org.openrdf.model.URI	next() Return the next vertex of the traversal.

Methods inherited from class java.lang.Object

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

Constructor Detail

DFS

public DFS(G g,
   Set<org.openrdf.model.URI> sources,
   WalkConstraint wc)

Create a DFS iterator, note that DFS is performed at instance creation. The resulting topological sort can be accessed through

DFS

public DFS(G g,
   org.openrdf.model.URI source,
   WalkConstraint wc)

Method Detail

hasNext

public boolean hasNext()

Description copied from interface: GraphTraversal

Check if the traversal is finished.

Specified by:

hasNext in interface GraphTraversal

Returns:

true if the traversal contains a vertex which has not been visited. Return false if the traversal is finished.

next

public org.openrdf.model.URI next()

Description copied from interface: GraphTraversal

Return the next vertex of the traversal.

Specified by:

next in interface GraphTraversal

Returns:

the next vertex of the traversal.

getTraversalOrder

public List<org.openrdf.model.URI> getTraversalOrder()

Returns the traversal ordering resulting of the DFS i.e topological sort. Note that the returned value corresponds to the data structure on which relies the iterator. Modification of the data structure will directly impact DFS behavior and coherence.

Returns:

the data structure on which the iterator relies i.e. precomputed topological ordering as a List of URI.