Package com.puresoltechnologies.graphs.graph

Class DeadEndAnalyzer

java.lang.Object

com.puresoltechnologies.graphs.graph.DeadEndAnalyzer

public class DeadEndAnalyzer
extends Object

This class contains method to check and evaluate Graphs.

Author:

Rick-Rainer Ludwig

Method Summary

Modifier and Type	Method	Description
static <V extends Vertex<V,E>,E extends Edge<V,E>> boolean	hasDeadEnds(Graph<V,E> stateModel, V startVertex, Set<V> endVertices)	This method checks whether a graph has dead ends or not assuming the provided graph is directed and the Pairs in the Edges are interpreted with first and second Vertex as start and target state.

Methods inherited from class java.lang.Object

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

Method Detail

hasDeadEnds

public static <V extends Vertex<V,E>,E extends Edge<V,E>> boolean hasDeadEnds(Graph<V,E> stateModel,
                                                                              V startVertex,
                                                                              Set<V> endVertices)
                                                                       throws IllegalArgumentException

This method checks whether a graph has dead ends or not assuming the provided graph is directed and the Pairs in the Edges are interpreted with first and second Vertex as start and target state. The dead ends are checked against a set of end states which are provided. For graph with these end states it is checked that from all vertices of the Graph an end state can be reached. If there is at least one state from which it is not possible, the graph has a dead end. Beware: The check is done recursively (but in linear time). So, for large models the stack needs to be large enough.

Type Parameters:

V - is the Vertex implementation to be used.

E - is the Edge implementation to be used.

Parameters:

stateModel - is the model to be checked. If the model has no end states, a IllegalArgumentException is thrown.

startVertex - is the Vertex to start the dead end search.

endVertices - is a Set of Vertex which define which vertices are to be treated as final states.

Returns:

true is returned of dead ends exist. false is returned otherwise.

Throws:

IllegalArgumentException - is thrown in case the model has no end states and cannot be checked for end states (because there are only dead ends).