C++ Creating a Weighted Graph?

Question

Hi, How do I create a C++ weighted Graph where each vertex in the graph has a weight (some integer value)?

You can download my graph project here (RapidShare):

Here is the function to create a graph from graph data stored in a text file:

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

And here is the Graph data (number of vertices = 10, vertex 0 to 9 and adjacent vertices) input from text file "Network2.txt":

10

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

My question is, how do i assign a unique value or weight to vertices 0 to 9? Any assistance will be really appreciated. Thanks in advance!

Answer 1

In your adjacency list, instead of having it just store the indexes of the adjacent node, have it store a struct that contains the indexes of the adjacent node, and a value for the edge connecting those nodes.

Answer 2

The Boost Graph Library (BGL) offers type MutablePropertyGraph, within which each edge and vertex can store a weight as a property. See the example here, which builds up a directed graph with weighted edges.