little_tools/graph_format/dimacs2metis.cpp

// =====================================================================================
//
//       Filename:  dimacs2metis.cpp
//
//    Description:  convert dimacs graph to metis format
//
//        Version:  1.0
//        Created:  2017年 12月 28日 星期四 07:03:07 -00
//       Revision:  none
//       Compiler:  g++
//
//         Author:  Jinkun Lin, jkunlin@gmail.com
//   Organization:  School of EECS, Peking University
//
// =====================================================================================
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int vertex_count = 0, edge_count = 0;
vector<vector<int>> adjacency_list;
vector<int> vertex_weight;
// read graph file into adjacency_list
void fast_read(string file_name) {/*{{{*/
	ifstream in_file(file_name);
	if (!in_file) {
		cout << "in_file error" << endl;
		exit(1);
	}
	in_file.seekg (0, in_file.end);
	size_t file_len = in_file.tellg();
	in_file.seekg (0, in_file.beg);
	char *data = new char [file_len];

	in_file.read(data, file_len);
	in_file.close();

	//skip comments
	char *pos = data;
	while (*pos == '%') {
		while(*(pos++) != '\n');
	}

	//read vertex_count
	while (*pos < '0' || *pos > '9') {
		++pos;
	}
	while (*pos != ' ') {
		vertex_count = vertex_count * 10 +  *pos - '0';
		++pos;
	}
	//read edge_count
	while (*pos < '0' || *pos > '9') {
		++pos;
	}
	while (*pos >= '0' && *pos <= '9') {
		edge_count = edge_count * 10 +  *pos - '0';
		++pos;
	}

	//read vertex_weight
	vertex_weight.resize(vertex_count + 1);
	int v,w;
	for(vector<vector<int>>::size_type i=1; i<vertex_weight.size(); ++i){
		v = w = 0;
		//read vertex
		while (*pos < '0' || *pos > '9') {
			++pos;
		}
		while (*pos != ' ') {
			v = v * 10 +  *pos - '0';
			++pos;
		}
		//read weight
		while (*pos < '0' || *pos > '9') {
			++pos;
		}
		while (*pos >= '0' && *pos <= '9') {
			w = w * 10 +  *pos - '0';
			++pos;
		}
		vertex_weight[v]=w;
	}

	//read adjacency_list
	adjacency_list.resize(vertex_count + 1);

	vector<int> vertex_degree(vertex_count + 1, 0);
	char *stash_pos = pos;
	int v1, v2;
	for (int i = 0; i < edge_count; ++i) {
		v1 = v2 = 0;
		//read v1
		while (*pos < '0' || *pos > '9') {
			++pos;
		}
		while (*pos != ' ') {
			v1 = v1 * 10 +  *pos - '0';
			++pos;
		}
		//read v2
		while (*pos < '0' || *pos > '9') {
			++pos;
		}
		while (*pos >= '0' && *pos <= '9') {
			v2 = v2 * 10 +  *pos - '0';
			++pos;
		}
		vertex_degree[v1]++;
		vertex_degree[v2]++;
	}
	for (size_t v = 1; v < adjacency_list.size(); ++v) {
		adjacency_list[v].reserve(vertex_degree[v]);
	}
	pos = stash_pos;
	for (int i = 0; i < edge_count; ++i) {
		v1 = v2 = 0;
		//read v1
		while (*pos < '0' || *pos > '9') {
			++pos;
		}
		while (*pos != ' ') {
			v1 = v1 * 10 +  *pos - '0';
			++pos;
		}
		//read weight
		while (*pos < '0' || *pos > '9') {
			++pos;
		}
		while (*pos >= '0' && *pos <= '9') {
			v2 = v2 * 10 +  *pos - '0';
			++pos;
		}
		adjacency_list[v1].push_back(v2);
		adjacency_list[v2].push_back(v1);
	}
	delete[] data;
}/*}}}*/

void convert(string graph_name) {
	ofstream out_graph(graph_name);
	if (!out_graph) {
		std::cout << "outfile error" << std::endl;
		abort();
	}
	out_graph << vertex_count << ' ' << edge_count << endl;
	for (size_t v = 1; v < adjacency_list.size(); ++v) {
		out_graph << adjacency_list[v][0];
		for (size_t i = 1; i < adjacency_list[v].size(); ++i) {
			int u = adjacency_list[v][i];	
			out_graph << ' ' << u;
		}
		out_graph << std::endl;
	}

	ofstream out_weight(graph_name + ".weights");
	if (!out_weight) {
		std::cout << "weights file error" << std::endl;
		abort();
	}
	
	// offset = -1
	for (int v = 0; v < vertex_count; ++v) {
		out_weight << v << ' ' << vertex_weight[v + 1] << std::endl;
	}

	out_graph.close();
	out_weight.close();
}
int main(int argc, char const *argv[]) {
	if (argc != 2) {
		std::cout << "usage" << std::endl;
		return 1;
	}

	string in_filename = argv[1];
	fast_read(in_filename);
	
	string graph_name;
	size_t begin_index = 0;
	if ((begin_index = in_filename.find_last_of('/')) != string::npos) {
		graph_name = in_filename.substr(begin_index + 1, in_filename.size() - 5 - begin_index - 1);
	}
	else {
		graph_name = in_filename.substr(0, in_filename.size() -5);
	}
	graph_name += ".graph";

	convert(graph_name);
	return 0;
}