How to accept graph from input file

Question

I am accepting undirected weighted graph from input file. File contains 200 nodes.
I have written code like this.

typedef pair<int, int> ipair;     
class Graph
{
    int V;
    list< pair <int, int> > *adj;

    public:

    Graph(int V);     
};

Graph::Graph( int V)
{
    this-> V = V;
    adj = new list<ipair>[V];
}

bool Graph :: read_file()
{
   const long int N = 1000000;

   std::ifstream infile("Dijkstra.txt");
   if(!infile.is_open()) return false;
   std::string line;

   int i = 0;
   while ( i < N && getline(infile, line) )
   {
      std::istringstream str(line);
      int u;

      str >> u;
      if ( u > N )
      {
         // Problem.
         abort();
      }

      int v;
      int w;
      while ( str >> v >> w)
      {
         adj[u].push_back(make_pair(v,w));
      }
      ++i;
   }
}

int main()
{
    Graph g(200);
    g.read_file();

    g.print_graph();
    return 0;
}      


I/P file :      

1   80,982  163,8164    170,2620    145,648 200,8021    173,2069    92,647  26,4122 140,546 11,1913 160,6461    27,7905 40,9047 150,2183    61,9146 159,7420    198,1724    114,508 104,6647    30,4612 99,2367 138,7896    169,8700    49,2437 125,2909    117,2597    55,6399      

2   42,1689 127,9365    5,8026  170,9342    131,7005    172,1438    34,315  30,2455 26,2328 6,8847  11,1873 17,5409 157,8643    159,1397    142,7731    182,7908    93,8177

Node 1 is connected to node 80 with weight 982
Node 1 is connected to node 163 with weight 8164

Node 2 is connected to node 42 with weight 1689
Node 2 is connected to node 127 with weight 9365
etc.....
Now with this I can accept node 1 is connected to node 80 with weight 982 (1 80,982 ) but what about remaining nodes which are connected with node 1 ??
i.e. How to make loop for accepting v and w ??

Partha Pratim Mukherjee · Accepted Answer · 2017-05-17T18:02:19.147

I think instead of list< pair <int, int> > *adj in Graph class you can use vector<list< pair <int, int> >> adj to store the data.

I have modified your program slightly to store all the pair of data related to a node.

#include <iostream>
#include <utility>
#include <list>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <vector>

using namespace std;

typedef pair<int, int> ipair;
class Graph
{
  int V;
  vector<list< pair <int, int> >> adj;

public:
  bool read_file();
  void print_graph();
  Graph(int V);
};

Graph::Graph( int V)
{
  this-> V = V;
  adj.reserve(V);
}

bool Graph:: read_file()
{
  const long int N = 1000000;

  std::ifstream infile("Dijkstra.txt");
  if(!infile.is_open()) return false;
  std::string line;

  int i = 0;
  while ( i < N && getline(infile, line) ) {
    std::istringstream str(line);
    int u;

    str >> u;
    if ( u > N ) {
      // Problem.
      abort();
    }

    int v;
    int w;
    char c;
    while ( str >> v >> c >> w) {
      if (u <= (int)adj.size()) { // index (u-1) exists
        auto list = adj[u-1]; // get the existing list
        list.push_back(make_pair(v,w)); // add new data
        adj[u-1] = list; // store it the same index
      } else { // index (u-1) doesn't exist
        list<ipair> list; // create a new list
        list.push_back(make_pair(v,w)); // store the values
        adj.push_back(list); // add it in the vector
      }
    }
    ++i;
  }
  return true;
}

void Graph::print_graph() {
  int node = 1;
  for (auto& x : adj) {
    cout << "from node: " << node++ << endl;
    for (auto it = begin(x); it != end(x); ++it) {
      cout << it->first << " " << it->second << "\n";
    }
  }
}

int main() {
  Graph g(200);
  g.read_file();

  g.print_graph();
  return 0;
}

Thank you for your reply ! But problem is I did not get the code properly. Can you explain your code from while loop ( read_file () ) ?? — Tushar, May 17 '17 at 17:42
Sure! The loop reads v and w from input along with a , in between. Then it checks if there is any element in the adj vector for index (u-1) because programming collections is 0 index based. If not (else block) it creates a list and push_back the newly created list into the vector. Next time (if block) it will find the list at index (u-1) so no need to create it, so we are assigning it to the vector at index (u-1). I will add comments in the code for readability. — Partha Pratim Mukherjee, May 17 '17 at 17:57
Thank you friend ! Way of writing is new for me, so facing difficulty. Still have some doubts , but I will search over it ( like auto keyword ) — Tushar, May 17 '17 at 18:20
You have written like vector >> adj ..... I want to understand how it looks ( diagrammatically) the way fresher understands pointer , so do you have any material which I can refer ?? — Tushar, May 17 '17 at 18:23
http://stackoverflow.com/questions/19504455/would-vector-of-vectors-be-contiguous — Partha Pratim Mukherjee, May 17 '17 at 18:32

score 0 · Answer 2 · answered May 17 '17 at 13:38

You can regex match ,.

e.g.

std::regex pairs_regex("(\d+),(\d+)");
auto pairs_it = std::sregex_iterator(line.begin(), line.end(), pairs_regex);
auto pairs_end = std::sregex_iterator();
for(;pairs_it != pairs_end; ++pairs_it)
{
    std::string v = pairs_it->str(1);
    std::string w = pairs_it->str(2);
    adj[u].push_back(make_pair(std::stoi(v), std::stoi(w)));
}

N.B. it would be safer if adj were a std:: container, not a raw array. The loop body would populate a list<pair<int, int>> temp, then adj.emplace_back(std::move(temp))

How to accept graph from input file

2 Answers2