Создание транзитивного набора пар с использованием переполнения стека STL

Question

Создание транзитивного набора пар с использованием переполнения стека STL

Я хотел бы создать набор, который имеет транзитивные пары. Мой вклад будет иметь вид pair<int, int> и мне нужен набор, который имеет все транзитивные пары для заданных входов.
Например, если у меня есть пары {1, 2} {2, 1} {2, 3} {3,4} в качестве входов, то мне нужно иметь SET, который имеет пары {{1,2}, {2, 1}, {1, 3}, {3, 4}, {1, 4}, {2, 4}}. Мне также нужно выяснить, является ли данная пара членом этого транзитивного набора.
Есть ли какая-либо встроенная структура данных / библиотека STL, которая позволит мне сделать это в C ++?

0

c++set stl transitive-closure

Решение

Другие решения

Вы можете представить свой набор с помощью:

set<pair<int, int>> myset;

Транзитивное замыкание затем может быть вычислено с помощью:

void transitive_closure(set<pair<int, int>>& s)
{
set<pair<int, int>> a;   // missing nodes to add
for (auto i = s.cbegin(); i != s.cend(); i++)
{
for (auto j = i; ++j != s.cend(); j)
{
if (i->second == j->first
&& i->first != j->second
&& s.count(make_pair(i->first, j->second))==0 )
a.insert(make_pair(i->first, j->second));
}
}
if (!a.empty()) {
for (auto p : a)
s.insert(p);
transitive_closure(s);
}
}

Это не самый оптимизированный алгоритм, потому что рекурсия повторит некоторые сравнения. Но это работает. Кстати, я думаю, что вы забыли {2, 3} в наборе результатов.

Чтобы проверить, принадлежит ли пара к набору, просто проверьте, s.count(make_pair(i->first, j->second)!=0

1

Источник

Accepted Answer

У вас есть график, и вы хотите превратить его в свободную категорию, AKA — транзитивное замыкание этого графика.

Ваш int парные элементы — это вершины, сами пары — ребра, это ваш граф. Теперь свободной категорией на графе является тот граф с законом композиции ребер и всеми дополнительными ребрами, которые могут быть созданы законом. Закон гласит, что

если есть грань (или «стрелка», как ее называет теория категорий) f который бежит из a в b
и ребро g который бежит из b в c
тогда есть еще один край, обозначенный f∘g который бежит из a в c
состав ассоциативный ((f∘g)∘h = f∘(g∘h))

(Каждая категория также имеет единичные ребра, обозначенные 1_a которые бегут от a в a для каждой вершины aи закон, который говорит, что для каждой стрелки f который бежит из a в b, 1_a∘f = f∘1_b= f, но речь не о тех).

_{Общеобразовательная часть этого ответа настоящим завершена.}

В стандартной библиотеке C ++ нет соответствующих алгоритмов, но вы можете проверить boost::graph или любая другая граф-ориентированная библиотека. boost::graph имеет transitive_closure метод, который как раз то, что вы хотите.

1