Я хочу создать огромный взвешенный неориентированный граф, представленный огромной матрицей смежности AJM. Таким образом, для цикла по I и J,Порог огромной матрицы, чтобы избежать чрезмерного использования памяти, C++
AJM [I] [J] = AJM [J] [I]
AJM [I] [I] = 0
весы генерируются как случайные двойные числа в интервале, скажем [0,01, 10,00]. Если у меня есть 10k вершин, то матрица будет 10k на 10k с записями двойного типа, что является огромным куском в памяти, если я его сохраню.
Теперь я хочу установить пороговое значение E для требуемого числа ребер и игнорировать все ребра с весом, большим некоторого порога T (T определяется E, E определяется пользователем), просто сохраните наименьший E края с весом под T в векторе для последующего использования. Не могли бы вы дать мне некоторое предложение, как эффективно это сделать? Лучше всего избегать любого хранения всей матрицы смежности, просто используйте поточную структуру. Поэтому мне интересно, как мне сгенерировать матрицу и сделать порог?
Я думаю, что файл для записи и чтения нужен, не так ли?
Один подход был бы, после того, как какой-то манипуляции с файлом, я установил порог Е и выполните следующие действия:
Я прочитал элемент из матрицы один за другим, так что я не читаю в целом (можете ли вы показать некоторые строки кода C++ для достижения этого?) и вставить свой вес в мини-кучу, сохранить соответствующий вектор края в векторе. Я останавливаюсь, когда размер кучи достигает E, так что вектор краевых индексов - это то, что я хочу.
Как вы считаете, это правильный способ сделать это? Любые другие предложения? Pls указывает на любую ошибку, которую я могу иметь здесь. Спасибо огромное!
Это * звучит * как * редкая матрица *, облегчит ваши проблемы с памятью, хотя в худшем случае все еще будет потребляться лодка памяти. то, как вы реализуете разреженность, является отдельной проблемой. – WhozCraig
Насколько случайны здесь случайные? Вы можете использовать PRNG, для которого вам нужно будет только сохранить начальное значение. Возможно, N значений семян. – mvds
Проблема в том, что это может привести к отключению графиков? Вам нужно сохранить исходный граф, или это какой-то временный? –