How to fill an adjacency list for a weighted graph?

Question

I am trying to read a file in c++ and populate my vector which represents an adjacency list.The file contains an adjacency list representation of an undirected weighted graph.Each row consists of the node tuples that are adjacent to that particular vertex along with the length of that edge. For example, the 6th row has 6 as the first entry indicating that this row corresponds to the vertex labeled 6. The next entry of this row "141,8200" indicates that there is an edge between vertex 6 and vertex 141 that has length 8200. The rest of the pairs of this row indicate the other vertices adjacent to vertex 6 and the lengths of the corresponding edges.

File eg:-

1 3,4 2,20 5,89
2 4,7 1,102

ifstream ifs;
string line;
ifs.open("dijkstraData.txt");
cout<<log(vertices)<<" "<<loops<<endl;
std::vector<vector < std::pair < int,int > > > CadjList(vertices);
while(getline(ifs,line)){
    // transfer the line contents to line_stream
    stringstream line_stream(line);
    //now what
}

Can't do your homework for you but I can give hints: 1) Split your string (http://stackoverflow.com/a/237280/1938163) 2) Split again 3) String to integer with http://www.cplusplus.com/reference/string/stoi/ 4) Populate your data vector. Good luck. — Marco A., Jun 15 '14 at 08:53

score 1 · Accepted Answer · answered Jun 16 '14 at 06:00

First I extracted the vertex and put it in a , then I extracted all the subsequent strings into rest and then it was just a matter of finding the comma and converting both the substrings into integers. I used atoi to convert string to int because I do not have C++11 on my machine , but I will recommend to update your gcc and use std::stoi .

while(getline(ifs,line)){
        stringstream line_stream(line);
        line_stream>>a;
        while(line_stream>>rest){
            int pos = rest.find(",");
            string vertex = rest.substr(0,pos);
            string weight = rest.substr(pos+1,rest.length() - pos);
            int ver = atoi(vertex.c_str());
            int wei = atoi(weight.c_str());
            pair<int,int> foo(ver,wei);
            v[a-1].push_back(foo);
        }
    }

score 1 · Answer 2 · answered Jun 18 '14 at 12:02

Another solution where you don't need atoi and will be a little bit shorter.

while (getline(ifs, line)) {
    for (string& ch : line) if (ch == ',') ch = ' ';        

    stringstream line_stream(line);
    int a; line_stream >> a;

    for (int node, length; line_stream >> node >> length; ) {
        v[a].push_back({ node, length });
    }
}

How to fill an adjacency list for a weighted graph?

2 Answers2