org.jgrapht.traverse

Class MaximumCardinalityIterator<V,E>

java.lang.Object

org.jgrapht.traverse.AbstractGraphIterator<V,E>

org.jgrapht.traverse.MaximumCardinalityIterator<V,E>

Type Parameters:

V - the graph vertex type.

E - the graph edge type.

All Implemented Interfaces:

Iterator<V>, GraphIterator<V,E>

public class MaximumCardinalityIterator<V,E>
extends AbstractGraphIterator<V,E>

A maximum cardinality search iterator for an undirected graph.

For every vertex in graph its cardinality is defined as the number of its neighbours, which have been already visited by this iterator. Iterator chooses vertex with the maximum cardinality, breaking ties arbitrarily. For more information of maximum cardinality search see: Berry, A., Blair, J., Heggernes, P. et al. Algorithmica (2004) 39: 287. https://doi.org/10.1007/s00453-004-1084-3 Maximum Cardinality Search for Computing Minimal Triangulations.

For this iterator to work correctly the graph must not be modified during iteration. Currently there are no means to ensure that, nor to fail-fast. The results of such modifications are undefined.

Note: only vertex events are fired by this iterator.

Author:

Timofey Chudakov

Field Summary

Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator

crossComponentTraversal, graph, nListeners, reusableEdgeEvent, reusableVertexEvent, reuseEvents

Constructor Summary

Constructors

Constructor and Description
MaximumCardinalityIterator(Graph<V,E> graph) Creates a maximum cardinality iterator for the graph.

Method Summary

Modifier and Type	Method and Description
boolean	hasNext() Checks whether there exists unvisited vertex.
boolean	isCrossComponentTraversal() Test whether this iterator is set to traverse the graph across connected components.
V	next() Returns the next vertex in the ordering.
void	setCrossComponentTraversal(boolean crossComponentTraversal) Sets the cross component traversal flag - indicates whether to traverse the graph across connected components.

Methods inherited from class org.jgrapht.traverse.AbstractGraphIterator

addTraversalListener, createEdgeTraversalEvent, createVertexTraversalEvent, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, getGraph, isReuseEvents, remove, removeTraversalListener, setReuseEvents

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Iterator

forEachRemaining

Constructor Detail

MaximumCardinalityIterator

public MaximumCardinalityIterator(Graph<V,E> graph)

Creates a maximum cardinality iterator for the graph.

Parameters:

graph - the graph to be iterated.

Method Detail

hasNext

public boolean hasNext()

Checks whether there exists unvisited vertex.

Returns:

true if there exists unvisited vertex.

next

public V next()

Returns the next vertex in the ordering.

Returns:

the next vertex in the ordering.

isCrossComponentTraversal

public boolean isCrossComponentTraversal()

Test whether this iterator is set to traverse the graph across connected components.

Always returns true since this iterator doesn't care about connected components.

Specified by:

isCrossComponentTraversal in interface GraphIterator<V,E>

Overrides:

isCrossComponentTraversal in class AbstractGraphIterator<V,E>

Returns:

true if traverses across connected components, otherwise false.

setCrossComponentTraversal

public void setCrossComponentTraversal(boolean crossComponentTraversal)

Sets the cross component traversal flag - indicates whether to traverse the graph across connected components.

Trying to disable the cross components nature of this iterator will result into throwing a IllegalArgumentException.

Overrides:

setCrossComponentTraversal in class AbstractGraphIterator<V,E>

Parameters:

crossComponentTraversal - if true traverses across connected components.