1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
|
Graphe::Graphe(int nbNoeuds, int nbAretes)
{
// we create the set of nodes
nodesGeneration(nbNoeuds);
// we create a set of Edges
edgesGeneration(nbAretes);
}
void Graphe::nodesGeneration(int nbNoeuds)
{
for (int i(0); i<nbNoeuds; i++)
{
m_ensNoeuds.push_back(Noeud(i));
}
}
void Graphe::edgesGeneration(int nbAretes)
{
// Definitions
int nbAretesRestantes(nbAretes);
int noeudsCandidats[2];
int noeudsInseres[nbAretes][2];
int poids(0);
bool presenceArete(true);
// Initialization
srand(time(0));
// Treatment
do
{
do
{
noeudsCandidats[0]=rand()%m_ensNoeuds.size();
noeudsCandidats[1]=rand()%m_ensNoeuds.size();
presenceArete=presenceAreteDansListe(noeudsInseres,nbAretes-nbAretesRestantes,noeudsCandidats[0], noeudsCandidats[1]);
}
while(presenceArete);
poids=rand()%10 +1; // random number between 1 and 10
m_ensArete.push_back(Arete(m_ensNoeuds[noeudsCandidats[0]], m_ensNoeuds[noeudsCandidats[1]],poids));
noeudsInseres[nbAretes-nbAretesRestantes][0]=noeudsCandidats[0];
noeudsInseres[nbAretes-nbAretesRestantes][1]=noeudsCandidats[1];
nbAretesRestantes-=1;
}
while (nbAretesRestantes>0);
}
void Graphe::afficherGraphe(std::ostream& flux)
{
for (int i(0); i<m_ensArete.size(); i++)
{
flux << m_ensArete[i];
}
}
bool presenceAreteDansListe(int noeudsInseres[][2], int taille, int noeudDepart, int noeudFin)
{
bool resultat(false);
for (int i(0); i<taille; i++)
{
if((noeudsInseres[i][0]==noeudDepart && noeudsInseres[i][1]==noeudFin) ||
(noeudsInseres[i][1]==noeudDepart && noeudsInseres[i][0]==noeudFin))
{
resultat=true;
break;
}
}
return resultat;
}
ostream& operator<< (ostream& flux, Graphe grapheAAfficher)
{
grapheAAfficher.afficherGraphe(flux);
flux;
} |
Partager