[Lemon-user] Game Tree Code

[Alpar Juttner]

Yes, it is reasonable to do it that way. However
      * you don't have to reinvent the wheel - BFS is already
        implemented, why not use it?
      * the deleted Nodes are indeed invalidated, but you can still
        iterate through the nodes if you store the successor of a node
        before deletion.

Thus, the code will look like this:

#include <lemon/bfs.h>

void dag_slice ( Graph& dag_, const Node& node_ ) {
  Bfs<Graph> bfs(dag_);
  bfs.run(node_);
  for(Graph::NodeIt n(g);n!=INVALID;) {
    NodeIt next = n; ++next;
    if(!bfs.reached(n))
      dag_.erase(n);
    n = next;
  }
}

Best regards,
Alpár Jüttner


On Wed, 2015-04-08 at 11:17 +0300, degski wrote:
> 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
> 
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user