80 lines
2.5 KiB
C++
80 lines
2.5 KiB
C++
#include "GraphColoring.h"
|
||
#include "ParticleSystem.h"
|
||
|
||
using namespace gti320;
|
||
|
||
void GraphColoring::color(ParticleSystem &particleSystem) {
|
||
m_partitions.clear();
|
||
|
||
// La palette de couleurs
|
||
ColorList C;
|
||
|
||
std::vector<Particle> &particles = particleSystem.getParticles();
|
||
std::vector<Spring> &springs = particleSystem.getSprings();
|
||
|
||
// Initialiser toutes les particules avec color = -1
|
||
for (Particle &p: particles) {
|
||
p.color = -1;
|
||
}
|
||
|
||
// Calculer les couleurs de toutes les particules du syst<73>me.
|
||
// Boucler sur chaque particule et appeler la fonction findColor.
|
||
|
||
// Construire les partitions qui correspond <20> chaque couleur.
|
||
// Les partitions sont repr<70>sent<6E>es par un tableau d'indices de particules, un pour chaque couleur.
|
||
// Stocker les partitions dans m_partitions.
|
||
|
||
int i = 0;
|
||
for (Particle &p: particles) {
|
||
int color = findColor(p, particles, springs, C);
|
||
p.color = color;
|
||
|
||
if (m_partitions.size() <= color) {
|
||
m_partitions.emplace_back();
|
||
}
|
||
m_partitions[color].push_back(i * 2);
|
||
m_partitions[color].push_back(i * 2 + 1);
|
||
i++;
|
||
}
|
||
}
|
||
|
||
int
|
||
GraphColoring::findColor(const Particle &p, const std::vector<Particle> &particles, const std::vector<Spring> &springs,
|
||
ColorList &C) const {
|
||
int n = (int) C.size();
|
||
int count[n];
|
||
memset(count, 0, sizeof(int) * n);
|
||
|
||
// Trouver la premi<6D>re couleur de la palette C qui n'est pas attribu<62>e <20> une particule voisine.
|
||
// Si une couleur est introuvable, ajouter une nouvelle couleur <20> la palette et retournez la couleur.
|
||
// Utiliser la fonction findNeighbors pour assembler une liste de particules qui sont directement connect<63>es <20> la particule p par un ressort (les voisines).
|
||
|
||
NeighborList neighbors = findNeighbors(p, particles, springs);
|
||
for (auto const &neighbor: neighbors) {
|
||
count[neighbor->color]++;
|
||
}
|
||
|
||
for (int c = 0; c < n; c++) {
|
||
if (count[c] == 0) {
|
||
return c;
|
||
}
|
||
}
|
||
|
||
C.push_back(n);
|
||
return n;
|
||
}
|
||
|
||
NeighborList GraphColoring::findNeighbors(const Particle &p, const std::vector<Particle> &particles,
|
||
const std::vector<Spring> &springs) const {
|
||
NeighborList N;
|
||
|
||
for (const Spring &s: springs) {
|
||
if (&particles[s.index0] == &p) {
|
||
N.push_back(&particles[s.index1]);
|
||
} else if (&particles[s.index1] == &p) {
|
||
N.push_back(&particles[s.index0]);
|
||
}
|
||
}
|
||
|
||
return N;
|
||
} |