#include "ConnectedComponents.h"

namespace cosi {

namespace algorithms {

namespace graph {

using namespace std;

ConnectedComponents::ConnectedComponents(
		cosi::commstruct::graph::U_RealWeightedGraph* G) {
	mG = G ;
}
void ConnectedComponents::Run() {
	//Insert one set for each vertex
	IdGraph::v_iterator U, V;
	for (U = mG->v_begin() ; U != mG->v_end() ; U++) {
		set<Vertex> S;
		S.insert(*U) ;
		mComponents.insert(S) ;
	}

	for (U = mG->v_begin() ; U != mG->v_end() ; U++) {
		for (V = mG->v_begin() ; V != mG->v_end() ; V++) {
			if (mG->InE(*U, *V)) {
				if (Disjoint(*U, *V)) {
					Union(*U, *V);
				}
			}
		}
	}
}

bool ConnectedComponents::Disjoint(Vertex U, Vertex V) {
	set<set<Vertex> >::iterator It;
	for (It = mComponents.begin() ; It != mComponents.end() ; It++) {
		if (It->find(U) != It->end() && It->find(V) != It->end() )
			return false;
	}
	return true;
}

void ConnectedComponents::Union(Vertex U, Vertex V) {
	set< Vertex > New;
	set<set<Vertex> >::iterator It , ItU , ItV;
	for (It = mComponents.begin() ; It != mComponents.end() ; It++) {
		if (It->find(U) != It->end()) {
			ItU = It ;
		}
		if (It->find(V) != It->end()) {
			ItV = It ;
		}
	}
	New.insert(ItU->begin() , ItU->end()) ;
	New.insert(ItV->begin() , ItV->end()) ;
	mComponents.erase(ItU) ;
	mComponents.erase(ItV) ;
	mComponents.insert(New) ;
}

std::set< std::set<Vertex> > ConnectedComponents::GetComponents() {
	return mComponents ;
}

ConnectedComponents::~ConnectedComponents() {

}

}

}

}
