不変グラフ上で効率的な非再帰的トポロジカルソートを行う方法

Question

不変グラフ上で効率的な非再帰的トポロジカルソートを行う良い方法はありますか？私はポインタでリンクされたグラフを横断していて、トポロジカルな並べ替えが必要な状況があります。私はグラフを修正しないことが重要ですが、ノードを訪問したとマークする方法と、それを行わずに効率的にチェックする方法はわかりません。現時点では、私はマーキングを格納するセットがありますが、私はlog(m)時間で検索が発生することを知っています。これを改善する方法はありますか？ここではいくつかの作業コードです：上記

f 
e 
d 
c 
a 
b 

を与える

// For std::shared_ptr 
#include <memory> 

// For std::list, std::stack, std::set 
#include <list> 
#include <stack> 
#include <set> 

// For std::cout 
#include <iostream> 

// Node in a directed acyclic graph with only two exiting edges 
struct Node { 
    // Identity of the node for debugging 
    char identity; 

    // Left and right branches 
    std::shared_ptr <Node> left; 
    std::shared_ptr <Node> right; 

    // Create a node 
    Node(
     char const & identity_, 
     std::shared_ptr <Node> const & left_, 
     std::shared_ptr <Node> const & right_ 
    ) : identity(identity_), left(left_), right(right_) 
    {} 
}; 


// Determines a topological sort of a directed acyclic graph of compute nodes 
std::list <std::shared_ptr <Node>> topo_sort(
    std::shared_ptr <Node> const & root 
) { 
    // Add the root node to the todo list. The todo list consists of 
    // (ptr,whether we've searched left,whether we've searched right). 
    auto todo = std::stack <std::tuple <std::shared_ptr <Node>,bool,bool>>(); 
    todo.push(std::make_tuple(root,false,false)); 

    // Add an empty list for the sorted elements 
    auto sorted = std::list <std::shared_ptr <Node>> {}; 

    // Keep track of which nodes have been marked 
    auto marked = std::set <std::shared_ptr <Node>> {root}; 

    // Determines if a node has been marked 
    auto is_marked = [&](auto const & node) { 
     return marked.find(node)!=marked.end(); 
    }; 

    // Loop over the elements in the todo stack until we have none left to 
    // process 
    while(todo.size()>0) { 
     // Grab the current node 
     auto & current = todo.top(); 
     auto & node = std::get <0> (current); 
     auto & searched_left = std::get <1> (current); 
     auto & searched_right = std::get <2> (current); 

     // Grab the left and right nodes 
     auto left = node->left; 
     auto right = node->right; 

     // Do a quick check to determine whether we actually have children 
     if(!left) 
      searched_left = true; 
     if(!right) 
      searched_right = true; 

     // If we've already transversed both left and right, add the node to 
     // the sorted list 
     if(searched_left && searched_right) { 
      sorted.push_front(node); 
      marked.insert(node); 
      todo.pop(); 

     // Otherwise, traverse the left branch if that node hasn't been marked 
     } else if(!searched_left) { 
      searched_left = true; 
      if(!is_marked(left)) { 
       todo.push(std::make_tuple(left,false,false)); 
       marked.insert(left); 
      } 

     // Next, traverse the right branch if that node hasn't been marked 
     } else if(!searched_right) { 
      searched_right = true; 
      if(!is_marked(right)) { 
       todo.push(std::make_tuple(right,false,false)); 
       marked.insert(right); 
      } 
     } 
    } 

    // Return the topological sort 
    return sorted; 
} 

int main() { 
    // Create a graph with some dependencies 
    auto a = std::make_shared <Node> ('a',nullptr,nullptr); 
    auto b = std::make_shared <Node> ('b',nullptr,nullptr); 
    auto c = std::make_shared <Node> ('c',a,a); 
    auto d = std::make_shared <Node> ('d',b,c); 
    auto e = std::make_shared <Node> ('e',d,c); 
    auto f = std::make_shared <Node> ('f',e,c); 

    // Sort the elements 
    auto sorted = topo_sort(f); 

    // Print out the sorted order 
    for(auto const & node : sorted) 
     std::cout << node->identity << std::endl; 
} 

は、ソートのための深さ優先探索を行う必要があります。そして、はい、これはグラフの面白い探し木ですが、左と右の要素は固有の要素を指す必要はありません。いずれにしても、事前に助けてくれてありがとう。

Answer 1

のstd ::

代わりstd::set<std::shared_ptr<Node>>のunorderd_setソリューションは、あなたが訪問したノードをマークするstd::unordered_set<Node*>を使用することができます。 unordered_setハッシュを使用してノードをインデックスする（複雑さ：平均で一定）ので、ほとんどの場合、setより速くなければなりません。また、参照カウント操作がないので、生ポインタ（Node*）をコンテナに保存すると、shared_ptrより速くなります。

このソリューションではメモリが多すぎる場合は、bitmapソリューションを試すことができます。

ビットマップソリューション

は、各ノードに0から始まる番号を付け、そして訪問した状態を保存するためにbitmapを使用しています。

は（そのID nある）n番目ノードを訪問するとき、bitmapにn番目ビットをセット0に設定し、すべてのビットとbitmapを初期化します。特定のノードが訪問されたかどうかを調べるには、対応するビットが設定されているかどうかをチェックするだけです。

このソリューションは、nがツリー内のノードの数である場合、nビットのメモリしか必要としません。

Answer 2

ログの複雑さはほとんど常に十分に速いです。 std :: mapとstd :: setには、ハッシュテーブルとは別の利点もあります。たとえば、パフォーマンスは100％保証されています。ハードリアルタイムシステム。ハッシュテーブルは、赤黒のツリー（マップ、セット）よりも高速ですが、ほとんどの場合、再ハッシュが必要な場合は、最悪の場合のパフォーマンスが発生します。