В чем проблема в коде работы с графом?

Question

[Xiran]

Задачу более простого типа я решил с помощью: Что не так с кодом, работающим с графом?, и эту не сам осилил.
Алгоритм такой же:
Есть массив, в котором хранятся числовые значения вершин.
В начале сохраняем этот массив в копию.
Если значение вершины i в копии положительное, то увеличиваем значения всех смежных вершин в исходном массиве на
значение вершины i в копии:

Код

using Graph = std::vector<std::vector<std::size_t>>;       
using ValuesTable = std::array<std::ptrdiff_t, GRAPH_SIZE>;
                                                           
void makeStep(Graph &graph, ValuesTable &table) {          
    ValuesTable stepLocalTable { table };                  
                                                           
    for (std::size_t i { 0 }; i < GRAPH_SIZE; i++)         
        for (const auto &adj : graph[i])                   
            if (stepLocalTable[i] > 0)                     
                table[adj] += stepLocalTable[i];           
}

Дан граф:

Нужно определить, через сколько повторений алгоритма значения всех вершин станут положительными.

Весь код

#include <cstddef>
#include <limits>
#include <algorithm>
#include <array>
#include <vector>
#include <iostream>

constexpr std::size_t GRAPH_SIZE { 7 };

using Graph = std::vector<std::vector<std::size_t>>;
using ValuesTable = std::array<std::ptrdiff_t, GRAPH_SIZE>;

void makeStep(Graph &graph, ValuesTable &table) {
    ValuesTable stepLocalTable { table };

    for (std::size_t i { 0 }; i < GRAPH_SIZE; i++)
        for (const auto &adj : graph[i])
            if (stepLocalTable[i] > 0)
                table[adj] += stepLocalTable[i];
}

int main() {
    Graph graph {
        { 1, 2, 6 }, { 0, 3 }, { 0, 4 }, { 1, 5 }, { 2, 6, 5 }, { 3, 4 }
    };

    ValuesTable table {
        1, -3, -5, -50, -30, -10, -250
    };

    for (std::size_t k { 0 }; k < std::numeric_limits<std::size_t>::max(); k++) {
        makeStep(graph, table);

        if (std::all_of(table.begin(), table.end(), [](auto i) { return i > 0; })) {
            std::cout << k;

            break;
        }
    }
}

Но он почему-то исполняется бесконечно. Где я не не углядел?

Comments

[Wataru]

Зачем вам значения хранить в типе ptrdiff?!

[Xiran]

Wataru, странная привычка, да и к тому же я не знаю точную платформу, боюсь переполненения

[Xiran]

Может, это и никак не влияет

[Wataru]

Xiran, Не влиет, конечно, но если вам нужна переносимость, то используйте, например int32_t. Так-то размер ptrdiff гарантируется быть хотя бы 17 бит, а сколько их там на другой платформе - вы знать не можете.

[Xiran]

Wataru, спасибо, я почему-то думал, что stdint типы не гарантируют размер, несмотря на названия

[Wataru]

Xiran, Все типы что про размер гарантируют. int хотя бы 16 бит, char хотя бы 8. stdint-овые гарантируют что-то логичное их названиям.

Answer 1

[Wataru]

Ошибка в том, что у вас граф криво задан. У вас там ровно 6 списков. А размер графа - 7. Поэтому в MakeStep вы обращаетесь к graph[6], а это undefined behavior. А там непонятно, что происходит. Может вы таблицу портите каким-то значениями и никогда положительного значения не получаете. Скорее всего корраптите память через обращение к мусорным adj в std::array (который на стеке лежит) и получаете мусор в каких-то локальных переменных.

Comments

[Xiran]

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

[Xiran]

Большое спасибо за помощь всем

Answer 2

[mayton2019]

Зачем делать безсмысленный makeStep? Пускай он возвращает булево значение.

boolean makeStep(Graph &graph, ValuesTable &table) { .... }

Не было отрицательных свойств среди вершин - значит пускай вернет true.
Тогда будет стоп алгоритма. И не надо будет
делать дополнительных пере-расчетов.

Comments

[Xiran]

#include <cstddef>
#include <limits>
#include <algorithm>
#include <array>
#include <vector>
#include <iostream>

constexpr std::size_t GRAPH_SIZE { 7 };

using Graph = std::vector<std::vector<std::size_t>>;
using ValuesTable = std::array<std::ptrdiff_t, GRAPH_SIZE>;

bool makeStep(Graph &graph, ValuesTable &table) {
    ValuesTable stepLocalTable { table };

    bool result { true };

    for (std::size_t i { 0 }; i < GRAPH_SIZE; i++) {
        if (stepLocalTable[i] < 0) {
            result = false;

            continue;
        }
  
        for (const auto &adj : graph[i])
            table[adj] += stepLocalTable[i];
    }

    return result;
}

int main() {
    Graph graph {
        { 1, 2, 6 }, { 0, 3 }, { 0, 4 }, { 1, 5 }, { 2, 6, 5 }, { 3, 4 }
    };

    ValuesTable table {
        1, -3, -5, -50, -30, -10, -250
    };

    std::size_t k { 0 };

    for (; !makeStep(graph, table); k++)

    std::cout << k;
}

Останавливается, но выводит что-то непонятное

[Xiran]

проверю еще раз список смежности

[mayton2019]

bool result { true };
Ты наверное прикалываешся так писать? Тебе лень поставить 1 знак равно вместо двух скобочек?

[Xiran]

mayton2019, единообразие в коде. Если это раздражает, буду писать =

[mayton2019]

Xiran, пиши меньше букв. И дело не в единообразии а в понимании для чего ты это пишешь.

Если тебе нужен трекинг успешной сходимости твоего процесса или алгортма - то заведи
переменную которая характеризует близость к успеху. И просто печатаей ее на экран
при каждой итерации.

Я всегда печатаю счетчики когда мне что-то непонятно. После этого очень-очень быстро все становится
понятно.

[Xiran]

mayton2019, а я просто дебажу, или пишу тесты. Но, действительно, какие-то промежуточные результаты тоже помогают. Но я пришел к выводу, что мне надо просто немного отдохнуть

[mayton2019]

Да ради бога. Можешь хоть целый год эту задачу делать.

Смотри. Если у тебя есть алгоритм который работает по шагам (step-by-step) то реши
его на бумажке. На малом объеме данных. Вручную. И трекай каждый шаг в таблице.
Это очень прояснит твое понимаение
и у тебя не будет таких наивных вопросов типа почему алгоритм зацикливается.