C ++: std :: map, найти циклы, алгоритм - PullRequest
Новая
       12

C ++: std :: map, найти циклы, алгоритм

0 голосов
/ 15 декабря 2018

Предположим, что следующая структура данных: 

std::map <int, std::vector<int> > M,

, где val представлен последовательностью вершин графа, а ключ является первой вершиной последовательности.Например, 

{1} {1, 8, 12, 7}
{4} {4, 3, 5}
{7} {7, 9, 13, 18, 0, 2}
{2} {2, 11, 1}
{5} {5, 17, 10, 4}
{9} {9, 6, 19, 14}
{14} {14, 15, 9}

Как найти все циклы (аналогичные начальная и конечная вершины) из сегментов {} 

C1: {1 8 12 7} {7 9 13 18 0 2} {2 11 1}
C2: {4 3 5} {5 17 10 4}
C3: {9 6 19 14} {14, 15, 9}

и как избежать дублирования последовательности сегментов с низкимвременная сложность (карта может содержать сотни тысяч последовательностей).Любой цикл может содержать n сегментов {}, где n> = 1.

Фаза инициализации : 

std::map <int, std::vector <int> > M;
M[1] = std::vector<int>{ 1, 8, 12, 7 };
M[4] = std::vector<int>{ 4, 3, 5 };
M[7] = std::vector<int>{ 7, 9, 13, 18, 0, 2 };
M[2] = std::vector<int>{ 2, 11, 1 };
M[5] = std::vector<int>{ 5, 17, 10, 4 };
M[9] = std::vector<int>{ 9, 6, 19, 14 };
M[14] = std::vector<int>{ 14, 15, 9 };

Черновик алгоритм: 

std::vector<std::vector <int> > R;
for (auto im = M.begin(); im != M.end();)
{
    std::vector<int> r, ri = im->second;
    for(;;)
    {
        r.insert(r.end(), ri.begin(), ri.end());
        ri = M[r.back()];
        im = M.erase(M.find(im->first));
        if (r.back() == r.front()) break;
    }
    R.push_back(r);
}

К сожалению, повторное удаление представляет собой дорогостоящую операцию ... Надеюсь, есть более красивое и эффективное решение: -)

Спасибо за вашу помощь ...

Ответы [ 2 ]

0 голосов
/ 15 декабря 2018

Во-первых, ваш внутренний цикл должен быть функцией (что, если пути не цикличны?)

Затем объявите ошибку, если либо

  • Конечный узел численноменьше начального узла (может быть циклом, но не каноническим, поэтому мы не будем печатать эту сдвинутую версию)
  • Конечный узел не найден в главной таблице путей

И это приводит к решению: 

bool try_follow(int from, std::vector<int>& result)
{
    int current = from;
    while (true) {
        auto path = M.find(current);
        if (path == M.end()) return false;
        current = path->second.back();
        if (current < from) return false;
        result.insert(result.end(), path->second.begin()+1, path->second.end());
        if (current == from) return true;
    }
}

int main(void)  
{
    for( auto& kvp : M )
    {
        std::vector<int> x;
        if (try_follow(kvp.first, x)) {
            std::cout << kvp.first;
            for( int y : x )
                std::cout << " - " << y;
            std::cout << std::endl;
        }
    }
}

Демонстрация: https://rextester.com/DWWZ9457

0 голосов
/ 15 декабря 2018

Моя первая трещина: 

for (auto it : M)
{
  if (it.first < it.second.back() && it.second.front() == M[it.second.back()].back())
    std::cout << "Cycle between " << it.first << " and " << it.second.back() << '\n';
}

Конечно, я не найду циклов, которые включают 3+ пути.

...