Reading graph from stream to vector of adjacency list

Question

I am trying to create a graph as adjacency list by reading from a file shown below

Here first line is number of vertices. In example below we have 12 verttices and in following lines for example 1 2 3 4 means vertex 1 had edges to 2, 3, and 4.

12
1 2 3 4
2 1 5 6
3 1 6
4 1 7
5 2 9 10
6 2 3
7 4 8 
8 4 7
9 5 10
10 5 9
11 12
12 11

C++ program

#include <iostream>
#include <fstream>
#include <strstream>
#include <sstream> // for std::getline

#include "Graph.h"

using namespace std;

// Note: vector index is will match the vertex id.
std::vector <std::vector<std::pair<int, int> > > vecIdxedGraph;


void storeEdges(const string& strEdges) {
    std::istringstream iss(strEdges);
    int FromVertex = 0;
    iss >> FromVertex;

    std::cout << "From Vertex " << FromVertex << endl;

    vector<pair<int, int>> edges;
    string toVertex;
    while (std::getline(iss, toVertex, ' ')) {
        std::cout << "to Vertex " << toVertex << " ";
        edges.push_back(std::make_pair(atoi(toVertex.c_str()), 0));
    }
    std::cout << std::endl;
    vecIdxedGraph.push_back(edges);
    return;
}

void printGraph() {
    for (int i = 0; i < vecIdxedGraph.size(); i++) {
        cout << "Vertex " << i + 1 << " ";
        for (int j = 0; j < vecIdxedGraph[i].size(); j++) {
            cout << vecIdxedGraph[i][j].first << " ";
        }
        cout << endl;
    }
}
int main() {

    // create Graph
    ifstream inFile("Graph.txt");
    if (!inFile) {
        cout << "Open input file failed." << endl;
    }

    // Set input stream to file.
    std::streambuf* pOldCinBuf = cin.rdbuf();
    cin.set_rdbuf(inFile.rdbuf());

    int iNumberOfNodes;
    cin >> iNumberOfNodes;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    cout << "Number of nodes in graph are: " << iNumberOfNodes << endl;

    vecIdxedGraph.reserve(iNumberOfNodes);



    for (int iVertexId = 1; iVertexId <= iNumberOfNodes; iVertexId++) {
        std::string vertIdDetails;
        std::getline(cin, vertIdDetails);
        // cout << (vertIdDetails.c_str()) << endl;
        // parse line and store to the vector.
        storeEdges(vertIdDetails);
        // cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    printGraph();
    return 0;
}

Following is output

Vertex 1 0 2 3 4
Vertex 2 0 1 5 6
Vertex 3 0 1 6
Vertex 4 0 1 7
Vertex 5 0 2 9 10
Vertex 6 0 2 3
Vertex 7 0 4 8
Vertex 8 0 4 7
Vertex 9 0 5 10
Vertex 10 0 5 9
Vertex 11 0 12
Vertex 12 0 11

Want to remove 0. I think 0 is coming from empty space while reading a line

while (std::getline(iss, toVertex, ' '))

I am not getting how to clear it.

Another question is how can I create a vector with default constructed so that I can use

vecIdxedGraph[FromVertex] = ..., rather than push_back.

Kindly help

Answer 1

Looks like you are over complicating stuff here. You would simply need, something like following.

// Some handy names
using Pair = std::pair<int, int>;
using Graph = std::vector<std::vector<Pair>> ;

// The stream handle
std::ifstream fileHandle("Graph.txt");

size_t iNumberOfNodes  = 0;

// 1. Get # of Vertices
fileHandle >> iNumberOfNodes;

// 2. Create a graph, pre allocate the # of vertices
// One node extra since your vertices starts from 1
Graph g{iNumberOfNodes + 1, std::vector<Pair>{}}; 

std::string lineStr;
int currNode = 0, vertex;
// 3. Iterate over file, reading line by line
while ( std::getline(fileHandle, lineStr) ) {
   std::stringstream ss{lineStr};
    ss >> currNode;
    while ( currNode != 0 && ss >> vertex ) {
        g[currNode].emplace_back( vertex, 0 ) ; // weight = 0;
    }   
 }

You're all set! Demo Here