C++ Создание взвешенного графика?

Question

Как создать взвешенный граф C++, где каждая вершина на графике имеет вес (некоторое целочисленное значение)?

Вы можете скачать мой график проекта here (RapidShare):

Здесь функция для создания графика из данных графиков, хранящихся в текстовом файле:

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(); 
} 

А вот данные Graph (число вершин = 10, вершинных 0 до 9 и смежных вершин) ввода из текстового файла "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

Мой вопрос, как я присвоить уникальное значение или вес к вершинам 0 до 9? Любая помощь будет действительно оценена. Заранее спасибо!

Answer 1

В списке смежности вместо того, чтобы просто хранить индексы соседнего узла, сохраните структуру, содержащую индексы соседнего узла, и значение для края, соединяющего эти узлы.

Answer 2

Boost Graph Library (BGL) предлагает тип MutablePropertyGraph, в котором каждый край и вершина могут хранить вес как свойство. См. example here, который создает ориентированный граф с взвешенными краями.