Сохранение наборов из файла C++

Question

Скажем, у меня есть .txt файл с содержимым

5 
0 1 
1 2 
2 4 
3 2 
4 0 
1 3 

Первое число означает число наборов в файле (NxN матрица). Остальные являются множествами простого графа.

Мне интересно, какой лучший способ хранения наборов данных (представлять точки для простого графика) из файла будет. Глядя на создание и отображение матрицы смежности с этими данными.

например:

0 1 0 0 1 
1 0 1 1 0 
0 1 0 1 1 
0 1 1 0 0 
1 0 1 1 1 

Я хочу, чтобы вытащить их из файла, сохранять их (как-то), что я тогда в состоянии сравнить их друг с другом для примыкания.

Я хочу, чтобы иметь возможность читать два номера в отдельности, поэтому, если я вижу набор 4 0, я знаю, что 4 находится рядом с 0 и наоборот. Я также хочу, чтобы иметь возможность просматривать каждый набор в графе один раз на матричную строку (4 & 0 смежны, что еще находится рядом с 4)

Как вы храните эти данные, чтобы наилучшим образом удовлетворить мои потребности? Стек? Массив? Вектор?

Приветствие

Answer 1

Для хранения пары вершин, вы можете использовать std::pair:

vector<pair<int, int> > vertices; 
while(cin >> a >> b){ 
    vertices.push_back(make_pair(a, b)); 
} 

После того, как у вас есть вершины, сохраненные в векторе пара, вы можете использовать 2-d matrix для хранения списков смежности , Если одна из пар равна (1,2), тогда вы инициализируете матрицу по индексам (1,2), а также (2,1) (так как график, как представляется, не направляется) равным 1, что указывает на то, что у них общий ребро, иначе инициализируйте этот индекс равным 0.

int **adjacency = new int *[n]; 
for(int i = 0;i < n;i++) 
    adjacency = new int[n]; 
memset(adjacency, 0, sizeof(adjacency)); 
vector<pair<int, int> >::iterator it = vertices.begin(); 
while(it != vertices.end()){ 
    adjacency[it -> first][it -> second] = 1; 
    adjacency[it -> second][it -> first] = 1; 
} 

Answer 2

Ах, черт возьми. С

std::map<unsigned, std::vector<unsigned>> sparse; 

sparse является отображение номера узла в список соседних узлов. Я пошел с unsigned, потому что большинство матриц на основе массивов ненавидят отрицательные индексы. Это не проблема с этим макетом, но кажется, что нужно создать матрицу смежности для высокоскоростного поиска. Эта структура меньше, предполагая разреженную матрицу, но она sloooooooow по сравнению с массивом логических значений. Если у вас достаточно ОЗУ, используйте его. Вот для чего это.

unsigned a,b; 
while(in >> a >> b) 
{ 
    sparse[a].push_back(b); 
    sparse[b].push_back(a); 
} 

a и b являются смежными, так что они добавляются в ряд друг друга. sparse[nodeNum] возвращает ссылку на вектор nodeNum, поэтому есть список соседних узлов. Например:

std::cout << "4 is adjacent to "; 
for(unsigned val: sparse[4]) 
{ 
    std::cout << val << " "; 
} 

Распечатайте все соседние узлы 4, 2 и 0 в примере OP.

Теперь, когда вы все прочитали, вы можете легко определить размеры (если вы еще не записали наибольшее число, просматриваемое при чтении файла), выделите матрицу и загрузите ее из разреженного малоимущего человека описанной выше.