// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Daniel Liles (Los Alamos National Laboratory), Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#include <stdio.h>
#include <strstream.h>
#include <LINK/graph/Graph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/graph/Attribute.h>
#include <LINK/basic/Set.h>
#include <LINK/basic/DJSet.h>
#include <LINK/basic/BinaryHeap.h>
#include <LINK/algorithm/Algorithms.h>


//
// minimum spanning tree, Kruskal's algorithm
//
Set<Edge*> 
Kruskal(Graph* graph, char* graph_view) 
{
    Vertex *vertex1, *vertex2;
    Edge *edge;

    ResetAttributes(graph);
 
    // temporary attributes used by the algorithm
    Attribute<DJSet*> dj_set(graph, "DJSet", (DJSet*) 0);
    
    int edgeCount = graph->size();

    // make disjoint sets
    Vertex** vertices = graph->vertexStart();
    int order = graph->order();
    int i;
    for (i=0; i < order; i++) {
        DJSet* djset = new DJSet(vertices[i]->name());
        setAttribute((GraphObject*) vertices[i], "DJSet", djset);
    }

    // sort edges by weight by using a binary heap
    BinaryHeap<double,Edge*> heap(edgeCount);

    const MSet<Edge*>& edges = graph->edges();
    Iterator<Edge*> get_edge(&edges);
    while (get_edge(edge)) {
        double weight;
        getAttribute((GraphObject*) edge, "weight", weight);
	setAttribute((GraphObject*) edge, "mark", 0);
        heap.insert(weight, edge);
	if (graph_view) {
		ostrstream oss;
		char *wgt;
		oss << weight << ends;
		wgt = oss.str();
    		animateEdge(edge, graph_view, "label", 
					      "edge-label", INIT_STEP, wgt);
		// must incorporate LINK_DYNAMIC
	}
    }

    for (i = 0; i < edgeCount; i++) {
        edge = (heap.extractMin())->item;
        Iterator<Vertex*> get_Vertices(edge->vertices());
        get_Vertices(vertex1);

        while (get_Vertices(vertex2)) {
            DJSet* set_a;
            DJSet* set_b;
            getAttribute((GraphObject*) vertex1, "DJSet", set_b);
            getAttribute((GraphObject*) vertex2, "DJSet", set_a);
            DJSet* parent_a = set_a->findSet();
            DJSet* parent_b = set_b->findSet();
	    if (graph_view) {
	    	Vertex *v1 = graph->findVertexByName(set_a->id());
	    	Vertex *v2 = graph->findVertexByName(set_b->id());
	    	Vertex *p1 = graph->findVertexByName(parent_a->id());
	    	Vertex *p2 = graph->findVertexByName(parent_b->id());
		animateVertex(v1, graph_view, "color","color",
					      ALG_STEP, (char *)"green");
		animateVertex(v2, graph_view,"color","color",
					      ALG_STEP, (char *)"green");
		animateVertex(p1, graph_view,"color","color",
					      ALG_STEP, (char *)"orange");
		animateVertex(p2, graph_view,"color","color",
					      ALG_STEP, (char *)"orange");
	    }
            if (parent_a != parent_b) {
	        parent_a->joinWith(parent_b);
	        setAttribute((GraphObject*) edge, "mark", 1);
		animateEdge(edge, graph_view,"color", "color", 
					      ALG_STEP, (char *)"red");
            } else
		animateEdge(edge, graph_view,"color", "color",
					      ALG_STEP, (char *)"black");
            vertex1 = vertex2;
        }
    }

    int ord = graph->order();
    for (int j=0; j < ord; j++) {
        DJSet* djset;
        getAttribute((GraphObject*) vertices[j], "DJSet", djset);
        delete djset;
    }
    Set<Edge*> result;
    get_edge.reset();
    while (get_edge(edge)) {
        int tree_edge;
        getAttribute((GraphObject*) edge, "mark", tree_edge);
	if (tree_edge)
		result.insert(edge);
    }
    return result;
}