Non-recursive post-order graph traversal?

Question

I'm looking to find some pseudocode, algorithm, or guidance that will help me find a proper iterative post-order traversal algorithm for generalized graph data structures.

I've found plenty of resources (like a two stack or one stack algorithms) that works great with trees, but break down for graphs as they can't handle cycles / back edges, cross edges, etc.

I've successfully written a recursive post-order graph traversal algorithm, which looks like this:

template<typename V, typename E>
void tGraph<V, E>::RecursivePostOrderSearch(const tGraph& g, const VertexType& u, std::set<VertexType>& visited, std::vector<VertexType>& result)
{
    if (visited.find(u) == visited.end())
    {
        visited.insert(u);

        EdgeSet edgesOut = g.outgoingEdgesOf(u);

        for(typename EdgeSet::const_iterator iter = edgesOut.begin(); iter != edgesOut.end(); iter++)
        {
            RecursivePostOrderSearch(g, iter->second.second, visited, result);
        }

        result.push_back(u);
    }
}

template<typename V, typename E> std::vector<V> tGraph<V, E>::postOrderList(const VertexType& v) const
{
    std::set<V> visited;
    std::vector<V> result;

    RecursivePostOrderSearch(*this, v, visited, result);

    return result;
}

Where V is the node type, E is an edge type-- pair of "weight" and incoming / outgoing node pairs.

If I run ::postOrderList on the following graph (with root node A):

I expect to get the following nodes in this order (the edges are followed in order by their weight):

D, E, F, B, G, C, A

…And my recursive algorithm above does indeed provide the correct results.

However, trying to convert this into an iterative algorithm has been challenging on my own, and I'm not having any success in doing so. I've tried converting to tail recursion so I can then convert to iterative, but I couldn't figure that out. I've also tried to convert the tree-based two-stack and one-stack algorithms, but am not able to replicate the results correctly there either.

I've seen similar stack overflow questions for this, but none appear to cover actual iterative algorithms, pseudocode, or recursive to iterative translation for this kind of algorithm, so any guidance in that direction I believe will really help.

Thanks in advance.

Related: https://stackoverflow.com/questions/1294701/post-order-traversal-of-binary-tree-without-recursion — Ciro Santilli OurBigBook.com, Mar 07 '22 at 10:37

score 4 · Accepted Answer · answered Jun 01 '18 at 14:56

The result.push_back is problematic but can be handled by handling each node twice, use a flag to specify whether you want to visit children or push it back.

To implement that you can use a stack/vector with a struct containing "u" and a bool (for the flag).

Something along these lines:

template<typename V, typename E>
void tGraph<V, E>::PostOrderSearch(const tGraph& g, const VertexType& u, std::set<VertexType>& visited, std::vector<VertexType>& result)
{
    std::vector<std::pair<VertexType,bool> > stack;
    stack.push_back(std::pair<VertexType, bool>(u,false));
    for(;;) {
      if (stack.empty()) return; // Done.
      std::pair<VertexType, bool> item=stack.back();
      stack.pop_back();
      VertexType u=item.first;
      if (item.second) {
         // Post-visit
         result.push_back(u);
      }
      else if (visited.find(u)==visited.end()) {
        // Add in reverse order, due to stack
        visited.insert(u);

        EdgeSet edgesOut = g.outgoingEdgesOf(u);

        stack.push_back(std::pair<VertexType, bool>(u,true));   

        for(typename EdgeSet::const_reverse_iterator iter = edgesOut.rbegin(); iter != edgesOut.rend(); iter++)
        {
            stack.push_back(std::pair<VertexType,bool>(iter->second.second,false));
        }
     }
}

Thank you so much. This worked; I think I understand where I was going wrong. In my attempts at solving this, I was trying to use `std::set` to tag nodes, similar to how I do with the `visited` set. However, it didn't occur to me that it would be better to tag the nodes with a bool, push it on a stack, and process the bool as an opcode-- which makes so much more sense now that I see how you've implemented it. Again, thanks so much. I really appreciate your help. — tjgrant, Jun 01 '18 at 20:26

Non-recursive post-order graph traversal?

1 Answers1