- Type Parameters:
V
- the graph vertex type.E
- the graph edge type.
- All Implemented Interfaces:
Iterator<V>
,GraphIterator<V,
E>
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.
-
Nested Class Summary
Nested classes/interfaces inherited from class org.jgrapht.traverse.AbstractGraphIterator
AbstractGraphIterator.FlyweightEdgeEvent<E>, AbstractGraphIterator.FlyweightVertexEvent<V>
-
Field Summary
FieldsModifier and TypeFieldDescriptionDisjoint sets of vertices of the graph, indexed by the cardinalities of already visited neighbours.Maps every vertex to its cardinality.private V
Contains current vertex.private int
The maximum index of non-empty set inbuckets
.private int
Number of unvisited vertices.Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator
crossComponentTraversal, graph, nListeners, reusableEdgeEvent, reusableVertexEvent, reuseEvents
-
Constructor Summary
ConstructorsConstructorDescriptionMaximumCardinalityIterator
(Graph<V, E> graph) Creates a maximum cardinality iterator for thegraph
. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
addToBucket
(V vertex, int cardinality) Adds thevertex
to the bucket with the givencardinality
.private V
advance()
Retrieves a vertex from thebuckets
with the maximum cardinality and returns it.boolean
hasNext()
Checks whether there exists unvisited vertex.boolean
Test whether this iterator is set to traverse the graph across connected components.next()
Returns the next vertex in the ordering.private int
removeFromBucket
(V vertex) Removesvertex
from the bucket it was contained in.void
setCrossComponentTraversal
(boolean crossComponentTraversal) Sets the cross component traversal flag - indicates whether to traverse the graph across connected components.private void
updateNeighbours
(V vertex) Increments the cardinalities of the neighbours of thevertex
by 1.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
-
Field Details
-
maxCardinality
private int maxCardinalityThe maximum index of non-empty set inbuckets
. -
remainingVertices
private int remainingVerticesNumber of unvisited vertices. -
current
Contains current vertex. -
buckets
Disjoint sets of vertices of the graph, indexed by the cardinalities of already visited neighbours. -
cardinalityMap
Maps every vertex to its cardinality.
-
-
Constructor Details
-
MaximumCardinalityIterator
Creates a maximum cardinality iterator for thegraph
.- Parameters:
graph
- the graph to be iterated.
-
-
Method Details
-
hasNext
public boolean hasNext()Checks whether there exists unvisited vertex.- Returns:
- true if there exists unvisited vertex.
-
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 interfaceGraphIterator<V,
E> - Overrides:
isCrossComponentTraversal
in classAbstractGraphIterator<V,
E> - Returns:
true
if traverses across connected components, otherwisefalse
.
-
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 classAbstractGraphIterator<V,
E> - Parameters:
crossComponentTraversal
- iftrue
traverses across connected components.
-
advance
Retrieves a vertex from thebuckets
with the maximum cardinality and returns it.- Returns:
- vertex retrieved from
buckets
.
-
removeFromBucket
Removesvertex
from the bucket it was contained in.- Parameters:
vertex
- the vertex, which has to be removed from the bucket it was contained in.- Returns:
- the cardinality of the removed vertex or -1, if the vertex wasn't contained in any bucket.
-
addToBucket
Adds thevertex
to the bucket with the givencardinality
.- Parameters:
vertex
- the vertex, which has to be added to the the bucket.cardinality
- the cardinality of the destination bucket.
-
updateNeighbours
Increments the cardinalities of the neighbours of thevertex
by 1. If the maximum cardinality increases, incrementsmaxCardinality
by 1.- Parameters:
vertex
- the vertex whose neighbours are to be updated.
-