Эффективное хранение графов: матрицы смежности

[Rsa97]

Не говоря уже о том, что вы изобрели велосипед, вы ещё и неправильно его изобрели.
Добавим по вашей формуле ребро (а вовсе не вершину!) 3-4
index = (3 * 3 + 4) / 8 = 13 / 8 = 1
mask = 128 >> ((3 * 3 + 4) % 8) = 128 >> (13 % 8) = 128 >> 5 = 4
Теперь добавим ребро 4-1
index = (4 * 3 + 1) / 8 = 13 / 8 = 1
mask = 128 >> ((4 * 3 + 1) % 8) = 128 >> (13 % 8) = 128 >> 5 = 4
Опаньки. Это же одно и то же ребро!
Проверять надо формулы перед публикацией.
Вовсе не случайно в программировании используют индексы, начинающиеся с нуля.
Если взять граф из N вершин, пронумерованных с единицы, то правильная формула для ребра X->Y примет вид:
bit = (X — 1) * N + (Y — 1)
index = bit / 8
mask = 1 << (bit % 8)
Да, и использование сдвига единицы, а не магической 128, это тоже общепринятая практика, так как биты нумеруются с младшего (нулевого).

[murloteg]

Вы правы, я ошибся в примере. Спасибо, что указали на это. Про магическую константу учту :)

[randomsimplenumber]

Если уж речь о хранении достаточно сложного объекта, и пишется какой то код на С(++), стоило бы оформить это в виде структуры или класса.

[Tiriet]

Есть у математиков такое понятие, как Sparse matrix- разреженные матрицы. Матрица, большая часть элементов которой- нули. Они очень распространены в задачах вычислительной математики и численных методах математической физики, в частности, любая практически задача, решаемая методом конечных элементов (МКЭ) в итоге сводится к разреженной матрице и какой-то операции с ней (как правило- итерационного решения, которое в свою очередь, сводится к многократному перемножению таких матриц). Мат-аппарат этого дела довольно хорошо развит, а то, что изложили Вы- очень напоминает "портрет матрицы".

У меня складывается ощущение, что велосипедостроение получило какой-то бонус в небесной канцелярии и стало массовым увлечением на хабре.

[aleex]

Да, это распространенная вещь для задач с размерностью выше единицы. И они реализованы например в Eigen, MTL, данные в соответствующем формате(CSR или CSC) идут на вход функций Intel MKL.

[wataru]

Вся статья заменяется одним предлождением: "матрица смежности состоит из чисел 0 и 1. Их можно хранить в битах большого массива". Или вообще одной фразой "битовое сжатие".

[VladimirKryukov]

Спасибо