使用STL C++编写传递对集合

Question

我想创建一个具有传递对的集合。我的输入将是pair<int, int>的形式，我需要一个具有给定输入的所有传递对的集合。例如，如果我有{1,2，2} {2，1} {2,3} {3,4}作为输入对，那么我需要一个具有{{1,2}，{2} ，1}，{1,3}，{3,4}，{1,4}，{2,4}}。我还需要找出一个给定的对是否是这个传递集的成员。 是否有任何内置的数据结构/ STL库，这将允许我在C++中完成此操作？

Answer 1

你有一个图，你想把它变成一个自由的类别，也就是该图的传递闭包。

您的int对元素是顶点，对本身是边，这就是您的图。现在图中的一个自由类别是具有边缘组合定律的图形以及可由法则产生的所有附加边缘。法律规定，

• 如果有一个边缘（或“箭头”的范畴论名字吧）f从a到b
• 以及从b运行到c
• 边缘g运行再有就是表示f∘g另一边缘运行从a到c
• 组合物缔合（(f∘g)∘h = f∘(g∘h)）

（每个类别还单元的边缘，表示1a从a运行a为每个顶点a，并且说，一个法律，对于每一个箭头f从a到b运行，1a∘f = f∘1b= f，但我们不是在谈论那些）。

_{此答案的一般教育部分现已完成。}

C++标准库中没有相关的算法，但您可能需要检查boost::graph或任何其他面向图形的库。 boost::graph有transitive_closure方法，这正是你想要的。

set<pair<int, int>> myset; 

传递闭包然后可以用计算：

Answer 2

你可以代表你的一套

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