/**
* @file tests/boost_graph/partitioning/gggp.cpp
* @author The PARADEVS Development Team
* See the AUTHORS or Authors.txt file
*/
/*
* PARADEVS - the multimodeling and simulation environment
* This file is a part of the PARADEVS environment
*
* Copyright (C) 2013 ULCO http://www.univ-litoral.fr
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
#include
#include
#include
namespace paradevs { namespace tests { namespace boost_graph {
extern UnorientedGraph::vertex_iterator vertexIt, vertexEnd;
extern UnorientedGraph::adjacency_iterator neighbourIt, neighbourEnd;
extern OrientedGraph::vertex_iterator vertexIto, vertexEndo;
extern OrientedGraph::adjacency_iterator neighbourIto, neighbourEndo;
void ggp(UnorientedGraph *g, Entiers *sommetsSource,
Entiers *sommetsDestination, EntiersEntiers &Partition)
{
//std::cout<<""<size()==1){
val=0;
//std::cout<<"Entré dans le debug ! "<size());
}
uint tmp=*max_element(tailles.begin(),tailles.end());
for(uint i=0; isize()==tmp)
{
ggp(g,Partition[i],sommetsDestination,Partition);
return;
}
}
}
else
val=rand_fini(0,sommetsSource->size()-1);//Tirage aléatoire de l'indice du premier sommet entre 0 et taille du tableau -1
//std::cout<<"val : "<at(val)<size();i++){
poids_max+=(*g)[sommetsSource->at(i)]._weight;
}
poids_max/=2.;
double poids=(*g)[sommetsSource->at(val)]._weight;
sommetsDestination->push_back(sommetsSource->at(val));
sommetsSource->erase(sommetsSource->begin() + val);
int cpt = 0;
// std::cout<<"taille sommetsSource avant le while : "<size()<size()>1)
{
//std::cout<<"taille sommetsSource dans le while "<size()<size() )
adjacence_ggp(sommetsDestination->at(cpt),sommets_adj,g);
else{
val=rand_fini(0,sommetsSource->size()-1);
sommetsDestination->push_back(sommetsSource->at(val));
sommetsSource->erase(sommetsSource->begin() + val);
adjacence_ggp(sommetsDestination->at(cpt),sommets_adj,g);
}
/*std::cout<<"adj :"<size();i++)
{
for (uint j=0; jsize();j++)
{
remove_edge(sommetsSource->at(i),sommetsDestination->at(j),*g);
}
}
sort(sommetsDestination->begin(), sommetsDestination->end());
return;
}
else{
for(uint i =0; isize()!=1){
sommetsDestination->push_back(sommets_adj.at(i));
poids+=(*g)[sommets_adj.at(i)]._weight;
suprim_val(*sommetsSource, sommets_adj[i]);
}
if(poids>poids_max || sommetsSource->size()==1)
break;
}
/*std::cout<<"Sommets_source :"<size();i++){
std::cout<at(i)<<",";
}
std::cout<size();i++){
std::cout<at(i)<<",";
}
std::cout<poids_max || sommetsSource->size()==1){
for (uint i=0; isize();i++)
{
for (uint j=0; jsize();j++)
{
remove_edge(sommetsSource->at(i),sommetsDestination->at(j),*g);
}
}
sort(sommetsDestination->begin(), sommetsDestination->end());
return;
}
sommets_adj.clear();
cpt++;
}
}
for (uint i=0; isize();i++)
{
for (uint j=0; jsize();j++)
{
remove_edge(sommetsSource->at(i),sommetsDestination->at(j),*g);
}
}
sort(sommetsDestination->begin(), sommetsDestination->end());
}
void Iter_2l(EntiersEntiers &part, int nbr_parties, UnorientedGraph *g,
const std::string &nom)
{
if (nom =="gggp"){
for(int i = 0; isize() > Partition.at(i)->size())
Partition.at(i)->swap(**it1);
}
}
for(int j = 0; jsize() - 1 == 0) {
Entiers tailles;
val = 0;
for (uint i = 0;i < Partition.size(); i++) {
tailles.push_back(Partition.at(i)->size());
}
uint tmp = *max_element(tailles.begin(), tailles.end());
for (uint i = 0; i < Partition.size(); i++) {
if (Partition.at(i)->size() == tmp) {
gggp(g, Partition.at(i), sommetsDestination, Partition);
}
break;
}
} else {
// Tirage aléatoire de l'indice du premier sommet entre 0 et
// taille du tableau -1
val = rand_fini(0, sommetsSource->size() - 1);
}
float poids_max=sommetsSource->size()/2.;
float poids=1;
Entiers sommets_cut;
//clog<<"Etape 1 : "<push_back(sommetsSource->at(val));
sommetsSource->erase(sommetsSource->begin() + val);
if (sommetsSource->size() < 2) {
return;
}
while (poids < poids_max) {
// for(uint i =0; i< sommetsDestination.size();i++){
// std::cout<size();i++)
{
for (uint j=0; jsize();j++)
{
remove_edge(sommetsSource->at(i),sommetsDestination->at(j),*g);
}
}
sort(sommetsDestination->begin(), sommetsDestination->end());
return;
} else {
/*clog<<"Liste voisin est : "<push_back(sommets_adj[tmp]);
suprim_val(*sommetsSource, sommets_adj[tmp]);
suprim_val(sommets_adj, sommets_adj[tmp]);
sommets_cut.clear();
poids++;
}
}
for (uint i = 0; i < sommetsSource->size(); i++) {
for (uint j = 0; j < sommetsDestination->size(); j++) {
remove_edge(sommetsSource->at(i), sommetsDestination->at(j), *g);
}
}
sort(sommetsDestination->begin(), sommetsDestination->end());
}
void gggp_pond(UnorientedGraph *g, Entiers *sommetsSource,
Entiers *sommetsDestination, EntiersEntiers &Partition)
{
int val;
Entiers sommets_adj;
if(sommetsSource->size()==1){
val=0;
Entiers tailles;
for(uint i=0;isize());
}
uint tmp=*max_element(tailles.begin(),tailles.end());
for(uint i=0; isize()==tmp)
{
gggp_pond(g,Partition[i],sommetsDestination,Partition);
return;
}
}
}
else
val=rand_fini(0,sommetsSource->size()-1);
double poids_max=0;
for(uint i=0;isize();i++){
poids_max+=(*g)[sommetsSource->at(i)]._weight;
}
poids_max/=2.;
double poids=(*g)[sommetsSource->at(val)]._weight;
std::vector sommets_cut;
float cut = Degree(*g,sommetsSource->at(val));
sommetsDestination->push_back(sommetsSource->at(val));
sommetsSource->erase(sommetsSource->begin() + val);
while(poidssize()>1)
{
Liste_Voisin(*sommetsDestination,sommets_adj,*g);
if(sommets_adj.size()==0)
{
for (uint i=0; isize();i++)
{
for (uint j=0; jsize();j++)
{
remove_edge(sommetsSource->at(i),sommetsDestination->at(j),*g);
}
}
sort(sommetsDestination->begin(), sommetsDestination->end());
return;
}
else{
sort(sommets_adj.begin(), sommets_adj.end());
for(uint i=0;ipush_back(sommets_adj[recherche_val2(sommets_cut,*min_element(sommets_cut.begin(),sommets_cut.end()))]);
poids+=(*g)[sommets_adj[recherche_val2(sommets_cut,*min_element(sommets_cut.begin(),sommets_cut.end()))]]._weight;
suprim_val(*sommetsSource, sommets_adj[recherche_val2(sommets_cut,*min_element(sommets_cut.begin(),sommets_cut.end()))]);
suprim_val(sommets_adj, sommets_adj[recherche_val2(sommets_cut,*min_element(sommets_cut.begin(),sommets_cut.end()))]);
sommets_cut.clear();
}
}
for (uint i=0; isize();i++)
{
for (uint j=0; jsize();j++)
{
remove_edge(sommetsSource->at(i),sommetsDestination->at(j),*g);
}
}
sort(sommetsDestination->begin(), sommetsDestination->end());
}
// void gggp_pond(UnorientedGraph *g, Entiers *sommetsSource,
// Entiers *sommetsDestination, EntiersEntiers &Partition)
// {
// int val;
// Entiers sommets_adj;
// if(sommetsSource->size()==1){
// val=0;
// //std::cout<<"Entré dans le debug ! "<size());
// }
// uint tmp=*max_element(tailles.begin(),tailles.end());
// for(uint i=0; isize()==tmp)
// {
// gggp_pond(g,Partition[i],sommetsDestination,Partition);
// return;
// }
// }
// }
// else
// val=rand_fini(0,sommetsSource->size()-1);//Tirage aléatoire de l'indice du premier sommet entre 0 et taille du tableau -1
// //std::cout<<"val : "<at(val)<size();i++){
// poids_max+=(*g)[sommetsSource->at(i)]._weight;
// }
// poids_max/=2.;
// double poids=(*g)[sommetsSource->at(val)]._weight;
// std::vector sommets_cut;
// float cut = Degree(*g,sommetsSource->at(val));
// sommetsDestination->push_back(sommetsSource->at(val));
// sommetsSource->erase(sommetsSource->begin() + val);
// // std::cout<<"taille sommetsSource avant le while : "<size()<size()>1)
// {
// //std::cout<<"taille sommetsSource dans le while "<size()<size();i++)
// {
// for (uint j=0; jsize();j++)
// {
// remove_edge(sommetsSource->at(i),sommetsDestination->at(j),*g);
// }
// }
// sort(sommetsDestination->begin(), sommetsDestination->end());
// return;
// }
// else{
// sort(sommets_adj.begin(), sommets_adj.end());
// /*std::cout<<"adj :"<push_back(sommets_adj[recherche_val2(sommets_cut,*min_element(sommets_cut.begin(),sommets_cut.end()))]);
// //std::cout<<"Sommet deplacé : "<size();i++){
// std::cout<at(i)<<",";
// }
// std::cout<size();i++){
// std::cout<at(i)<<",";
// }
// std::cout<size();i++)
// {
// for (uint j=0; jsize();j++)
// {
// remove_edge(sommetsSource->at(i),sommetsDestination->at(j),*g);
// }
// }
// sort(sommetsDestination->begin(), sommetsDestination->end());
// //std::cout<<"fin du gggp_pond"<size() > Partition.at(i)->size())
// Partition.at(i)->swap(**it1);
// }
// }
// for(int j = 0; jsize(); j++){
// // std::cout<at(j)<<" ";
// // }
// // std::cout<<"\n"<size();
uint cpt_sommets=1;
int val;
uint cpt;
if(nbr_parties==size){
for(uint i = 0; i < nbr_parties;i++){
if(Partition.at(0)->size()!=1)
{
val=rand_fini(0,Partition.at(0)->size()-1);//tirage aléatoire d'un sommets
}
else
val=0;
int vertex = Partition.at(0)->at(val);
Entiers *part = new Entiers();
part->push_back(vertex);// ajout du sommet tiré
suprim_val(*Partition.at(0),vertex);//suppression du sommet dans la premiere partie
}
}
/*
* Boucle sur le nombre de partie à réaliser
*/
for(uint i = 0; i < nbr_parties-1;i++){
if(Partition.at(0)->size()!=1)
{
val=rand_fini(0,Partition.at(0)->size()-1);//tirage aléatoire d'un sommets
}
else
val=0;
int vertex = Partition.at(0)->at(val);
/*
* Initialisation d'un pointeur sur un vecteur d'entier, dans notre cas
* la n+1 ième partie de la partition
*/
Entiers *part = new Entiers();
part->push_back(vertex);// ajout du sommet tiré
suprim_val(*Partition.at(0),vertex);//suppression du sommet dans la premiere partie
cpt=1;
/*
* Pour chaque element de la nouvelle partie faire
*/
for(uint j = 0; jsize();j++){
/*
* Détermination des voisins de chacun des sommets de cette nouvelle
* partie et ajoue de ce voisin si celui-ci est présent dans la première partie (Partition[0])
*/
tie(neighbourIt, neighbourEnd) = adjacent_vertices(part->at(j),*g);
for (; neighbourIt != neighbourEnd; ++neighbourIt){
if(In_tab(*Partition.at(0),*neighbourIt)==1){
// std::cout<<"le voisin déplacé est : "<<*neighbourIt<push_back(*neighbourIt);
cpt_sommets++;
suprim_val(*Partition.at(0),*neighbourIt);
cpt++;
}
/*
* Si le nombre moyen de sommets est atteind dans la partie on sort de la boucle des voisins
* Même chose si l'on a rencontré le nombre total de sommets
*/
if(cpt==(size/nbr_parties)+1)
break;
if(cpt_sommets==size)
break;
}
/*
* Même chose
*/
if(cpt==(size/nbr_parties)+1)
break;
if(cpt_sommets==size)
break;
}
Partition.push_back(part);// ajoue de la nouvelle partie à la partition
if(cpt_sommets==size)
break;
}
}
EntiersEntiers Random_partitioning(UnorientedGraph *g,
uint nbr_parties)
{
EntiersEntiers Partition;
Entiers random_order; //gestion d'un tableau contenant tout les sommets et ranger de façon aléatoire
for (uint i=0 ; ipush_back(random_order.at(i));
}
Partition.push_back(part);
}
Entiers *part = new Entiers();
for(uint i = (nbr_parties-1)*size; i < random_order.size(); i++){
part->push_back(random_order.at(i));
}
Partition.push_back(part);
for(uint i = 0 ; i < Partition.size() ; i++){
sort(Partition.at(i)->begin(),Partition.at(i)->end());
}
return Partition;
}
OrientedGraphs Multiniveau(uint niveau_contraction,
UnorientedGraph *g,
UnorientedGraph *graph_origin,
OrientedGraph *go,
int nbr_parties,
std::string contraction,
std::string type_methode,
std::string choix_affinage,
std::string type_cut,
Edges& /* edge_partie */,
OutputEdgeList& outputedgelist,
InputEdgeList& inputedgelist,
Connections& connections)
{
EntiersEntiers Partition;
Entiers *part = new Entiers();
Base_Graph baseg;
baseg.push_back(g);
ListEntiersEntiers liste_corr;
uint cpt =0;
int val_cpt = num_vertices(*g);
bool stop = false;
if (niveau_contraction == val_cpt) {
stop = true;
}
while(stop != true)
{
if(contraction == "HEM")
stop = contraction_HEM(baseg.at(cpt),baseg,liste_corr,niveau_contraction,val_cpt);
else
stop = contraction_Random_Maching(baseg.at(cpt),baseg,liste_corr,niveau_contraction,val_cpt);
cpt++;
// std::cout<<"passage"<push_back(i);
}
Partition.push_back(part);
bissectionRec(baseg.at(baseg.size()-1),Partition,nbr_parties,type_methode);
double cut_norm = Cut_cluster(Partition,*gtmp,"norm");
// std::cout<<"Cout de coupe normalisé initial : "<push_back(i);
}
new_Partition.push_back(new_part);
bissectionRec(baseg.at(baseg.size()-1),new_Partition,nbr_parties,type_methode);
double new_cut_norm = Cut_cluster(new_Partition,*gtmp,"norm");
// std::cout<<"Nouveau cout de coupe normalisé : "<size(); j++)
// {
// std::cout<at(j)<<" ";
// }
// std::cout<<"\n"<begin(); it1 != (*it)->end(); it1++)
{
delete *it1;
*it1 = NULL;
}
delete *it;
*it = NULL;
}
for(Base_Graph::iterator it = baseg.begin(); it != baseg.end(); it++)
{
delete *it;
*it = NULL;
}
return Graphes;
}
} } } // namespace paradevs tests boost_graph