Index (optimal-mst 1.0 API)

A B C D E F G H I K L M N O P R S T U V W

A

AdjacencyList<E extends DirectedEdge<?,E>> - Class in util.graph: Represents the AdjacencyList of a Graph.
AdjacencyList(int) - Constructor for class util.graph.AdjacencyList: Creates a new AdjacenyList for a graph with count vertices
append(int, E) - Method in class util.graph.AdjacencyList: Appends an edge to the adjacency of a given vertex.
append(E) - Method in class util.graph.EdgeList: Takes an edge and appends it to this EdgeList.
ascendingIntPairs(int, BiFunction<Integer, Integer, T>) - Static method in class util.decision.Iterators

B

BinaryHeap<T> - Class in util.queue
BinaryHeap(Comparator<? super T>) - Constructor for class util.queue.BinaryHeap
BinaryHeap() - Constructor for class util.queue.SoftHeap.BinaryHeap
BinaryHeapNode(SoftHeap<T>.BinaryHeapNode, SoftHeap<T>.BinaryHeapNode, T, int) - Constructor for class util.queue.SoftHeap.BinaryHeapNode
BinaryHeapNode() - Constructor for class util.queue.SoftHeap.BinaryHeapNode
BoruvkaMST - Class in mst
BoruvkaMST() - Constructor for class mst.BoruvkaMST

C

clear() - Method in class util.graph.EdgeList: Clears the EdgeList
clear() - Method in class util.queue.SoftHeap: Resets the binary heap
collect(Supplier<C>) - Method in class util.graph.EdgeList: Returns a new Collection of the elements of this EdgeList using the provided factory.
combinations(int, List<E>) - Static method in class util.decision.Iterators
combine(SoftHeap<T>.BinaryHeap) - Method in class util.queue.SoftHeap.BinaryHeap
compareTo(IndexedEdge<T, E>) - Method in class util.graph.edge.IndexedEdge
compareTo(WeightedEdge<T>) - Method in class util.graph.edge.WeightedEdge
componentMapping(int, Iterable<E>) - Static method in class util.graph.Graphs: Returns an array representing a connected component mapping.
componentMapping(int, List<List<Integer>>) - Static method in class util.graph.Graphs: Creates an array representing a connected component mapping.
components(int, Iterable<E>) - Static method in class util.graph.Graphs: Takes a graph specified by a number of vertices and an Iterable of edges and returns a List of List of Integer, where the i-th List contains the indices of all vertices that belong to the i-th connected component.
compute(int, Iterable<E>) - Static method in class mst.BoruvkaMST
compute(int, Iterable<E>) - Static method in class mst.FredmanTarjanMST
compute(int, Iterable<E>) - Static method in class mst.KruskalMST
compute(int, Iterable<E>) - Static method in class mst.PettieRamachandranMST
compute(int, Iterable<E>) - Static method in class mst.PrimMST
computeUpTo(int) - Static method in class util.decision.PrecomputedMSTCollection: Computes all optimal mst decision trees for graphs with up to maxVertices vertices
contract(int, Iterable<D>, Iterable<E>) - Static method in class util.graph.Graphs: Contracts a graph specified by the number of vertices and an Iterable of edges along the edges given by the Iterable span.
ContractedEdge<T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> - Class in util.graph.edge: An implementation of AbstractRenamedEdge, which represents contracted edges.
ContractedEdge(E) - Constructor for class util.graph.edge.ContractedEdge: Creates a new contracted edge that keeps the start and end indices from the original edge.
ContractedEdge(int, int, E) - Constructor for class util.graph.edge.ContractedEdge: Creates a new contracted edge that connects the vertices from and to and internally references the original edge.
corrupted() - Method in interface util.queue.PriorityQueue
corrupted() - Method in class util.queue.SoftHeap
corrupted() - Method in interface util.queue.SoftPriorityQueue: Returns a Collection of corrupted elements -- that is, elements which are associated with the wrong key.

D

decrease(long) - Method in interface util.queue.ExtendedPriorityQueue
decrease(long) - Method in class util.queue.FibonacciHeap
decrease(long) - Method in class util.queue.KAryHeap
DirectedEdge<T,R extends DirectedEdge<T,R>> - Interface in util.graph.edge: Represents an Edge with generic weight type.
DisjointSet - Interface in util.disjointset: Represents a disjoint set data structure.
distinct() - Method in interface util.disjointset.DisjointSet: Returns the number of distinct sets.
distinct() - Method in class util.disjointset.OptimalUnionFind

E

edge - Variable in class util.graph.edge.IndexedEdge
EdgeList<E extends DirectedEdge<?,E>> - Class in util.graph: A linked list of edges for a graph that supports concatenation in O(1).
EdgeList() - Constructor for class util.graph.EdgeList: Creates an empty EdgeList
EdgeList(Iterable<? extends E>) - Constructor for class util.graph.EdgeList: Takes another EdgeList an appends it to this one
edges - Variable in class util.graph.Graph: The EdgeList of edges in the graph
empty() - Method in interface util.queue.SoftPriorityQueue: Returns whether the queue is empty.
equals(Object) - Method in class util.graph.edge.IndexedEdge
equals(Object) - Method in class util.graph.edge.WeightedEdge
equals(Object) - Method in class util.graph.EdgeList: Checks if another object is equal to this EdgeList.
ExtendedPriorityQueue<T> - Interface in util.queue

F

FibonacciHeap<T> - Class in util.queue
FibonacciHeap(Comparator<? super T>) - Constructor for class util.queue.FibonacciHeap
find(int) - Method in interface util.disjointset.DisjointSet: Returns a representative member of the set that i is part of.
find(int) - Method in class util.disjointset.OptimalUnionFind
findMST(int, List<E>) - Method in class util.decision.PrecomputedMSTCollection
findMST(int, Iterable<E>) - Method in interface util.graph.MinimumSpanningTreeAlgorithm
flatten(EdgeList<ContractedEdge<T, ContractedEdge<T, E>>>) - Static method in class util.graph.Graphs: Takes an EdgeList of at least doubly contracted edges and removes the second-outermost layer of contracted edges
flatten(Graph<ContractedEdge<T, ContractedEdge<T, E>>>) - Static method in class util.graph.Graphs: Takes a Graph of at least doubly contracted edges and removes the second-outermost layer of contracted edges
FredmanTarjanMST - Class in mst
FredmanTarjanMST() - Constructor for class mst.FredmanTarjanMST
from() - Method in interface util.graph.edge.DirectedEdge: Returns where the edge starts.
from() - Method in class util.graph.edge.IndexedEdge
from() - Method in class util.graph.edge.WeightedEdge

G

get(int) - Method in class util.graph.AdjacencyList: Returns an EdgeList of edges for a given vertex.
getMaxVertices() - Method in class util.decision.PrecomputedMSTCollection: Returns the max number of vertices of a graph up to which the optimal mst decision trees have been computed.
Graph<E extends DirectedEdge<?,E>> - Class in util.graph: Represents a Graph as a number of vertices and an EdgeList
Graph(int, EdgeList<E>) - Constructor for class util.graph.Graph: Creates a new Graph with the given number of vertices and the EdgeList
Graphs - Class in util.graph: Provides a lot of utility methods for working with graphs

H

hashCode() - Method in class util.graph.edge.IndexedEdge
hashCode() - Method in class util.graph.edge.WeightedEdge

I

index - Variable in class util.graph.edge.IndexedEdge
IndexedEdge<T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> - Class in util.graph.edge: A special type of edge that is associated with an index.
IndexedEdge(int, E) - Constructor for class util.graph.edge.IndexedEdge: Creates a new indexed edge with the given index, referencing the given edge
indexPermutations(int) - Static method in class util.decision.Iterators
insert(T) - Method in class util.queue.FibonacciHeap
insert(T) - Method in class util.queue.KAryHeap
insert(T) - Method in class util.queue.SoftHeap.BinaryHeapNode: Inserts the given element into the selected node.
insert(T) - Method in class util.queue.SoftHeap
insert(T) - Method in interface util.queue.SoftPriorityQueue: Inserts an element into the queue.
insertWithId(T) - Method in interface util.queue.ExtendedPriorityQueue
insertWithId(T) - Method in class util.queue.FibonacciHeap
insertWithId(T) - Method in class util.queue.KAryHeap
isLeaf() - Method in class util.queue.SoftHeap.BinaryHeapNode: Returns whether a node is a leaf, which is the case if both of its children don't exist.
iterator() - Method in class util.graph.EdgeList: Returns an Iterator over the elements in this EdgeList.
Iterators - Class in util.decision

K

KAryHeap<T> - Class in util.queue
KAryHeap(int, Comparator<? super T>) - Constructor for class util.queue.KAryHeap
KruskalMST - Class in mst
KruskalMST() - Constructor for class mst.KruskalMST

L

Launcher - Class in main
Launcher() - Constructor for class main.Launcher
lightestEdgePerVertex(int, Iterable<E>) - Static method in class util.graph.Graphs: Takes a graph specified by the number of vertices and an Iterable of edges.
log(Object) - Static method in class util.log.Logger
logf(String, Object...) - Static method in class util.log.Logger
Logger - Class in util.log

M

main - package main
main(String[]) - Static method in class main.Launcher
main(String[]) - Static method in class main.PrecomputeLauncher
map(Function<E, T>) - Method in class util.graph.EdgeList: Transforms the elements of this EdgeList using the provided function.
mapCollect(Function<E, T>, Supplier<C>) - Method in class util.graph.EdgeList: Returns a new Collection of the elements of this EdgeList using the provided factory after transforming each element using the provided function.
meld(EdgeList<E>) - Method in class util.graph.EdgeList
meld(T) - Method in interface util.queue.Meldable: Destructively melds other into this.
meld(SoftHeap<T>) - Method in class util.queue.SoftHeap
Meldable<T> - Interface in util.queue
MinimumSpanningTreeAlgorithm<E extends DirectedEdge<?,E>> - Interface in util.graph
mst - package mst

N

naturallyOrdered() - Static method in class util.queue.BinaryHeap
naturallyOrdered() - Static method in class util.queue.FibonacciHeap
naturallyOrdered(int) - Static method in class util.queue.KAryHeap
naturallyOrdered(double) - Static method in class util.queue.SoftHeap: Creates a new soft heap on the basis of the comparable type argument and the given error rate.

O

of(Graph<E>) - Static method in class util.graph.AdjacencyList: Takes a Graph graph and transforms it into an AdjacencyList
of(int, Iterable<? extends E>) - Static method in class util.graph.AdjacencyList: Takes a graph given by the number of vertices and an Iterable of edges and transforms it into an AdjacencyList
OptimalUnionFind - Class in util.disjointset: Provides an implementation of the DisjointSet interface.
OptimalUnionFind(int) - Constructor for class util.disjointset.OptimalUnionFind: Creates a new OptimalUnionFind data structure of the specified size

P

peek() - Method in class util.queue.FibonacciHeap
peek() - Method in class util.queue.KAryHeap
peek() - Method in class util.queue.SoftHeap
peek() - Method in interface util.queue.SoftPriorityQueue: Peeks into the top of the queue, returning the element which is believed to have minimal key.
permutations(List<T>) - Static method in class util.decision.Iterators
PettieRamachandranMST - Class in mst
PettieRamachandranMST() - Constructor for class mst.PettieRamachandranMST
PettieRamachandranMST.PartitionWrapper<T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> - Class in mst
pop() - Method in class util.queue.FibonacciHeap
pop() - Method in class util.queue.KAryHeap
pop() - Method in class util.queue.SoftHeap
pop() - Method in interface util.queue.SoftPriorityQueue: Peeks into the top of the queue, returning the element which is believed to have minimal key.
powerSet(List<E>) - Static method in class util.decision.Iterators
PrecomputedMSTCollection - Class in util.decision: Represents a decision tree that can compute the MST of graphs up to a given size using an optimal number of comparisons.
PrecomputeLauncher - Class in main
PrecomputeLauncher() - Constructor for class main.PrecomputeLauncher
prepend(E) - Method in class util.graph.EdgeList: Takes an edge and prepends it to this EdgeList.
PrimMST - Class in mst
PrimMST() - Constructor for class mst.PrimMST
PriorityQueue<T> - Interface in util.queue: In contrast to soft priority queues, "standard" priority queues have to be exact.

R

removeDuplicates(int, Iterable<E>) - Static method in class util.graph.Graphs: Removes multiple edges between two vertices.
RenamedEdge<T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> - Class in util.graph.edge: An implementation of AbstractRenamedEdge
RenamedEdge(int, int, E) - Constructor for class util.graph.edge.RenamedEdge: Creates a new abstract renamed edge with new from, to, internally referencing the original edge.
renameVertices(Iterable<E>) - Static method in class util.graph.Graphs: Takes an Iterable of edges and renames the vertices, so that all vertex indices are between 0 and n - 1 where n is the number of vertices
reversed() - Method in class util.graph.edge.ContractedEdge
reversed() - Method in interface util.graph.edge.DirectedEdge: Returns a new edge with DirectedEdge.from() and DirectedEdge.to() swapped.
reversed() - Method in class util.graph.edge.IndexedEdge
reversed() - Method in class util.graph.edge.RenamedEdge
reversed() - Method in class util.graph.edge.WeightedEdge
reweighted(T) - Method in class util.graph.edge.WeightedEdge: Creates a new edge linking the same two vertices with the given weight.

S

setActive(boolean) - Static method in class util.log.Logger
sift() - Method in class util.queue.SoftHeap.BinaryHeapNode: Replenishes the elements associated with the given key if the amount of elements in the list has dropped below size / 2.
size() - Method in interface util.disjointset.DisjointSet: Returns the number of elements.
size() - Method in class util.disjointset.OptimalUnionFind
size() - Method in class util.graph.EdgeList: Returns the number of edges in this EdgeList.
size() - Method in class util.queue.FibonacciHeap
size() - Method in class util.queue.KAryHeap
size() - Method in class util.queue.SoftHeap
size() - Method in interface util.queue.SoftPriorityQueue: Returns the size of the queue.
SoftHeap<T> - Class in util.queue: The soft heap, first described by Chazelle, is an approximate data structure similar to a priority queue.
SoftHeap(double, Comparator<? super T>, T) - Constructor for class util.queue.SoftHeap: Constructs a new soft heap with the given error rate containing the specified element.
SoftHeap(double, Comparator<? super T>) - Constructor for class util.queue.SoftHeap: Constructs an empty soft heap with the given error rate.
SoftHeap.BinaryHeap - Class in util.queue: Represents a binary heap in the queue of binary heaps that the soft heap consists of
SoftHeap.BinaryHeapNode - Class in util.queue
SoftPriorityQueue<T> - Interface in util.queue: A soft priority queue is a type of priority queue which is allowed to make mistakes.
sortEdges(int, Iterable<E>) - Static method in class util.graph.Graphs: Takes a graph specified by the number of vertices and an Iterable of edges and returns an EdgeList containing all edges in a sorted manner.
stream() - Method in class util.graph.EdgeList: Returns a Stream of the edges of this EdgeList.

T

to() - Method in interface util.graph.edge.DirectedEdge: Returns where the edge ends.
to() - Method in class util.graph.edge.IndexedEdge
to() - Method in class util.graph.edge.WeightedEdge
toArray(IntFunction<E[]>) - Method in class util.graph.EdgeList: Creates an array of the edges of this EdgeList using the provided generator
toString() - Method in class util.graph.AdjacencyList
toString() - Method in class util.graph.edge.ContractedEdge
toString() - Method in class util.graph.edge.IndexedEdge
toString() - Method in class util.graph.edge.RenamedEdge
toString() - Method in class util.graph.edge.WeightedEdge
toString() - Method in class util.graph.EdgeList: Returns a string representation of this EdgeList.
toString() - Method in class util.graph.Graph
toString() - Method in class util.queue.FibonacciHeap
toString() - Method in class util.queue.SoftHeap.BinaryHeap
toString() - Method in class util.queue.SoftHeap

U

union(int, int) - Method in interface util.disjointset.DisjointSet: Unions the two sets specified by i and j.
union(int, int) - Method in class util.disjointset.OptimalUnionFind
updateSuffixMin() - Method in class util.queue.SoftHeap.BinaryHeap: Updates sufMin, which points to the tree following this tree with the smallest root node.
util.decision - package util.decision
util.disjointset - package util.disjointset
util.graph - package util.graph
util.graph.edge - package util.graph.edge
util.log - package util.log
util.queue - package util.queue

V

vertices - Variable in class util.graph.Graph: The number of vertices in the graph

W

weight() - Method in interface util.graph.edge.DirectedEdge: Returns the weight of the edge.
weight() - Method in class util.graph.edge.IndexedEdge
weight() - Method in class util.graph.edge.WeightedEdge
WeightedEdge<T extends java.lang.Comparable<? super T>> - Class in util.graph.edge: Represents a weighted edge.
WeightedEdge(int, int, T) - Constructor for class util.graph.edge.WeightedEdge: Create a new weighted edge from from to to with the given weight

A B C D E F G H I K L M N O P R S T U V W