Wolfram Function Repository
Instant-use add-on functions for the Wolfram Language
Function Repository Resource:
Provide an indexed priority queue data structure with its standard operations
returns an indexed priority queue initialized with default settings.
returns an indexed queue initialized to have length size, null element null and comparison function comp.
returns an indexed queue initialized with parameters in inits and containing values vals.
returns a list containing the index and value of the topmost element in queue.
places value in queue, associating to it an index equal to the current queue length plus one.
removes the element indexed by index from queue.
replaces the current value of element index with value, reordering queue as needed.
gives the number of elements in queue.
gives the value of the topmost element in queue.
gives the index of the topmost element in queue.
gives the value associated to the element indexed by keyindex, or the null value if it is not present.
Initialize a priority queue (aka ordered heap) with 20 random reals between -1 and 1:
Check the size:
Check the value of the largest element:
Add 80 more random values to the heap:
Recheck length and largest value:
When we dequeue elements one-by-one, the result is a sorted list of values; this method is called the "heap-sort" algorithm:
Check that it is indeed empty:
An alternative check is that the length is zero:
Check that the result is correctly sorted largest-to-smallest:
IndexedQueue can work with any data type for which an ordering exists, such as words with alphabetical order:
Now sort them in dictionary order by dequeuing, returning both original positions and values:
For a queue of size n, we expect speed proportional to n log n for creating and removing all elements. We test this by timing a basic sorting, then doubling size twice.
Use a queue to enqueue 10000 random values:
Now dequeue all elements:
Double the size and check enqueing and dequeing timings:
Again double the size and check enqueing and dequeing timings:
Attempting to dequeue from an empty queue gives the default element:
IndexedQueue has the same asymptotic complexity as the resource function PriorityQueue, but it has a larger constant factor due to the extra work in handling enqueuing and dequeuing.
Define a timing test for purposes of comparing IndexedQueue with PriorityQueue:
Create a set of 10000 random real values:
Time enqueuing and dequeuing using IndexedQueue:
Compare to enqueuing and dequeuing using PriorityQueue:
A minimum spanning tree for a connected graph is a tree that connects every vertex, has no cycles and is of minimal total edge weight. The "eager" version of Prim's method for computing the minimum spanning tree of a connected, weighted undirected graph works as follows. Start with any vertex. For any edge from that vertex, enqueue the vertex it connects to with value set to the edge weight. Iteratively remove from the queue the vertex of lowest edge weight and add it to the spanning tree under construction. Then iterate over the vertices connected to that vertex. Ignore those that already are in the tree. Enqueue with edge weight those that are not already in the queue. For a vertex currently in the queue, update the value if the edge weight is less than that which was previously associated to that vertex. For a graph of V vertices and E edges the complexity is O(E log V).
Code for the eager form of Prim's algorithm, specialized to a complete graph with edge weights as pairwise distances between planar points:
Create an example set of points:
Find the minimal spanning tree and total edge weight:
Check the total edge weight:
Plot the spanning tree:
Double the vertex count and repeat:
Using the built-in Prim method is an order of magnitude faster:
A vertex cover for a graph is a subset of vertices that hit all edges. Stated differently, every edge must have at least one endpoint in the cover. A cover with the minimal number of vertices is called a minimal cover. An approximate minimal cover can be found efficiently using a greedy algorithm as follows. First choose a vertex that hits the most edges, and remove those edges from consideration. This means we decrement the edge counts of all vertices connected to the one that was selected. Iteratively remove a vertex hitting the greatest number of remaining edges, and decrement edge counts of vertices connected to the one selected. Continue until no edges remain unhit. This can be implemented efficiently using an indexed priority queue.
Implement a greedy-with-updates approximate vertex cover using an indexed queue:
Create a random graph with 30 vertices and 80 edges:
Find an approximate vertex cover for this graph:
Check that it is a cover:
Compare the length to the actual minimal cover length:
Time this for a much larger random graph:
Check that it is a cover and find the length:
A method used in the resource function ApproximateVertexCover is substantially similar to the one above:
This work is licensed under a Creative Commons Attribution 4.0 International License