1

Есть класс который считывает ребра (в формате (2, 4)) и решает задачу сильно связных компонент. Все отлично работает. Но когда ребер не 19, а например 10000 происходит переполнение стека из-за функции DFSR

void Graph::DFSR(std::vector<std::pair<int, int>> G, int vertex)
{
m_ReadyTest.push_back(vertex); // V как протестированная
// для каждого ребра (s, v) в G
for (auto i : G)
{
    if (vertex == i.first)
    {
        bool go(false);
        // если V еще не протестирован 
        for_each(m_ReadyTest.begin(), m_ReadyTest.end(), 
            [=, &go] (int x)
                {
                    if (x == i.second)
                        go = true;
                });
        if (!go)
        {
            // DFSR(G, V)
            DFSR(G, i.second);
        }
    }
}
++m_time;
auto tmpProcT = make_pair(vertex, m_time); // t = t + 1
m_ProcessingTime.push_back(tmpProcT);      // f[V] = t время завершения обработки вершины V
}

Собственно как я не пытался переписать функцию без рекурсии (использовал цикл + stack)... то вылетает, то не правильно считает. Вообщем нужна ваша помощь.

p.s. ЛИБО как вариант. Объясните подробно как увеличить стек в VisualStudio 15 p.s.s. заранее спасибо!

Вот мой вариант:

void Graph::DFS(vector<pair<int, int>> G, int vertex)
{
/*1*/
m_ReadyTest.push_back(vertex); // V как протестированная

/*2*/
stack<int> iStack;
iStack.push(vertex); // V ложим на вершину стека

/*3*/
while (!iStack.empty()) // пока стек НЕ пустой
{

/*4*/
    int iU = iStack.top();
    for (auto i : G) // ищим все V для U
    {
        if (iU == i.first) // i.second -- V
        {

/*5*/
            bool go(false);
            // если V еще не протестирован 
            for_each(m_ReadyTest.begin(), m_ReadyTest.end(),
                [=, &go](int x)
            {
                if (x == i.second) // V протестирован
                    go = true;
            });
            if (!go)
            {
 /*6*/
                m_ReadyTest.push_back(i.second); // V как протестировану

 /*7*/
                iStack.push(i.second); // V в голову стеку
            }
        }
    }// вершина обработана...

    if (!iStack.empty() && iU == iStack.top())
    {
        iStack.pop();// удаляем U из стека
        ++m_time;
        auto tmpProcT = make_pair(iU, m_time); // t = t + 1
        m_ProcessingTime.push_back(tmpProcT);  // f[V] = t время завершения обработки вершины V
    }
}
}

Результаты мелких тестов совпадают, результат теста на 55к ребер: Результат последнего теста

Боюсь что при решении задачи, а там 5105043 ребра (насколько помню), результат совсем плох будет. п.с. Хоть убей, не понимаю, что еще не правильно у меня в функции DFS.

9
  • 1
    я думаю у вас один выход - это это всё-таки добить версию без рекурсии ... а увеличивать стек в visual studio это уже ненужные извращения.
    – ampawd
    8 июн 2016 в 21:16
  • Угу, присоединяюсь. Покажите ещё вашу попытку с циклом и стеком.
    – VladD
    8 июн 2016 в 22:06
  • Добавил свой DFS.
    – Andrey
    8 июн 2016 в 22:22
  • Из тестовых входных данных правильно работает с 2/3. В 1/3 происходит просто зацикливание.
    – Andrey
    8 июн 2016 в 22:26
  • int iU = iStack.top();: вам в любом случае надо удалять вершину из стека, раз вы её проходите. И для протестированных вершин заведите лучше unordered_set. И локальный, а то вдруг там от прошлого пробега что-то останется.
    – VladD
    8 июн 2016 в 22:36

2 ответа 2

4

Увеличить стек можно так: Свойства проекта → С/С++ → Командная строка и в поле Дополнительные параметры вписываете /F %количество_байт%, то есть:

/F 20971520 – это стек в 20 Мб

Вот статья об этом на MSDN, там же есть и другие способы увеличения стека.

P.S. лучше конечно переписать функцию, но для этого покажите, как вы пытались это сделать и где оно вылетало и т.д.

3
void Graph::DFSR(std::vector<std::pair<int, int>> &G, int vertex)
5
  • Та это вообще не имеет никакого значения в данном случае.
    – Andrey
    8 июн 2016 в 22:37
  • 1
    Можно подсчитать что у вас хранится на стек фрейме на каждый вызов - for (auto i : G) : 8 байт как минимум можно переписать на for (const auto &i : G) плюс вершина и ссылка на граф и того 20 байт плюс минус - на 1000 вершин точно хватит. Оригинальный код без ссылки как минимум медленее плюс добавляет члены вектора в каждый фрейм - а зачем ?
    – ugene
    8 июн 2016 в 22:51
  • В пятом тестовом файле данных почти 55к графов. Ну мне не сложно проверить. Просто суть задания как раз в том, что бы не позволить выполнить его стандартным путем. По этому я сразу и не заморачивался.
    – Andrey
    8 июн 2016 в 23:01
  • по прежнему вылетает ошибка переполнения
    – Andrey
    8 июн 2016 в 23:03
  • К стати в файле с данными по которым нужно дать результат (не тестовые) -- 5105043 графа. Только сейчас увидел.
    – Andrey
    8 июн 2016 в 23:44

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.