make_hypercube

[kuvshinovdr]

1. Обновить свою ветку по main.
2. В директории source создать файл make_hypercube.cpp
3. В этом файле в пространстве имён ogxx определить функцию make_hypercube_one_direction с заголовком вида:

   void make_hypercube_one_direction(Graph_view& gv, Index_iterator_uptr vertices);

   Эта функция должна создавать гиперкуб на вершинах, перечисляемых vertices. Число этих вершин должно быть степенью двойки. Если это не степень двойки, бросать исключение std::invalid_argument. Показатель степени двойки определяет размерность гиперкуба и количество рёбер добавляемых для каждой вершины.

Примеры по размерности:

0. Одна вершина -- нульмерный куб, рёбра не добавляются.
1. Две вершины -- одномерный куб = отрезок, добавляем одно ребро, соединяющее эти вершины: (0, 1) -> 0-1.
2. Четыре вершины -- двумерный куб = квадрат, добавляем четыре ребра, соединяющие эти вершины: (0, 1, 2, 3) -> 0-1, 0-2, 1-3, 2-3.
3. Восемь вершин -- трёхмерный куб, добавляем 12 рёбер: (0, 1, 2, 3, 4, 5, 6, 7) -> 0-1, 0-2, 0-4, 1-3, 1-5, 2-3, 2-6, 3-7, 4-5, 4-6, 5-7, 6-7.
4. Шестнадцать вершин -- четырёхмерный куб = тессеракт, добавляем 32 ребра (перечислять не буду).

Вообще, в гиперкубе размерности n число вершин $V(n) = 2^n$, число рёбер $E(n) = 2E(n-1) + V(n-1)$, $E(0) = 0$, т.е. $E(n) = n\cdot 2^{n-1}$.

Теперь о том, как генерировать рёбра:

1. Сохранить индексы из vertices в вектор. Этот вектор позволяет далее работать с индексами вершин от 0 до V-1, где V -- общее число вершин, V = $2^n$. При вставке рёбер мы подставляем эти индексы в вектор и извлекаем "настоящие вершины".
2. Перебираем все индексы от 0 до V-1.
3. Для каждого индекса как для последовательности бит перебираем биты с номерами от 0 до n-1 и меняем их по очереди на противоположные. Это даёт нам индексы соседних вершин, которые надо соединять рёбрами.
4. Чтобы не дублировать рёбра, добавляем u-v только для u < v.

[ViktoriaZaykina]

подскажите пожалуйста, что такое u и v в 4ом пункте?

[kuvshinovdr]

Вы всё-таки делаете эту задачу? Она, в принципе, не сложная.

что такое u и v в 4ом пункте

Это просто номера двух вершин, которые мы соединяем ребром. Если оказалось, нам достаточно рассматривать только такие пары, что u < v.

[ViktoriaZaykina]

да, решила сделать эту хорошо, спасибо

[ViktoriaZaykina]

код выложила, только без теста

[kuvshinovdr]

После этого цикла:

        for (Scalar_index item; vertices->next(item);) {
            ++count_of_vertices;
        }

индексы вершин уже не будут доступны, поскольку vertices->next будет всегда возвращать false. Лучше их тогда сохранить в вектор сразу, а потом уже брать его размер.

[kuvshinovdr]

Здесь должно быть отрицание условия:

        if (count_of_vertices > 0 && (count_of_vertices & (count_of_vertices - 1)) == 0) {
            throw std::invalid_argument("make_hypercube_one_direction: count of vertices != 2^n.");
        }

[kuvshinovdr]

Зачем нам вектор masks

        std::vector<Scalar_index> masks;
        for (Scalar_index i = 1, j = 0; j < n; i = i << 1, ++j) {
            masks.push_back(i);
        }

если masks[j] можно получить как Scalar_index(1) << j?

[ViktoriaZaykina]

сделала правки в соответствии с замечаниями

[kuvshinovdr]

Хорошо, задание засчитано, баллы выставлены в таблицу. Пока что в main я код не добавляю и этот issue не закрываю по сторонним причинам.