reading&maintaining graph in C++

Question

I have a text file from where I would read an undirected graph. The format is as follows:

1 2 3
2 1
3 1

Where every first element in the row corresponds to a vertice, and the rest is basically the adjacency list for the vertice.

So my two questions are:

• 1) What is the best way to read this info in C++? With the following code segment I can read all the info consequtively but of course that's not what I want to achieve in the end. I want to be able to separate the info of different rows in a decent way.(This part is actually closely related to my second question, as seen below)

  void inputHandle(ifstream& f, int arr[], string fileName)
  {
  
      f.open(fileName);
  
      if (!f) {
          cout << "Unable to open file";
          exit(1); // terminate with error
      }
  
      string temp;
      int i = 0, numTemp;
  
      while(f >> temp){
          numTemp= atoi(temp.c_str());
          arr[i] = numTemp;
          cout<<arr[i];
          i++;
      }
  
      f.close();
  }
  

• 2) What would be the best data structure to preserve this graph? I will be implementing a mincut algorithm hence I'll be modifying the graph with each iteration(deleting/modifying rows).

Thanks in advance for the help.

Answer 1

I would store graphs as either a adjacency list or a matrix, in C++ here is one way of coding this. Depending on performance/storage requirements you may need to tweak this.

vector< list<int> > graph;

or you could use an adjaceny matrix.

vector< vector<bool> > graph;

As for reading your file format, I would use getline() to read the file line by line and then parse each line for the integer values (perhaps with istringstream), something like this perhaps:

ifstream f;

vector< list<int> > graph;

f.open(fileName);
while(!f.eof() && !f.fail())
{
    char line[1024]; // Reserve enough space for longest line
    f.getline(line, 1024);

    istringstream iss(line, istringstream::in);

    int vertex;
    iss >> vertex;
    if(!f.fail())
    {
        if(vertex > graph.size()) // Max number of vertex is unknown
        {
            graph.resize(vertex); 
        }
        vertex--; // From your 1-base to zero-based
        list<int>& vertex_list = graph[vertex];
        do
        {
            int to_vertex;
            iss >> to_vertex;
            if(!iss.fail())
            {
               vertex_list.push_back(to_vertex - 1);
            }
        } while(!iss.eof() && !iss.fail());
    }
}