After deciding that adjacency matrix won't work out for 80513 nodes and 5899882 edges I've decided to apply adjacency list. It's my first implementation of adjacency list and basically I've decided to apply vector of vectors method.
Таким образом, например, vectorOfVectors[5] будет содержать соседей для включения соседнего узла 5. Набор данных, который я использую, можно найти здесь
В настоящее время я написал этот код, и он работает без ошибок, однако на моем компьютере это занимает 26 секунд (i5 2.4 с 6 ГБ оперативной памяти, работающая под управлением Win7). Мне было интересно, можно ли улучшить мой код, чтобы уменьшить скорость выделения.
PS: я использую библиотеку fstream и читаю из файла .csv.
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
using namespace std;
int main()
{
ifstream file("edges.csv");
string word="",data="";
getline(file,word);
int arrTemp[3];
int numberOfNodes=atoi(word.c_str());
vector<int>temp;
vector< vector<int> >adjacencyList;
for(int i=0;i<numberOfNodes;i++)
{
adjacencyList.push_back(temp);
}
while(file.good() && getline(file,word))
{
//cout<<word<<endl;
if(word.size()>0)
{
for(int i=0;i<3;i++)
{
int cutFrom=word.find_first_of(',');
arrTemp[i]=atoi(word.substr(0,cutFrom).c_str());
word=word.substr(cutFrom+1,word.length());
}
//cout<<arrTemp[0]<<" "<<arrTemp[1]<<endl;
adjacencyList[arrTemp[0]-1].push_back(arrTemp[1]-1);
}
else
break;
}
cout<<"Vector size:"<<adjacencyList[1].size()<<endl;
return 0;
}
