Package org.graph4j.spanning

Class WeightedSpanningTreeIterator

java.lang.Object

org.graph4j.spanning.WeightedSpanningTreeIterator

All Implemented Interfaces:

Iterator<Collection<Edge>>

Direct Known Subclasses:

MinimumSpanningTreeIterator

public class WeightedSpanningTreeIterator
extends Object
implements Iterator<Collection<Edge>>

Iterates over all spanning trees of a graph, in ascending or descending order by their weight. The iterator returns the collection of edges of a spanning tree, which can be used to create the actual tree with the method Graph.subgraph(java.util.Collection). See: G.K. Janssens, K. Sörensen, An algorithm to generate all spanning trees in order of increasing cost, Pesquisa Operacional, 2005-08, Vol. 25 (2), p. 219-229, https://www.scielo.br/j/pope/a/XHswBwRwJyrfL88dmMwYNWp/?lang=en

Author:

Cristian Frăsinaru

See Also:

• SpanningTreeIterator

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	WeightedSpanningTreeIterator.Part

Field Summary

Fields

Modifier and Type	Field	Description
protected final Edge[]	edges
protected final Graph	graph
protected final int	numVertices
protected final PriorityQueue<WeightedSpanningTreeIterator.Part>	queue

Constructor Summary

Constructors

Constructor	Description
WeightedSpanningTreeIterator(Graph graph)	Creates an iterator over the spanning trees of the specified graph, in ascending order of their weight.
WeightedSpanningTreeIterator(Graph graph, boolean ascending)	Creates an iterator over the spanning trees of the specified graph, in ascending or descending order by their weight.

Method Summary

Modifier and Type	Method	Description
boolean	hasNext()
Collection<Edge>	next()
protected void	refine(WeightedSpanningTreeIterator.Part part)

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, remove

Field Details

graph

protected final Graph graph

numVertices

protected final int numVertices

edges

protected final Edge[] edges

queue

protected final PriorityQueue<WeightedSpanningTreeIterator.Part> queue

Constructor Details

WeightedSpanningTreeIterator

public WeightedSpanningTreeIterator(Graph graph)

Creates an iterator over the spanning trees of the specified graph, in ascending order of their weight.

Parameters:

graph - the input graph.

WeightedSpanningTreeIterator

public WeightedSpanningTreeIterator(Graph graph,
 boolean ascending)

Creates an iterator over the spanning trees of the specified graph, in ascending or descending order by their weight.

Parameters:

graph - the input graph.

ascending - true if the spanning trees are returned in ascending order by their weight, false if the order should be descending.

Method Details

hasNext

public boolean hasNext()

Specified by:

hasNext in interface Iterator<Collection<Edge>>

next

public Collection<Edge> next()

Specified by:

next in interface Iterator<Collection<Edge>>

refine

protected void refine(WeightedSpanningTreeIterator.Part part)