Add support for reading (and writing) .graph files

[ardasener]

SparseBase should provide Readers for METIS GRAPH Files. This is quite a flexible format that can contain both vertex and edge weights.

The code snippet below is one I used in another project and reads the file into a CSR format. Note that this code was not of critical importance so it isn't really optimized. It only supports vertex weights. The x variable on the first line should be checked for values other than 10 and the reader should act accordingly. Here are the possible values and their meanings:

%  FMT has the following meanings:
%    0  the graph has no weights (in this case, you can omit FMT);
%    1  the graph has edge weights;
%   10  the graph has vertex weights;
%   11  the graph has both edge and vertex weights.

int new_reader_read_graph(const char* input_file, vtx_type* nvtxs, adj_type** xadj, vtx_type** adj, wgt_type** vwgt, wgt_type** adjwgt){

	vtx_type n;
	adj_type m;

	ifstream ifs(input_file);

	cout << "Reading graph from: " << input_file << endl;

	string line;
	bool first_line = true;
	size_t last_index = 0;
	vtx_type u = 0;
	while(getline(ifs,line)){
		
		if(line[0] == '%'){
			continue;
		}

		stringstream ss(line);

		if(first_line){
			
			int x;
			ss >> n >> m >> x;
			m *= 2;
			cout << "N=" << n << " M=" << m << endl;
			if(x != 10){
				cout << "File must have vertex weights" << endl;
				return 2;
			}
			first_line = false;

			*xadj = new adj_type[n+1];
			(*xadj)[0] = 0;
			*adj = new vtx_type[m];
			*vwgt = new wgt_type[n];
			
		} else {
			wgt_type w;
			ss >> w;
			vtx_type v;
			while(ss >> v){
				(*adj)[last_index++] = v-1;					
			}
			(*xadj)[u+1] = last_index;
			(*vwgt)[u] = w;
			u++;
		}
	}

	cout << "Done reading graph" << endl;

	*nvtxs = n;

	return 1;
}

[ardasener]

The main issue right now is that this file format can contain vertex weights which the current Format system won't represent. And since this file format is designed to be used for graphs, it is logical to return Graph objects from the reader. We do have a Graph class but it hasn't been updated in a while. So we should probably delay this until we update that.

[AmroAlJundi]

Add a reader for .graph metis format

[ardasener]

Here is a library with a .graph reader: https://github.com/dlasalle/wildriver. Looks like it hasn't been updated in a while and I had trouble with it in another project. So I suggest using it as a reference, not adding it as a dependency.