/**
* @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-2015 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
#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, int rand, int &index_partition, int distance)
{
Entiers sommets_adj;
if(sommetsSource->size()==1){
Entiers tailles;
for(uint i=0;isize());
}
uint tmp=*max_element(tailles.begin(),tailles.end());
for(uint i=0; isize() == tmp)
{
sommetsSource->clear();
for(uint id = 0; id < Partition.at(i)->size();id++){
sommetsSource->push_back(Partition.at(i)->at(id));
}
index_partition = i;
if(distance != -1){
ggp(g, sommetsSource, sommetsDestination, Partition,
Partition.at(i)->at(rand_fini(0,Partition.at(i)->size())),
index_partition, distance);
}else{
ggp(g, sommetsSource, sommetsDestination, Partition,
rand_fini(0,Partition.at(i)->size()),
index_partition, distance);
}
return;
}
}
}
double poids_max=0;
for(uint i=0;isize();i++){
poids_max+=(*g)[sommetsSource->at(i)]._weight;
}
poids_max/=2.;
double poids;
if(distance == -1){
poids=(*g)[sommetsSource->at(rand)]._weight;
sommetsDestination->push_back(sommetsSource->at(rand));
sommetsSource->erase(sommetsSource->begin() + rand);
}else{
poids=(*g)[rand]._weight;
sommetsDestination->push_back(rand);
suprim_val(*sommetsSource,rand);
}
uint cpt = 0;
while(poidssize()>1)
{
if(cptsize()){
adjacence_ggp(sommetsDestination->at(cpt),sommets_adj,g);
} else{
int 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);
}
if(sommets_adj.size() == 0)
{
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]);
}
else if(poids>=poids_max || sommetsSource->size() == 1){
sort(sommetsDestination->begin(), sommetsDestination->end());
return;
}
}
/*std::cout<<"Sommets_source :"<size();i++){
std::cout<at(i)<<",";
}
std::cout<size();i++){
std::cout<at(i)<<",";
}
std::cout<begin(), sommetsDestination->end());
}
void Transfert_vertex_bissection(UnorientedGraph *g, Entiers *sommetsSource, Entiers *sommetsDestination, Entiers &sommets_adj, const std::string &name, double &poids, double &cut){
std::vector sommets_cut;
sort(sommets_adj.begin(), sommets_adj.end());
for(uint i=0;ipush_back(sommets_adj[recherche_val_double(sommets_cut,*min_element(sommets_cut.begin(),sommets_cut.end()))]);
//std::cout<<"*** Passage 3 cuta ***"<at(rand_fini(0,sommetsSource->size()));
diff = Diff_cut_ratio_bissection(g, sommetsSource, tmp_tir, name);
}
poids += (*g)[tmp_tir]._weight;
if(name == "cut"){
cut = modif_Cout_coupe(*sommetsDestination,tmp_tir,cut,g);
}else{
cut = Modif_ratio_cut(g, sommetsSource, sommetsDestination, tmp_tir, cut);
}
sommetsDestination->push_back(tmp_tir);
suprim_val(*sommetsSource,tmp_tir);
}
bool Best_transfert_vertex_bissection(UnorientedGraph *g, Entiers *sommetsSource, Entiers *sommetsDestination, Entiers &sommets_adj,
const std::string &name, double &poids, double poids_max, double PC, int stop, int &cpt, double &cut){
Liste_Voisin(*sommetsDestination,sommets_adj,*g);
//sort(sommets_adj.begin(), sommets_adj.end());
if((sommets_adj.size() == 0) & (cptsize()>1))
{
cpt++;
//std::cout<<"*** Passage 1 ***"<size()>1)){
Best_transfert_vertex_bissection(g, sommetsSource, sommetsDestination, sommets_adj,
name, poids, poids_max, PC, stop, cpt, cut);
}else{
//std::cout<<"*** Passage 1ac ***"<=stop)){
//std::cout<<"*** Passage 2 ***"<size()==1){
//std::cout<<"*** Passage 4 ***"<size()==1){
Entiers tailles;
for(uint i=0;isize());
}
uint tmp=*max_element(tailles.begin(),tailles.end());
for(uint i=0; isize()==tmp)
{
sommetsSource->clear();
for(uint id = 0; id < Partition.at(i)->size();id++){
sommetsSource->push_back(Partition.at(i)->at(id));
}
index_partition = i;
if(distance != -1)
gggp_pond(g,sommetsSource,sommetsDestination,Partition,
Partition.at(i)->at(rand_fini(0,Partition.at(i)->size())),
index_partition, name, distance);
else
gggp_pond(g, sommetsSource, sommetsDestination,
Partition, rand_fini(0,Partition.at(i)->size()),
index_partition, name ,distance);
return;
}
}
}
for(uint i=0;isize();i++){
poids_max+=(*g)[sommetsSource->at(i)]._weight;
}
poids_max/=2.;
if(distance == -1){
poids=(*g)[sommetsSource->at(rand)]._weight;
if(name == "cut"){
cut = Degree(*g,sommetsSource->at(rand));
}else if(name == "ratio"){
cut = Degree(*g,sommetsSource->at(rand));
double tmp_cut = cut/2./(*g)[sommetsSource->at(rand)]._weight
+ cut/2./(Cluster_Weight(*g,*sommetsSource)-(*g)[sommetsSource->at(rand)]._weight);
cut = tmp_cut;
}
sommetsDestination->push_back(sommetsSource->at(rand));
sommetsSource->erase(sommetsSource->begin() + rand);
}else{
poids=(*g)[rand]._weight;
cut = Degree(*g,rand);
if(name == "ratio"){
double tmp_cut = cut/2./(*g)[rand]._weight + cut/2./(Cluster_Weight(*g,*sommetsSource)-(*g)[rand]._weight);
cut = tmp_cut;
}
sommetsDestination->push_back(rand);
suprim_val(*sommetsSource,rand);
}
while(poidssize()>1)
{
int cpt = 0;
bool next = Best_transfert_vertex_bissection(g, sommetsSource, sommetsDestination, sommets_adj,
name, poids, poids_max, 20, 2, cpt, cut);
if(next == true){
sort(sommetsDestination->begin(), sommetsDestination->end());
return;
}
}
sort(sommetsDestination->begin(), sommetsDestination->end());
}
/*Liste_Voisin(*sommetsDestination,sommets_adj,*g);
if(sommets_adj.size()==0)
{
std::cout<<"*** Passage ***"<begin(), sommetsDestination->end());
return;
}
}else{
sort(sommetsDestination->begin(), sommetsDestination->end());
return;
}
}
else{
Transfert_vertex_bissection(g, sommetsSource, sommetsDestination, sommets_adj, name, poids);
}*/
void Iter_2l(EntiersEntiers &part, int nbr_parties, UnorientedGraph *g,
const std::string &nom_cut, int nbr_tirage,
const std::string &nom_strat, bool rec, int distance)
{
UnorientedGraph copy_graph;
boost::copy_graph(*g,copy_graph);
int cpt = 0;
for(int i = 0; i color;
color.push_back("[color=blue2, fontcolor=blue2];");
color.push_back("[color=red, fontcolor=red];");
color.push_back("[color=green, fontcolor=green];");
color.push_back("[color=turquoise, fontcolor=turquoise];");
color.push_back("[color=saddlebrown, fontcolor=saddlebrown];");
color.push_back("[color=indigo, fontcolor=indigo];");
color.push_back("[color=yellow, fontcolor=yellow2];");
color.push_back("[color=orange, fontcolor=orange];");
color.push_back("[color=olivedrab, fontcolor=olivedrab];");
color.push_back("[color=gold, fontcolor=gold];");
color.push_back("[color=slateblue2, fontcolor=slateblue2];");
color.push_back("[color=dimgrey, fontcolor=dimgrey];");
color.push_back("[color=cyan, fontcolor=cyan];");
color.push_back("[color=purple1, fontcolor=purpule1];");
color.push_back("[color=crimson, fontcolor=crimson];");
color.push_back("[color=black, fontcolor=black];");
std::vector nom;
char * tmp_nom1 = "../../sortie_graphe/Tests/Graphes/Bissection/txt/bissection_1.txt";
nom.push_back(tmp_nom1);
char * tmp_nom2 = "../../sortie_graphe/Tests/Graphes/Bissection/txt/bissection_2.txt";
nom.push_back(tmp_nom2);
char * tmp_nom3 = "../../sortie_graphe/Tests/Graphes/Bissection/txt/bissection_3.txt";
nom.push_back(tmp_nom3);
char * tmp_nom4 = "../../sortie_graphe/Tests/Graphes/Bissection/txt/bissection_4.txt";
nom.push_back(tmp_nom4);
char * tmp_nom5 = "../../sortie_graphe/Tests/Graphes/Bissection/txt/bissection_5.txt";
nom.push_back(tmp_nom5);
char * tmp_nom6 = "../../sortie_graphe/Tests/Graphes/Bissection/txt/bissection_6.txt";
nom.push_back(tmp_nom6);
char * tmp_nom7 = "../../sortie_graphe/Tests/Graphes/Bissection/txt/bissection_7.txt";
nom.push_back(tmp_nom7);
char * tmp_nom8 = "../../sortie_graphe/Tests/Graphes/Bissection/txt/bissection_8.txt";
nom.push_back(tmp_nom8);
char * tmp_nom9 = "../../sortie_graphe/Tests/Graphes/Bissection/txt/bissection_9.txt";
nom.push_back(tmp_nom9);
char * tmp_nom10 = "../../sortie_graphe/Tests/Graphes/Bissection/txt/bissection_10.txt";
nom.push_back(tmp_nom10);
std::ofstream GRAPH2 (nom.at(cpt), std::ios::out);
GRAPH2<<"graph G {"<(copy_graph)[*vertexIt]._index)
GRAPH2<<(copy_graph)[*neighbourIt]._index<<";";
}
GRAPH2<<"}"<size(); t++)
{
GRAPH2<<(copy_graph)[part.at(k)->at(t)]._index<size() > Partition.at(i)->size())
Partition.at(i)->swap(**it1);
}
}
for(int j = 0; jsize();
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 parts_number)
{
EntiersEntiers Partition;
Entiers random_order; //gestion d'un tableau contenant tout les sommets et ranger de façon aléatoire
uint cpt = 0;
for (uint i=0 ; ipush_back(random_order.at(id));
cpt++;
if(cpt == parts_number)
cpt = 0;
}
for(uint i = 0 ; i < Partition.size() ; i++){
sort(Partition.at(i)->begin(),Partition.at(i)->end());
}
return Partition;
}
void Coarsening_Phase(Base_Graph &baseg, ListEntiersEntiers &liste_corr,
uint niveau, int nbr_vertex,
std::string parameter){
uint cpt = 0;
bool stop = false;
while(!stop){
if(parameter == "HEM")
stop = contraction_HEM_degree(baseg.at(cpt), baseg,
liste_corr, niveau, nbr_vertex);
else
stop = contraction_Random_Maching(baseg.at(cpt), baseg,
liste_corr, niveau, nbr_vertex);
cpt++;
}
}
EntiersEntiers Partitioning_Phase(const Base_Graph &baseg,
const std::vector &numeric_parameters,
const std::vector ¶meters,
int distance){
EntiersEntiers Partition;
if(parameters.at(1) == "gggp" || parameters.at(1) == "ggp"){
Entiers *part = new Entiers();
for(uint i = 0; ipush_back(i);
Partition.push_back(part);
bissectionRec(baseg.at(baseg.size()-1), Partition,
numeric_parameters.at(1), parameters.at(3),
numeric_parameters.at(2), parameters.at(1),
distance);
}
else
Partition = Random_partitioning(baseg.at(baseg.size()-1),
numeric_parameters.at(1));
return Partition;
}
void Uncoarsening_Phase(const Base_Graph &baseg,
EntiersEntiers &Partition,
const std::vector ¶meters,
ListEntiersEntiers &liste_corr,
double poids_moy, bool rec){
ListEntiersEntiers::iterator lit(liste_corr.end());
bool proj;
uint taille_list = liste_corr.size();
if(liste_corr.size()==0){
taille_list = 1;
proj = true;
}
else{
lit--;
proj = false;
}
std::vector nom;
std::vector nom_a;
if(rec){
const char * tmp_nom1 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_1.txt";
nom.push_back(tmp_nom1);
const char * tmp_nom_a1 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_1.txt";
nom_a.push_back(tmp_nom_a1);
const char * tmp_nom2 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_2.txt";
nom.push_back(tmp_nom2);
const char * tmp_nom_a2 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_2.txt";
nom_a.push_back(tmp_nom_a2);
const char * tmp_nom3 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_3.txt";
nom.push_back(tmp_nom3);
const char * tmp_nom_a3 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_3.txt";
nom_a.push_back(tmp_nom_a3);
const char * tmp_nom4 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_4.txt";
nom.push_back(tmp_nom4);
const char * tmp_nom_a4 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_4.txt";
nom_a.push_back(tmp_nom_a4);
const char * tmp_nom5 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_5.txt";
nom.push_back(tmp_nom5);
const char * tmp_nom_a5 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_5.txt";
nom_a.push_back(tmp_nom_a5);
const char * tmp_nom6 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_6.txt";
nom.push_back(tmp_nom6);
const char * tmp_nom_a6 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_6.txt";
nom_a.push_back(tmp_nom_a6);
const char * tmp_nom7 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_7.txt";
nom.push_back(tmp_nom7);
const char * tmp_nom_a7 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_7.txt";
nom_a.push_back(tmp_nom_a7);
const char * tmp_nom8= "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_8.txt";
nom.push_back(tmp_nom8);
const char * tmp_nom_a8 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_8.txt";
nom_a.push_back(tmp_nom_a8);
const char * tmp_nom9 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_9.txt";
nom.push_back(tmp_nom9);
const char * tmp_nom_a9 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_9.txt";
nom_a.push_back(tmp_nom_a9);
const char * tmp_nom10 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_10.txt";
nom.push_back(tmp_nom10);
const char * tmp_nom_a10 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_10.txt";
nom_a.push_back(tmp_nom_a10);
const char * tmp_nom11 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_11.txt";
nom.push_back(tmp_nom11);
const char * tmp_nom_a11 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_11.txt";
nom_a.push_back(tmp_nom_a11);
const char * tmp_nom12 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_12.txt";
nom.push_back(tmp_nom12);
const char * tmp_nom_a12 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_12.txt";
nom_a.push_back(tmp_nom_a12);
const char * tmp_nom13 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_13.txt";
nom.push_back(tmp_nom13);
const char * tmp_nom_a13 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_13.txt";
nom_a.push_back(tmp_nom_a13);
const char * tmp_nom14 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_14.txt";
nom.push_back(tmp_nom14);
const char * tmp_nom_a14 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_14.txt";
nom_a.push_back(tmp_nom_a14);
const char * tmp_nom15 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_15.txt";
nom.push_back(tmp_nom15);
const char * tmp_nom_a15 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_15.txt";
nom_a.push_back(tmp_nom_a15);
const char * tmp_nom16 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_16.txt";
nom.push_back(tmp_nom16);
const char * tmp_nom_a16 = "../../sortie_graphe/Tests/Graphes/Multiniveau/txt/projection_partition_affine_16.txt";
nom_a.push_back(tmp_nom_a16);
}
for(uint y =0 ; y < taille_list ; y++){
if(!proj){
projection(Partition,lit);
if(rec)
Plot_UnorientedGraph_All(baseg.at(baseg.size()-2-y),
Partition,nom.at(y), true);
double cut = Cut_cluster(Partition,
*baseg.at(baseg.size()-2-y),
parameters.at(3));
if(parameters.at(2) == "charge")
Affinage_equilibrage_charge(baseg.at(baseg.size()-2-y),
Partition);
else if(parameters.at(2) == "locale"){
Affinage_recherche_locale(baseg.at(baseg.size()-2-y),
Partition, cut, parameters.at(3));}
else
Affinache_gain_diff(baseg.at(baseg.size()-2-y),
Partition, cut,
parameters.at(3), poids_moy);
if(rec)
Plot_UnorientedGraph_All(baseg.at(baseg.size()-2-y),
Partition, nom_a.at(y), true);
lit--;
}
}
}
/* std::vector parameters :
* 0 -> contraction : nom de la méthode de contraction
* 1 -> type_methode : nom de la méthode de partitionnement
* 2 -> choix_affinage : nom de la méthode d'affinage
* 3 -> type_cut : nom de la fonction objectif étudiée
*
* std::vector numeric_parameters :
* 0 -> niveau_contraction : niveau de contraction à atteindre
* 1 -> nbr_parties : nombre de parties de la partition
* 2 -> nbr_tirage : nombre de tirage de sommet de depart
* 3 -> distance : distance minimum de selection de sommet
* de depart par default -1
*/
OrientedGraphs Multiniveau(OrientedGraph *go,
const std::vector &numeric_parameters,
const std::vector ¶meters,
Edges& /* edge_partie */,
OutputEdgeList& outputedgelist,
InputEdgeList& inputedgelist,
Connections& connections,
bool rec, int distance)
{
boost::timer t;
UnorientedGraph *g = new UnorientedGraph();
make_unoriented_graph(*go, *g);
Base_Graph baseg;
baseg.push_back(g);
ListEntiersEntiers liste_corr;
OrientedGraphs Graphes;
int val_cpt = num_vertices(*g);
bool time = true;
double t1, t2, t3, t4;
if(numeric_parameters.at(0) != val_cpt && parameters.at(1) != "rand"){
Coarsening_Phase(baseg, liste_corr, numeric_parameters.at(0), val_cpt, parameters.at(0));
if(rec){
std::ofstream GRAPHp ("../../sortie_graphe/Tests/Graphes/Bissection/poids_graphe.txt", std::ios::out);
GRAPHp<<"Poids du graphe contracté : "< "<<(*baseg.at(baseg.size()-1))[*vertexIt]._weight<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;
}
//double t5 = t.elapsed();
//std::cout << "Devs : " << (t5 - t4)<size() ; i++)
Random_list_vertices.push_back(i);
for (uint j=0 ; jsize()-1 ; j++) {
uint rand_pos = rand()%(Partition.at(index_partition)->size()-j)+j;
uint tmp = Random_list_vertices[j];
Random_list_vertices[j] = Random_list_vertices[rand_pos];
Random_list_vertices[rand_pos] = tmp;
}
if(Partition.at(index_partition)->size()< nbr_tirage)
nbr_tirage = Partition.at(index_partition)->size();
/*Boucle de conservation de la meilleure bissection*/
for(int k = 0; ksize();t++)
tmp_part->push_back(Partition.at(index_partition)->at(t));
if(name_strat == "gggp")
gggp_pond(g, tmp_part, part2, Partition,
Random_list_vertices.at(k), index_partition,
name_cut , -1);
else if(name_strat == "ggp")
ggp(g, tmp_part, part2, Partition,
Random_list_vertices.at(k), index_partition ,-1);
else
std::cout<<"Nom de stratégie de partitionnement non valide ! "<size();i++)
{
for (uint j=0; jsize();j++)
{
remove_edge(part_cour_cons->at(i),part2_cons->at(j),*g);
}
}
/*Modification des informations*/
delete Partition.at(index_partition);
Partition.at(index_partition)=part_cour_cons;
Partition.push_back(part2_cons);
}
void Optimisation_method_neighbour_distance(UnorientedGraph *g,
EntiersEntiers &Partition, int index_partition,
int nbr_tirage, int distance, const std::string &name_cut,
const std::string &name_strat){
/*Initialisation des parametres*/
Entiers *part2_cons = new Entiers();
Entiers *part_cour_cons = new Entiers();
double cut=1000000000.;
int val;
std::list vertex_list;
for(uint verx =0; verxsize(); verx++){
vertex_list.push_back(Partition.at(index_partition)->at(verx));
}
if(Partition.at(index_partition)->size()< nbr_tirage)
nbr_tirage = Partition.at(index_partition)->size();
/*Boucle de conservation de la meilleure bissection*/
for(int k = 0; k::iterator Iter;
if(vertex_list.size()!=0){
Iter = vertex_list.begin();
for(int i = 0; isize();t++)
tmp_part->push_back(Partition.at(index_partition)->at(t));
if(name_strat == "gggp")
gggp_pond(g, tmp_part, part2, Partition, val,
index_partition, name_cut, distance);
else if(name_strat == "ggp")
ggp(g, tmp_part, part2, Partition, val,
index_partition, distance);
else
std::cout<<"Nom de stratégie de partitionnement non valide ! "<size();i++)
{
for (uint j=0; jsize();j++)
{
remove_edge(part_cour_cons->at(i), part2_cons->at(j), *g);
}
}
/*Modification des informations*/
delete Partition.at(index_partition);
Partition.at(index_partition)=part_cour_cons;
Partition.push_back(part2_cons);
}
void Optimisation_method_neighbour_degree(UnorientedGraph *g,
EntiersEntiers &Partition, int index_partition,
const std::string &name_cut,
const std::string &name_strat){
std::vector vertex_degree;
Entiers *part2 = new Entiers();
for(uint i =0; isize(); i++)
vertex_degree.push_back(Degree(*g,
Partition.at(index_partition)->at(i)));
uint best_cpt = 0;
double best_degree = vertex_degree.at(0);
for(uint i =1; ibest_degree){
best_degree = vertex_degree.at(i);
best_cpt = i;
}
}
if(name_strat == "gggp")
gggp_pond(g, Partition.at(index_partition), part2,
Partition, best_cpt, index_partition,
name_cut, -1);
else if(name_strat == "ggp")
ggp(g ,Partition.at(index_partition), part2, Partition,
best_cpt, index_partition, -1);
else
std::cout<<"Nom de stratégie de partitionnement non valide ! "<size();i++){
for (uint j=0; jsize();j++){
remove_edge(Partition.at(index_partition)->at(i),
part2->at(j), *g);
}
}
Partition.push_back(part2);
}
void Optimisation_method_neighbour_minweight(UnorientedGraph *g,
EntiersEntiers &Partition, int index_partition,
const std::string &name_cut,
const std::string &name_strat){
std::vector vertex_weight;
Entiers *part2 = new Entiers();
for(uint i =0; isize(); i++){
vertex_weight.push_back((*g)[Partition.at(index_partition)->at(i)]._weight);
}
uint best_cpt = 0;
double best_weight = vertex_weight.at(0);
for(uint i =1; ibest_weight){
best_weight = vertex_weight.at(i);
best_cpt = i;
}
}
if(name_cut == "ratio"){
int tmp_best_cpt;
tmp_best_cpt = Partition.at(index_partition)->at(best_cpt);
best_cpt = tmp_best_cpt;
}
if(name_strat == "gggp"){
gggp_pond(g, Partition.at(index_partition), part2,
Partition, best_cpt, index_partition,
name_cut, -1);
} else if(name_strat == "ggp"){
ggp(g, Partition.at(index_partition), part2,
Partition, best_cpt, index_partition, -1);
} else {
std::cout<<"Nom de stratégie de partitionnement non valide ! "<size();i++)
{
for (uint j=0; jsize();j++)
{
remove_edge(Partition.at(index_partition)->at(i),
part2->at(j), *g);
}
}
Partition.push_back(part2);
}
void tirage_distance(UnorientedGraph *g, int tirage,
std::list &vertex_list, int distance){
std::vector > vertex_delete;
std::list liste1;
std::list vd;
liste1.push_back(tirage);
vertex_delete.push_back(liste1);
for(int i=0; i liste_tmp;
std::list::iterator Ite_tmp;
for(Ite_tmp = vertex_delete.at(i).begin();
Ite_tmp != vertex_delete.at(i).end();
Ite_tmp ++){
tie(neighbourIt, neighbourEnd) =
adjacent_vertices(*Ite_tmp,*g);
for (; neighbourIt != neighbourEnd; ++neighbourIt){
liste_tmp.push_back(*neighbourIt);
}
}
liste_tmp.sort();
liste_tmp.unique();
vertex_delete.push_back(liste_tmp);
}
for(int index = 0; index < vertex_delete.size(); index ++){
vd.merge(vertex_delete.at(index));
}
vd.unique();
std::list::iterator Ite;
for(Ite = vd.begin(); Ite != vd.end(); Ite ++){
vertex_list.remove(*Ite);
}
}
} } } // namespace paradevs tests boost_graph