- java.lang.Object
-
- org.jgrapht.traverse.AbstractGraphIterator<V,E>
-
- org.jgrapht.traverse.DegeneracyOrderingIterator<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
java.util.Iterator<V>
,GraphIterator<V,E>
public class DegeneracyOrderingIterator<V,E> extends AbstractGraphIterator<V,E>
A degeneracy ordering iterator.The degeneracy of a graph $G $is the smallest value d such that every nonempty subgraph of $G$ contains a vertex of degree at most $d.$ If a graph has degeneracy $d$, then it has a degeneracy ordering, an ordering such that each vertex has $d$ or fewer neighbors that come later in the ordering.
The iterator crosses components but does not track them, it only tracks visited vertices.
The iterator treats the input graph as undirected even if the graph is directed. Moreover, it completely ignores self-loops, meaning that it operates as if self-loops do not contribute to the degree of a vertex.
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class org.jgrapht.traverse.AbstractGraphIterator
AbstractGraphIterator.FlyweightEdgeEvent<E>, AbstractGraphIterator.FlyweightVertexEvent<V>
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.Set<V>[]
buckets
private V
cur
private java.util.Map<V,java.lang.Integer>
degrees
private int
minDegree
-
Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator
crossComponentTraversal, graph, nListeners, reusableEdgeEvent, reusableVertexEvent, reuseEvents
-
-
Constructor Summary
Constructors Constructor Description DegeneracyOrderingIterator(Graph<V,E> graph)
Constructor
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private V
advance()
boolean
hasNext()
boolean
isCrossComponentTraversal()
Test whether this iterator is set to traverse the graph across connected components.V
next()
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
-
-
-
-
Method Detail
-
isCrossComponentTraversal
public boolean isCrossComponentTraversal()
Test whether this iterator is set to traverse the graph across connected components. Always returns true since the iterator does not care about 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 aIllegalArgumentException
.- Overrides:
setCrossComponentTraversal
in classAbstractGraphIterator<V,E>
- Parameters:
crossComponentTraversal
- iftrue
traverses across connected components.
-
hasNext
public boolean hasNext()
-
next
public V next()
-
advance
private V advance()
-
-