Module org.jgrapht.core

Package org.jgrapht.graph

Class DirectedAcyclicGraph.VisitedArrayListImpl

java.lang.Object

org.jgrapht.graph.DirectedAcyclicGraph.VisitedArrayListImpl

All Implemented Interfaces:

Serializable, DirectedAcyclicGraph.VisitedStrategy, DirectedAcyclicGraph.VisitedStrategyFactory

Enclosing class:

DirectedAcyclicGraph<V,E>

protected static class DirectedAcyclicGraph.VisitedArrayListImpl
extends Object
implements DirectedAcyclicGraph.VisitedStrategy, DirectedAcyclicGraph.VisitedStrategyFactory

A visited strategy using an ArrayList.

This implementation seems to offer the best performance in most cases. It grows the internal ArrayList as needed to be as large as |AR|, so it will be more memory intensive than the HashSet implementation, and unlike the Array implementation, it will hold on to that memory (it expands, but never contracts).

See Also:

• Serialized Form

Field Summary

Fields

Modifier and Type	Field	Description
private DirectedAcyclicGraph.Region	affectedRegion
private static final long	serialVersionUID
private final List<Boolean>	visited

Constructor Summary

Constructors

Constructor	Description
VisitedArrayListImpl()	Constructor

Method Summary

Modifier and Type	Method	Description
void	clearVisited(int index)	Clear the visited state of the given topological index.
boolean	getVisited(int index)	Get if the given topological index has been visited.
DirectedAcyclicGraph.VisitedStrategy	getVisitedStrategy(DirectedAcyclicGraph.Region affectedRegion)	Create a new instance of DirectedAcyclicGraph.VisitedStrategy.
void	setVisited(int index)	Mark the given topological index as visited.
private int	translateIndex(int index)	We translate the topological index to an ArrayList index.

Methods inherited from class java.lang.Object

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

Field Details

serialVersionUID

private static final long serialVersionUID

See Also:

• Constant Field Values

visited

private final List<Boolean> visited

affectedRegion

private DirectedAcyclicGraph.Region affectedRegion

Constructor Details

VisitedArrayListImpl

public VisitedArrayListImpl()

Constructor

Method Details

getVisitedStrategy

public DirectedAcyclicGraph.VisitedStrategy getVisitedStrategy(DirectedAcyclicGraph.Region affectedRegion)

Description copied from interface: DirectedAcyclicGraph.VisitedStrategyFactory

Create a new instance of DirectedAcyclicGraph.VisitedStrategy.

Specified by:

getVisitedStrategy in interface DirectedAcyclicGraph.VisitedStrategyFactory

Parameters:

affectedRegion - the affected region

Returns:

a new instance of DirectedAcyclicGraph.VisitedStrategy for the affected region

setVisited

public void setVisited(int index)

Description copied from interface: DirectedAcyclicGraph.VisitedStrategy

Mark the given topological index as visited.

Specified by:

setVisited in interface DirectedAcyclicGraph.VisitedStrategy

Parameters:

index - the topological index

getVisited

public boolean getVisited(int index)

Description copied from interface: DirectedAcyclicGraph.VisitedStrategy

Get if the given topological index has been visited.

Specified by:

getVisited in interface DirectedAcyclicGraph.VisitedStrategy

Parameters:

index - the topological index

Returns:

true if the given topological index has been visited, false otherwise

clearVisited

public void clearVisited(int index)
                  throws UnsupportedOperationException

Description copied from interface: DirectedAcyclicGraph.VisitedStrategy

Clear the visited state of the given topological index.

Specified by:

clearVisited in interface DirectedAcyclicGraph.VisitedStrategy

Parameters:

index - the index

Throws:

UnsupportedOperationException - if the implementation doesn't support (or doesn't need) clearance. For example, if the factory creates a new instance every time, it is a waste of cycles to reset the state after the search of the Affected Region is done, so an UnsupportedOperationException *should* be thrown.

translateIndex

private int translateIndex(int index)

We translate the topological index to an ArrayList index. We have to do this because topological indices can be negative, and we want to do it because we can make better use of space by only needing an ArrayList of size |AR|.

Returns:

the ArrayList index