Discussion :

[siriki26]

salut a tous voici mon projet en c++ quelqu'un peut me donner des idées

Crée en c++ une classe permettant d'implementer un graphe selon le model suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
class graph 
{
private :
int rechercher_indice_sommet(string id);
public:
int creer_sommet(string id);
int creer_arret(string u, string v,double pds=0);
in enregistrer(string fichier);
int ouvrir(string fichier);
};

sachant que les methodes creer_sommeet ;creer_arret doivent permettre de créer respectivement les sommets et les arêtes (pondérées ou non) de toute instance de cette classe. La méthode rechercher_indice_sommet permettant de vérifier l'existence d'un sommet et de retrouver son indice le cas échéant. La méthode enregistrer doit permettre de sauvegarder les éléments du graphe (sommets + arêtes) dans un fichier texte ou binaire. Tandis que la méthode enregistrer permettra quant à elle, de recréer les éléments d'un graphe à partir du contenu du fichier fourni en paramètre


Selon votre groupe vous devez ajouter à la classe Graph une méthode court chemin dijkstra(string u, string v ) ;court_chemin_bellman_Ford (string u, string v), court_chemin_floyd warshall(string u, string v), permettant de rechercher respectivement le plus court chemin entre deux sommets selon les algorithmes de Dijkstra, de Bellman-Ford et de Floyd-Warshall. Ne pas oublier d'implémenter également les méthodes parcours_profondeur() et parcours largeur () permettant de parcourir le graphe respectivement en profondeur*et*en*largeur.

[bacelar]

La définition de la classe "graph" sens bon le "C with class" plutôt que le C++ moderne (int en valeur de retour, manque "const", une using namespace std implicite, etc...).
Est-ce un biais de votre formation qui commence par du C puis du C++ ou un truisme de votre prof pour le C et non le C++ ?

Concept de base de l'informatique : diviser les "gros" problèmes en problèmes plus simples.

Commencez par choisir une manière de représenter un graphe de manière souple (donc pas performant) pour ne pas être bloqué plus tard.
(Moi, stratégie de faignant, je chercherais une bibliothèque dédiée, mais peut-être pas très pertinent pour votre apprentissage)

Les algorithmes utilisés ont une influence non négligeable sur l'efficacité d'une représentation d'un graphe ou pas.
Il vous faut donc connaitre un minimum l'algorithme à implémenter pour savoir si la représentation du graphe lui convient ou pas.
(Donc réfléchissez à 2 fois avant de pomper le travail d'un autre groupe. )

[siriki26]

Mais vous pouviez me donner un exemplaire de code source de l'implémentation des graphes en c++

[bacelar]

Bin, si vous voulez pomper sans comprendre, prenez le code source des dites bibliothèques.
Sinon, répondez aux questions qu'on vous pose.

[siriki26]

Bin, si vous voulez pomper sans comprendre, prenez le code source des dites bibliothèques.
Sinon, répondez aux questions qu'on vous pose.

ok posez les questions je vais vous repondre

[bacelar]

Quelle algo ?
Quelles structures de données maîtriser-vous ?
Avez-vous droit à des bibliothèques dédiées ?
Si oui, les quelles ?

Avez-vous déjà réfléchi à la structuration des données ?
Si oui, quel le résultat de cette réflexion ?

Avec cette structure de données, avez-vous tenté d'implémenter les algorithmes ?
Si oui, qu'est-ce qui coince ?

[siriki26]

Quelle algo ?
Quelles structures de données maîtriser-vous ?
Avez-vous droit à des bibliothèques dédiées ?
Si oui, les quelles ?

Avez-vous déjà réfléchi à la structuration des données ?
Si oui, quel le résultat de cette réflexion ?

Avec cette structure de données, avez-vous tenter d'implémenter les algorithmes ?
Si oui, qu'est-ce qui coince ?

ok moi suis un debutant dans la programmation c'est un projet qui m'a ete donner en classe pour implementer les graphes en langage C++
et puisse que je n'ai pas beaucoup de notion sur le langage donc c'est pourquoi je demande de l'aide
Si vous comprenez l'exercice expliquer moi comment on fait
pour les bibliothèques ils nous a demandé d'utiliser les bibliothèques: string,vector,iostream,fstream avec les headers
et on doit utiliser la structure des CLASSES

[foetus]

Il faut utiliser des sites comme https://cplusplus.com/ ou https://en.cppreference.com/w/

Par exemple, la classe std::string sa documentation

1 graphe en informatique est composé d'1 liste de sommets et d'1 liste d'arêtes (2 sommets).
Dans ton exercice :

• 1 sommet est identifié par 1 identifiant de type "chaîne de caractères" (<- ce n'est pas idéal, mais pourquoi pas)
• comme 1 arête peut être pondérée, je ne pense pas que tu puisses utiliser std::pair. Tu peux éventuellement faire 1 arête "paire de sommets", et ensuite 1 paire "arête, poids"

Donc tu peux commencer par faire 1 petite structure pour 1 arête ("edge" en anglais).
Par exemple, avec tous les attributs en public, pas d'accesseur/ mutateur (on appelle cela 1 dto ["Data Transfer Object"] ou 1 objet valeur ["value object"[)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
struct t_one_edge {
public:
 
    t_one_edge() : weight(0.0) {}
 
 
public:
 
     std::string u;
     std::string v;
     /*unsigned*/ double weight;
};

Édit: ici, 1 arête est composée de 2 identifiants de sommets u et v (et d'1 poids).
Mais on pourrait aussi à la place des 2 identifiants "chaine de caractères", stocker les indices des 2 sommets dans la liste des sommets du graphe. Mais cela crée des indirections, ce qui peut être "complexe" à gérer pour 1 débutant.

Ainsi:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
class t_graph {
// ...
 
private:
 
    std::vector<std::string> list_vertices;
    std::vector<t_one_edge>  list_edges;
};

La recherche est assez triviale. Le retour de l'indice n'est pas génial, parce que 0 veut dire soit faux soit premier sommet
retourne la taille de list_vertices si non trouvé.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
size_t t_graph::find_vertice_index(string id) {
    if ( id.empty() ) { return list_vertices.size(); }
 
    size_t index, nb_vertices;
    bool no_found;
 
    no_found = true;
 
    for(index=0, nb_vertices=list_vertices.size(); (no_found && (index < nb_vertices)); ++index) {
        if (id == list_vertices[index]) { no_found = false; }
    }
 
    return index;
}

Tu peux utiliser les itérateurs, les "for range", 1 lambda, std::find, …

Mais si tu débutes, il faut regarder ton cours et y aller progressivement

[siriki26]

...

svp pouviez vous expliquer vos ligne de code????????

[siriki26]

Voici ce que j'ai commencer mais je suis bloquer si vous pouviez m'aider

en HEADER VOICI MON CODE:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
class Graph
{
private:
    int nbresommets;
    int rechercher_indice_sommet(string id);
 
struct arete
{
    string vers;//PARTIR VERS
    double pds;//POIDS
};
struct sommet
{
    string id;
    vector <struct arete> aretes;
};
vector<struct sommet> graph;
public:
    int creer_sommet(string id);
    int creer_arete(string u,string v,double pds=0);
    bool existearc(string u,string v);//rnvoie vraie ou fausse s'il existe un arc entre deux sommets
//    parcours_en_largeur();
//    parcours_en_profondeur();
    int enregistrer(string fichier);
    int ouvrir(string fichier);
};
 
#endif // GRAPH_H_INCLUDED

en graph.cpp
voici le code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include "graph.h"
#include <string>
#include <vector>
 
using namespace std;
 
int Graph::rechercher_indice_sommet(string id)
{
    vector <struct sommet>::iterator i;
    int idx=0 ;
       for (i=graph.begin();i!=graph.end();++i)
       {
           if((*i).id==id)
                return idx;
           idx++;
       }
       return -1;
 
}
int Graph::creer_sommet(string id)
{
    if(rechercher_indice_sommet(id)==-1)
    {
        struct sommet v;
        v.id=id;
        graph.push_back(v);
    }
    else return -1;
return graph.size();
}
Graph::creer_arete(string u,string v,double pds)
{
    int idx_1=rechercher_indice_sommet(u);
    int idx_2=rechercher_indice_sommet(v);
    if(idx_1!=-1 && idx_2!=-1)
    {
        struct arete a;
        a.vers=v;
        a.pds=pds;
        graph[idx_1].aretes.push_back(a);
        return graph[idx_1].aretes.size();
    }
    return -1;
}
 
//parcours_en_largeur()
//{
//    FILE F;
//    int n;
//    bool *visite=new bool[n+1];
//    cout <<"Entrez le nombre de sommet du graphe"<<endl;
//    cin>>n;
//    for(int i=1;i<=n;++i)
//        visite[i]=false;
//    F.ajouefile(graph[0]);
//    visite[graph[0]]=true;
//    cout <<"resultat du parcours en largeur"<<endl;
//    cout<<"en commencent a partir du sommet "<<s<<" ";
//    cout<<"**************************************"<<endl;
//    while(!F.filevide())
//    {
//        string k=F.enleverfile();
//        cout <<" "<<endl;
//        for(int j=1;j<=n;++j)
//            if(existearc(k,j)&&visite[j]==false)
//        {
//            F.ajouerfile(j);
//            visite[j]=true;
//        }
//    }
//}
//
//void Graph::parcours_en_profondeur()
//{
//    Pile P;
//    bool *visite=new bool[n+1];
//    int i;
//    for(i=1;i<=n;++i)
//        visite[i]=false;
//    P.empiler(s);
//    visite[s]=true;
//    cout <<"parcours en profondeur en commencant par"<<s<<" "<<endl;
//    while (!P.Pilevide())
//    {
//        int k=P.depiler();
//        cout<<k<<endl:
//            for(i=n;i>=1;--i)
//                if(existearc(k,i)&&visite[i]==false)
//            {
//                P.empiler(i);
//                visite[i]=true;
//
//            }
//    }
//    cout <<endl;
//}

et dans le programme principal

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include <iostream>
#include <string>
#include <vector>
 
#include "graph.h"
 
using namespace std;
 
int main()
{
    int nbresommets;
    vector<struct sommet> graph;
    cout <<"combien de sommets voulez-vous créer :";
    cin>>nbresommets;
    cout<<" "<<endl;
    for(int i=1;i<=nbresommets;++i)
    {
        cout <<"entrez l'ID du sommet" <<i<<":"<<endl;
        string id;
        cin>>id;
        int j=creer_sommet(id);
    }
        for(int i=0;i<=graph.size();++i)
    {
        string de=graph[i].id;
        cout <<"le sommet "<< de << " a combien de voisins?"<<endl;
        int nbrevoisins;
        cin>>nbrevoisins;
        cin.ignore();
        for(int i=0;i<nbrevoisins;++i)
        {
            cout <<"entrez l'ID su voisin"<<i+1<< " :";
            string vers;
            getline(cin,vers);
            if(creer_arete(de,vers)==-1)
                cout<<"le voisin " << vers<< " n'existe pas";
        }
    }
 
    return 0;
}

[bacelar]

Avec votre approche où les sommets contiennent les arrêtes, une arrête qui part du sommet A vers le sommet B ne sera pas la même que l'arrête qui part du sommet B vers le sommet A.
Dans certain type de graphes c'est pas gênant, même obligatoire pour les graphes "à arrêtes non symétriques".
Mais je ne vois pas de trace de ce type de problématique dans votre sujet.
Il est possible de maintenir la symétrie avec une couche d'abstraction mais j'ai du mal à y voir un intérêt.

Dans l'exemple de @foetus, il n'y pas cette notion de sommets contenant des arrêtes.
C'est le graphe qui contient les 2 et qui peut maintenir la cohérence entre les groupes, les sommets et les arrêtes.

[siriki26]

Donc vous ne pouvez pas m'aider ?

[bacelar]

???
Vous voulez qu'on le fasse à votre place ce projet ?

@foetus vous a donné une base "saine", pas complexe, et j'ai donné ce qui me semble la principale faille dans votre conception.

Qu'est-ce qui n'est pas clair dans le code de @foetus ?

[siriki26]

Merci à vous