Taking input from a file in C++

Question

I'm trying to implement the Prim's algorithm. I am taking the input from a file as follows.

3 3   // Number of vertices and edges
1 2 3 // edge 1 edge 2 cost
2 3 4 // edge 2 edge 3 cost
1 3 4 // edge 1 edge 3 cost

I create a cost matrix as follows. Initially, every weight in the cost matrix is infinity (9999 in this case).

for(i = 0; i < n; i++)
{
    for( j = 0; j < n; j++)
    {
        cost[i][j] = 9999;
    }
}

Now, i need to update the weights of the cost matrix by reading the weights from the file. So, I am reading the file as follows.

ifstream fin;
fin.open("input.txt",ios::in);
fin >> n; //nodes
fin >> e; //edges
while(fin)
{
    fin>>a>>b>>w;
    cost[a-1][b-1] =cost[b-1][a-1]= w;   
}
fin.close();

So, a and b are the edges and w is the weight for that edge. So, Suppose I have edge(1,2) and its weight is 3. So, my cost matrix cost[1][2] and cost[2][1] should update to 3. I am not able to figure out how I should update the cost matrix using file operations.

To put it again, I have a text file like the file I mentioned above. The first line of the file contains number of vertices in edges. I want to read the vertices in a variable v and edges in variable e. Then, I have an initial cost matrix cost[i][i] where all values are infinity. I want to update the edges in this cost matrix from the file. So, i will read the second line from the file and update the cost[1][2] = 3. I have no idea how to do this still.

Here's the full program I have now:

#include<iostream>
#include<fstream>
using namespace std;

int n,e,a,b,w;
int **cost = new int*[n];

void prim()
{
int i,j,k,l,x,nr[10],temp,min_cost=0;
int **tree = new int*[n];

for(i = 0; i < n; i++)
tree[i]=new int[n];

/* For first smallest edge */
temp=cost[0][0];
for(i=0;i< n;i++)
 {
 for(j=0;j< n;j++)
 {
    if(temp>cost[i][j])
    {
    temp=cost[i][j];
    k=i;
    l=j;
    }
 }
}
/* Now we have fist smallest edge in graph */
tree[0][0]=k;
tree[0][1]=l;
tree[0][2]=temp;
min_cost=temp;

/* Now we have to find min dis of each 
vertex from either k or l
 by initialising nr[] array 
 */

 for(i=0;i< n;i++)
  {
   if(cost[i][k]< cost[i][l])
    nr[i]=k;
   else
    nr[i]=l;
   }
  /* To indicate visited vertex initialise nr[] for them to 100 */
  nr[k]=100;
  nr[l]=100;
  /* Now find out remaining n-2 edges */
  temp=99;
  for(i=1;i< n-1;i++)
   {
    for(j=0;j< n;j++)
     {
      if(nr[j]!=100 && cost[j][nr[j]] < temp)
       {
       temp=cost[j][nr[j]];
       x=j;
       }
   }
  /* Now i have got next vertex */
  tree[i][0]=x;
  tree[i][1]=nr[x];
  tree[i][2]=cost[x][nr[x]];
  min_cost=min_cost+cost[x][nr[x]];
  nr[x]=100;

   /* Now find if x is nearest to any vertex 
   than its previous near value */

for(j=0;j< n;j++)
{
if(nr[j]!=100 && cost[j][nr[j]] > cost[j][x])
     nr[j]=x;
}
temp=9999;
}
/* Now i have the answer, just going to print it */
cout<<"\n The minimum spanning tree is:"<<endl;
 for(i=0;i< n-1;i++)
{
for(j=0;j< 3;j++)
       cout<<tree[i][j];
cout<<endl;
}

 cout<<"\nMinimum cost:";
 cout<<min_cost;
}


 int main()
 {
  int i,j;

   for(i = 0; i < n; i++)
    cost[i]=new int[n];


for(i = 0; i < n; i++)
    {
    for( j = 0; j < n; j++)
        {
        cost[i][j] = 9999;
        }
    }

    ifstream fin;
     fin.open("input.txt",ios::in);

//cout<<n<<e;
     fin>>n>>e;

     while(fin>>a>>b>>w)
     {

    cost[a-1][b-1] = w;


      }
fin.close();
    prim();
    system("pause");
  }

Start with this: [Why is iostream::eof inside a loop condition considered wrong?](http://stackoverflow.com/questions/5605125/why-is-iostreameof-inside-a-loop-condition-considered-wrong) — WhozCraig, Oct 18 '13 at 05:09
nope. Thats only slightly better than checking for eof. Let me ask you, How do you know the extraction of `a`, `b`, and `w` *worked* ?? (hint: you don't). Try `while (fin >> a >> b >> w)` and remove the first line in the while-block. I leave all the other places you're not checking for stream validation to you. (I count at least three more in that snippet alone. — WhozCraig, Oct 18 '13 at 05:25
Okay I got it. So similarly, I will need to check for n and e too, right? — user2893084, Oct 18 '13 at 05:32
Yes. Further, you can construct the file directly from the declaration, `ifstream fin("input.txt");` if (`fin >> n >> e) { while... }` you get the idea. — WhozCraig, Oct 18 '13 at 05:51
I am sorry, but I still don't understand how I should tackle this. A more detailed explanation with an example will be much apreciated. — user2893084, Oct 18 '13 at 15:32
There are so many other questions like these (unsurprisingly, text input happens quite often). If you just search for _"[c++] ifstream"_ I bet you can see so many examples that you won't have any questions left. A random example from today: [How can I test for reflexive, symmetric, or transitive](http://stackoverflow.com/questions/19415372/how-can-i-test-for-reflexive-symmetric-or-transitive/19415543#19415543) — sehe, Oct 18 '13 at 15:40
So i can successfully read the number of edges and vertices in line 1. I dont understand how to get to line 2 and loop through all the remaining lines to update my cost matrix. This is the only thing left in my code. My rest of the code works perfectly fine. — user2893084, Oct 18 '13 at 16:02
I tried doing this. `ifstream fin; fin.open("input.txt",ios::in); //cout<>v>>e; while(fin>>a>>b>>w) { cost[a-1][b-1] = w; } fin.close();` However, I still get an unhandled exception at the line cost[a-1][b-1] = w. Obviously, I am not reading it right to update the matrix. — user2893084, Oct 18 '13 at 16:08
I'm going to all-but guaranteed your matrices are not sized. Ie. there is a reason for those first two values. if you think this problem is trivial, I assure you it *is*, but you need to know how to use `std::vector<>` and stream input validation. If I get some time, I'll post something. — WhozCraig, Oct 18 '13 at 17:37
@WhozCraig I've just posted two alternatives. I realize that I went the adjacency list approach, and the question mentions cost-matrix... Still my code should tell the OP how to do things regarding stream input. — sehe, Oct 18 '13 at 18:55

sehe · Accepted Answer · 2013-10-18T22:07:13.370

Update

An adaptation of the read code added to the OP later:

#include<vector>

typedef int Cost;
typedef std::vector<std::vector<Cost> > Matrix;
typedef Matrix::value_type Row;

Not change prim to take the cost matrix by ref:

void prim(Matrix const& cost)

And reading becomes:

int main()
{
    ifstream fin;
    fin.open("input.txt", ios::in);
    unsigned n, e;

    if (fin >> n >> e)
    {
        Matrix cost(n, Row(n, 9999));

        unsigned a, b;
        Cost w;
        while(fin >> a >> b >> w)
        {
            cost[a - 1][b - 1] = w;
        }
        prim(cost);
    }
    fin.close();
}

You see,

avoid manual memory management
do error checking

Old Answers:

Assuming a datastructure of:

typedef unsigned Vertex;
typedef std::pair<Vertex, Vertex> Edge;
typedef double Cost;

typedef std::map<Edge, Cost> Graph;
typedef Graph::value_type Entry;

Here is a pretty clean version of readGraph using just standard library facilities:

Graph readGraph(std::istream& is)
{
    size_t vertices, edges;

    if (is >> vertices >> edges)
    {
        is.ignore(1024, '\n'); // assume not overly long lines

        Graph graph;
        while (edges--)
        {
            std::string line;
            if (is && std::getline(is, line))
            {
                Vertex from, to;
                Cost cost;

                std::istringstream line_stream(line);

                if (line_stream >> from >> to >> cost)
                {
                    if (!(graph.insert({ { from, to }, cost }).second))
                        throw std::runtime_error("Duplicate edge");
                } else
                {
                    is.setstate(is.rdstate() | std::ios::badbit);
                }
            }
        }

        if (!is.bad())
            return graph;
    }

    throw std::runtime_error("Invalid input");
}

See it Live On Coliru

Graph const graph = readGraph(std::cin);

for (auto& entry: graph)
{
    Edge const& edge = ::get_edge(entry);
    Cost        cost = ::get_cost(entry);

    std::cout << "Edge(" << get_source(edge) << ", " << get_destination(edge) << "): cost " << cost << "\n";
}

Outputs:

Edge(1, 2): cost 3
Edge(1, 3): cost 4
Edge(2, 3): cost 4

Alternative

Using Boost Spirit to do the parsing. This is a drop-in replacement and the data structures and main() have been complete un-altered:

Graph readGraph(std::istream& is)
{
    typedef boost::spirit::istream_iterator It;
    is.unsetf(std::ios::skipws);
    It f(is), l;

    size_t vertices = 0, edges = 0;
    Graph graph;

    using namespace boost::spirit::qi;
    static const rule<It, Edge(), blank_type> edge_rule = uint_ >> uint_;

    bool ok = phrase_parse(f, l, 
            uint_ >> uint_ >> eol >>
            (edge_rule >> double_) % eol >> (*eol > eoi),
            blank,
            vertices, edges, graph);

    assert(ok && f==l && graph.size() == edges);

    return graph;
}

See it Live on Coliru too.

Full code for reference

(in case Coliru ceases to exist):

#include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <sstream>
#include <map>
#include <cassert>
#include <stdexcept>

typedef unsigned Vertex;
typedef std::pair<Vertex, Vertex> Edge;
typedef double Cost;

typedef std::map<Edge, Cost> Graph;
typedef Graph::value_type Entry;

Graph readGraph(std::istream& is)
{
    size_t vertices, edges;

    if (is >> vertices >> edges)
    {
        is.ignore(1024, '\n'); // assume not overly long lines

        Graph graph;
        while (edges--)
        {
            std::string line;
            if (is && std::getline(is, line))
            {
                Vertex from, to;
                Cost cost;

                std::istringstream line_stream(line);

                if (line_stream >> from >> to >> cost)
                {
                    if (!(graph.insert({ { from, to }, cost }).second))
                        throw std::runtime_error("Duplicate edge");
                } else
                {
                    is.setstate(is.rdstate() | std::ios::badbit);
                }
            }
        }

        if (!is.bad())
            return graph;
    }

    throw std::runtime_error("Invalid input");
}

static inline Vertex      get_source     (Edge  const& e) { return e.first;  }
static inline Vertex      get_destination(Edge  const& e) { return e.second; }
static inline Edge const& get_edge       (Entry const& e) { return e.first;  }
static inline double      get_cost       (Entry const& e) { return e.second; }

static inline Vertex&     get_source     (Edge       & e) { return e.first;  }
static inline Vertex&     get_destination(Edge       & e) { return e.second; }
static inline double&     get_cost       (Entry      & e) { return e.second; }

int main()
{
    Graph const graph = readGraph(std::cin);

    for (auto& entry: graph)
    {
        Edge const& edge = ::get_edge(entry);
        Cost        cost = ::get_cost(entry);

        std::cout << "Edge(" << get_source(edge) << ", " << get_destination(edge) << "): cost " << cost << "\n";
    }
}

+1 (and i wish I could up-vote this again and again...) The initializer lists on the graph insertion are an especially nice touch, along with the duplicate-edge check via the returned iterator,bool pair. — WhozCraig, Oct 18 '13 at 18:57
@WhozCraig Good point, in that respect, the std-library version is more full-featured than the Spirit version — sehe, Oct 18 '13 at 19:04
Thank you so much. That was really helpful. Suppose I choose not to use vectors, what are my alternatives then? I will post my entire code so that it becomes easier. My code works perfectly if I take the input from the user from the console. — user2893084, Oct 18 '13 at 20:39
@user2893084 What is the question left, if your code works perfectly (by the way my samples also take the input from the "console" (stdin)) — sehe, Oct 18 '13 at 21:01
`>>` in C++ has 3 meanings: bitwise shift-right, reading from an ostream, and an upvote to sehe for yet another Boost.Spirit answer ;-) — TemplateRex, Oct 18 '13 at 21:49
@user2893084 Just added a "sane" approach. Your code was failing because of UB, reading from a file works fine like this. — sehe, Oct 18 '13 at 22:08

Taking input from a file in C++

1 Answers1

Update

Old Answers:

Alternative

Full code for reference