C++ Création d'un graphique pondéré?

Question

Comment créer un graphe pondéré C++ où chaque sommet du graphe a un poids (une valeur entière)?

Vous pouvez télécharger mon projet graphique here (Rapidshare):

Voici la fonction pour créer un graphique à partir des données de graphique stockées dans un fichier texte:

void GraphType::createGraph() 
{ 
    ifstream infile; 
    char fileName[50]; 

    int index; 
    int vertex; 
    int adjacentVertex; 

    if(gSize != 0) 
     clearGraph(); 

    cout << "Enter input file name: "; 
    cin >> fileName; 
    cout << endl; 

    infile.open(fileName); 

    if(!infile) 
    { 
      cout << "Cannot open input file." << endl; 
      return; 
    } 

    infile >> gSize; 

    graph = new UnorderedLinkList[gSize]; 

    for(index = 0; index < gSize; index++) 
    { 
      infile >> vertex; 
      infile >> adjacentVertex; 

      while(adjacentVertex != -999) 
      { 
       graph[ vertex ].insertLast(adjacentVertex); 
       infile >> adjacentVertex; 
      } 
    } 
    infile.close(); 
} 

Et voici les données Graphique (= nombre de sommets 10, le sommet de 0 à 9 et les sommets adjacents) d'entrée de fichier texte "Network2.txt":

0 1 2 9 -999

1 0 2 -999

2 0 1 9 8 3 -999

3 2 8 5 -999

4 3 8 6 5 -999

5 4 6 7 -999

6 4 7 8 -999

7 8 6 5 -999

8 9 2 3 4 6 7 -999

9 0 2 8 -999

Ma question est, Comment attribuer une valeur unique ou en poids de sommets 0 à 9? Toute aide sera vraiment appréciée. Merci d'avance!

Answer 1

Dans votre liste d'adjacences, au lieu de la stocker uniquement les index du nœud adjacent, faites-lui stocker une structure contenant les index du nœud adjacent et une valeur pour le tronçon connectant ces nœuds.

Answer 2

Le Boost Graph Library (BGL) offre le type MutablePropertyGraph, dans lequel chaque arête et sommet peuvent stocker un poids en tant que propriété. Voir le example here, qui construit un graphique dirigé avec des bords pondérés.