[Lemon-user] Game Tree Code

[degski]

The code below implements the deletion of parts of a DAG not reachable from
a certain node. The DAG (ListDigraph) represents a Game Tree with
Transpositions in a "Monte Carlo Tree Search"-implementation. So the code
below does a depth first traversal of the tree (dag), using a std::stack,
marks the visited nodes as visited and deletes the nodes not visited. I
found that deletion of a node invalidates the iterator, so I store the
nodes temporarily in a std::vector and then delete all afterwards. The code
is as follows:

void dag_slice ( Graph& dag_, const Node& node_ ) {

    stack<Node> stk_;

    stk_.push ( node_ );

    IterableBoolNodeMap ibm_ ( dag_ );

    while ( not ( stk_.empty ( ) ) ) {

        const Node n_ ( stk_.top ( ) );

        stk_.pop ( );

        ibm_.set ( n_, true );

        for ( OutArcIt a_ ( dag_, n_ ); a_ != lemon::INVALID; ++a_ ) {

            const Node t_ ( dag_.target ( a_ ) );

            if ( not ( ibm_ [ t_ ] ) ) {

                stk_.push ( t_ );
            }
        }
    }

    vector<Node> ns_;

    for ( IterableBoolNodeMap::FalseIt n_ ( ibm_ ); n_ != lemon::INVALID;
++n_ ) {

        ns_.push_back ( n_ );
    }

    for ( auto n_ : ns_ ) {

        dag_.erase ( n_ );
    }
}

My questions are as follows: Is this a reasonable way to do this? Are there
better suited tools in the lemon library? Should one store Id's instead of
Nodes, and why, if so? Do you have any other suggestions?

Thank you in advance,

Degski
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20150408/eb259293/attachment.html>