/**************************************************************************
* File: Prim.java
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* An implementation of Prim's minimum spanning tree algorithm.  The algorithm
* takes as input a weighted, undirected graph and returns a new graph that
* is a tree on the original nodes of minimum weight.
*
* Prim's algorithm is in many ways similar to Dijkstra's algorithm.  Starting
* at an arbitrary node in the graph, we grow the spanning tree outward one
* edge at a time by adding the cheapest outgoing edge from the spanned nodes
* to a node not in the spanning tree.  The key difference between Dijkstra's
* algorithm and Prim's algorithm is that Dijkstra's algorithm creates a
* shortest-path tree from the source node, while Prim's algorithm builds an
* MST from the source node.
*
* The main advantage of Prim's algorithm is that it can be made to run in
* O(|E| + |V| lg |V|) using some clever optimizations and a Fibonacci heap.
* The main algorithm is as follows.  First, as in Dijkstra's algorithm,
* create a Fibonacci heap and assign each node infinite priority.  Next,
* pick some arbitrary node to use as the source node, set its priority to
* zero, and then decrease the key of each connected node to the cost of the
* edge connecting that node to the source node.  Now, we repeat the following
* procedure until a tree is found:
*
* 1. Dequeue some node from the priority queue.  This node will be the node
*    connected to the existing MST by the least-cost edge.
* 2. Scan over the edges leaving this node and find the minimum-cost node
*    connecting it to the existing MST nodes.  This is the node that caused
*    the node to have its priority.
* 3. Add this edge to the MST.
*
* The runtime of this algorithm can be shown to be O(|E| + |V| lg |V|) using
* a Fibonacci heap as follows.  First, we do O(|V|) insertions into the heap,
* which takes O(|V|) time.  We then do O(|V|) dequeues (since we only want
* a total of |V| - 1 edges).  These dequeues take a total of O(|V| lg |V)
* time, though any one dequeue might take much more than that.  Finally, on
* each dequeue, we scan all of the outgoing edges from the dequeued node.
* Since we never consider the same node twice, the total number of edges
* visited by all iterations of this step must be twice the number of edges
* in the graph, since each edge will be visited once from each endpoint.
* This contributes the final O(|E|) term to the runtime, for a net of an
* elegant O(|E| + |V| lg |V|).
*
* This implementation relies on the existence of a FibonacciHeap class, also
* from the Archive of Interesting Code.  You can find it online at
*
*         http://keithschwarz.com/interesting/code/?dir=fibonacci-heap
*/

import java.util.*; // For HashMap

public final class Prim {
/**
* Given a connected undirected graph with real-valued edge costs,
* returns an MST of that graph.
*
* @param graph The graph from which to compute an MST.
* @return A spanning tree of the graph with minimum total weight.
*/

public static <T> UndirectedGraph<T> mst(UndirectedGraph<T> graph) {
/* The Fibonacci heap we'll use to select nodes efficiently. */
FibonacciHeap<T> pq = new FibonacciHeap<T>();

/* This Fibonacci heap hands back internal handles to the nodes it
* stores.  This map will associate each node with its entry in the
* Fibonacci heap.
*/

Map<T, FibonacciHeap.Entry<T>> entries = new HashMap<T, FibonacciHeap.Entry<T>>();

/* The graph which will hold the resulting MST. */
UndirectedGraph<T> result = new UndirectedGraph<T>();

/* As an edge case, if the graph is empty, just hand back the empty
* graph.
*/

if (graph.isEmpty())
return result;

/* Pick an arbitrary starting node. */
T startNode = graph.iterator().next();

/* Add it as a node in the graph.  During this process, we'll use
* whether a node is in the result graph or not as a sentinel of
* whether it's already been picked.
*/

/* Begin by adding all outgoing edges of this start node to the
* Fibonacci heap.
*/

/* Now, until we have added |V| - 1 edges to the graph, continously
* pick a node and determine which edge to add.
*/

for (int i = 0; i < graph.size() - 1; ++i) {
/* Grab the cheapest node we can add. */

/* Determine which edge we should pick to add to the MST.  We'll
* do this by getting the endpoint of the edge leaving the current
* node that's of minimum cost and that enters the visited edges.
*/

T endpoint = minCostEndpoint(toAdd, graph, result);

/* Add this edge to the graph. */

/* Explore outward from this node. */
}

/* Hand back the generated graph. */
return result;
}

/**
* Given a node in the source graph and a set of nodes that we've visited
* so far, returns the minimum-cost edge from that node to some node that
* has been visited before.
*
* @param node The node that has not been considered yet.
* @param graph The original graph whose MST is being computed.
* @param result The resulting graph, used to check what has been visited
*               so far.
*/

private static <T> T minCostEndpoint(T node, UndirectedGraph<T> graph,
UndirectedGraph<T> result) {
/* Track the best endpoint so far and its cost, initially null and
* +infinity.
*/

T endpoint = null;
double leastCost = Double.POSITIVE_INFINITY;

/* Scan each node, checking whether it's a candidate. */
for (Map.Entry<T, Double> entry : graph.edgesFrom(node).entrySet()) {
/* If the endpoint isn't in the nodes constructed so far, don't
* consider it.
*/

if (!result.containsNode(entry.getKey())) continue;

/* If the edge costs more than what we know, skip it. */
if (entry.getValue() >= leastCost) continue;

/* Otherwise, update our guess to be this node. */
endpoint = entry.getKey();
leastCost = entry.getValue();
}

/* Hand back the result.  We're guaranteed to have found something,
* since otherwise we couldn't have dequeued this node.
*/

return endpoint;
}

/**
* Given a node in the graph, updates the priorities of adjacent nodes to
* take these edges into account.  Due to some optimizations we make, this
* step takes in several parameters beyond what might seem initially
* required.  They are explained in the param section below.
*
* @param node The node to explore outward from.
* @param graph The graph whose MST is being computed, used so we can
*              get the edges to consider.
* @param pq The Fibonacci heap holding each endpoint.
* @param result The result graph.  We need this information so that we
*               don't try to update information on a node that has
*               already been considered and thus isn't in the queue.
* @param entries A map from nodes to their corresponding heap entries.
*                We need this so we can call decreaseKey on the correct
*                elements.
*/

private static <T> void addOutgoingEdges(T node, UndirectedGraph<T> graph,
FibonacciHeap<T> pq,
UndirectedGraph<T> result,
Map<T, FibonacciHeap.Entry<T>> entries ) {
/* Start off by scanning over all edges emanating from our node. */
for (Map.Entry<T, Double> arc : graph.edgesFrom(node).entrySet()) {
/* Given this arc, there are four possibilities.
*
* 1. This endpoint has already been added to the graph.  If so,
*    we ignore the edge since it would form a cycle.
* 2. This endpoint is not in the graph and has never been in
*    the heap.  Then we add it to the heap.
* 3. This endpoint is in the graph, but this is a better edge.
*    Then we use decreaseKey to update its priority.
* 4. This endpoint is in the graph, but there is a better edge
*    to it.  In that case, we similarly ignore it.
*/

if (result.containsNode(arc.getKey())) continue// Case 1

if (!entries.containsKey(arc.getKey())) { // Case 2
entries.put(arc.getKey(), pq.enqueue(arc.getKey(), arc.getValue()));
}
else if (entries.get(arc.getKey()).getPriority() > arc.getValue()) { // Case 3
pq.decreaseKey(entries.get(arc.getKey()), arc.getValue());
}

// Case 4 handled implicitly by doing nothing.
}
}
};