/*--------------------------kruskal algo implementation to find Minimum Spanning Tree (MST) of a weighted undirected graph------------------------*/
/*------------------------------kruskal.h  this is header file-------------------------*/
/* Author: Laxman Kasyap 24/oct/2009 */


#include <iostream>
#include <tbb/tbb.h>
#include <tbb/task_scheduler_init.h>
#include <tbb/blocked_range.h>
#include <tbb/parallel_do.h>
#include <tbb/parallel_sort.h>
#include <vector>
#include <map>
#include <algorithm>
#include <fstream>

using namespace std;
using namespace tbb;

#ifndef _kruskal
#define _kruskal

class kruskal{

              private:	

                      struct Edge{  int vi,vj,w;   };                                     // each struct Edge stores the 2 vertexes and weight of each edge in the graph
                      typedef Edge* argument_type;        
                      vector <Edge*> edges;                                               //stores the graph
                      vector <Edge*> mst;                                                 //stores the MST
                      vector<int> circles;                                                //used to prevent any circles in the MST
                      int n;                                                              //number of nodes

              public:
                  
				     kruskal(int a);                                                       //constructor initialises number of nodes n=a
                     static bool lequal(Edge const* t1, Edge const* t2);                   //function used as 3rd argument in parallel_sort
                     void init_graph(map<int,map<int,int> >m);                             //initialises the edges with given graph as map
                     void kruskalApply();                                                  //applies kruskal algo on edges and finds MST
                     void showGraph();                                                     //shows the MST

             };
		

kruskal::kruskal(int a){ n=a; }                        //constructor

static bool kruskal::lequal(Edge const* t1, Edge const* t2){ return (t1->w<t2->w); }      //comparision funtion    

void kruskal::init_graph(map<int,map<int,int> >m){                                        //initialising the vector<Edge *> edges with the graph given

                                                  Edge *e;
                                                  map<int,map<int,int> >::iterator it1;
                                                  map<int,int>::iterator it2;
                                                  for(it1=m.begin();it1!=m.end();it1++)
                                                  for(it2=(it1->second).begin();it2!=(it1->second).end();it2++){
                                                                                                               e = new Edge;
                                                                                                               e->vi=it1->first; e->vj=it2->first; e->w=it2->second; 
                                                                                                               ed.push_back(e); 

                                                                                                               }

                                                 }                

void kruskal::kruskalApply(){

                             parallel_sort(edges.begin(),edges.end(),kruskal::lequal);    //applying parallel sort so the edges sort in increasing order of weights
							                                                              //here is where iam getting the problem after calling this function my nodes
																						  //values and weights change to 1
                             int number;
                             for(int i=1;i<=n;i++) circles.push_back(i);
                             while(mst.size()<n-1) {
                                                   if(circles[edges[0]->vi]!=circles[edges[0]->vj]) {                                //prevents any cycles in MST
                                                                                                    number = circles[edges[0]->vj];
                                                                                                    for(int i=1;i<n;i++) {
                                                                                                                         if(circles[i]==number)
                                                                                                                         circles[i] = circles[edges[0]->vi];
                                                                                                                         }

                                                                                                    mst.push_back(edges[0]);

                                                                                                    }
                                                    edges.erase(edges.begin(),edges.begin()+1);

                                                    }

                            }   


void kruskal::showGraph(){                                                                 //outputs the mst obtained into a file kruskal.out

                         int W=0;
                         ofstream fout("kruskal.out");
                         fout<<endl<<"i       j         weight"<<endl;
                         for(unsigned int i=0;i<mst.size();i++) {
                                                                W+=mst[i]->w;
                                                                fout<<mst[i]->vi<<"      "<<mst[i]->vj<<"      "<<mst[i]->w<<endl;
                                                                 }
                         fout<<"The Minimun Spanning Tree has cost: "<<W<<endl;

                         }

#endif