#include <graphwalker.h>

Public Types
typedef std::queue< edge_type >	bfs_type
typedef graph< N, E > ::const_edge_iterator	const_edge_iterator
typedef graph< N, E > ::edge_iterator	edge_iterator
typedef graph< N, E >::edge_list	edge_list
typedef std::pair < const_edge_iterator, const_edge_iterator >	edge_range
typedef graph< N, E >::edge_type	edge_type
typedef graph< N, E >::index_result	index_result
typedef graph< N, E >::index_type	index_type
typedef bool	result_type
typedef std::vector< edge_range >	stack_type
typedef graph< N, E >::value_type	value_type
Public Member Functions
value_type	current () const
value_type	current_bfs () const
result_type	firstChild ()
	graphwalker (const graph< N, E > &, const N &)
	creates a walker rooted by the node given
	graphwalker (const graph< N, E > &)
	creates a walker rooted by the first candidate root found in the underlying graph
result_type	next ()
result_type	next_bfs ()
result_type	nextSibling ()
result_type	parent ()
void	reset ()
const stack_type &	stack () const
Protected Attributes
const graph< N, E > &	graph_
bfs_type	queue_
edge_list	root_
stack_type	stack_
Private Member Functions
	graphwalker ()

Detailed Description

template<class N, class E>
class graphwalker< N, E >

a walker for an acyclic directed multigraph

Definition at line 13 of file graphwalker.h.

Member Typedef Documentation

template<class N, class E>

typedef std::queue<edge_type> graphwalker< N, E >::bfs_type

Definition at line 34 of file graphwalker.h.

template<class N, class E>

typedef graph<N,E>::const_edge_iterator graphwalker< N, E >::const_edge_iterator

Definition at line 26 of file graphwalker.h.

template<class N, class E>

typedef graph<N,E>::edge_iterator graphwalker< N, E >::edge_iterator

Definition at line 24 of file graphwalker.h.

template<class N, class E>

typedef graph<N,E>::edge_list graphwalker< N, E >::edge_list

Definition at line 22 of file graphwalker.h.

template<class N, class E>

typedef std::pair<const_edge_iterator, const_edge_iterator> graphwalker< N, E >::edge_range

Definition at line 29 of file graphwalker.h.

template<class N, class E>

typedef graph<N,E>::edge_type graphwalker< N, E >::edge_type

Definition at line 20 of file graphwalker.h.

template<class N, class E>

typedef graph<N,E>::index_result graphwalker< N, E >::index_result

Definition at line 18 of file graphwalker.h.

template<class N, class E>

typedef graph<N,E>::index_type graphwalker< N, E >::index_type

Definition at line 16 of file graphwalker.h.

template<class N, class E>

typedef bool graphwalker< N, E >::result_type

Definition at line 36 of file graphwalker.h.

template<class N, class E>

typedef std::vector<edge_range> graphwalker< N, E >::stack_type

Definition at line 33 of file graphwalker.h.

template<class N, class E>

typedef graph<N,E>::value_type graphwalker< N, E >::value_type

Definition at line 38 of file graphwalker.h.

Constructor & Destructor Documentation

template<class N, class E>

graphwalker< N, E >::graphwalker ( const graph< N, E > & g )

creates a walker rooted by the first candidate root found in the underlying graph

Definition at line 83 of file graphwalker.h.

References graphwalker< N, E >::graph_, graphwalker< N, E >::queue_, graphwalker< N, E >::root_, and graphwalker< N, E >::stack_.

 : graph_(g)
{  // complexity = (no nodes) * (no edges)
   graph_.findRoots(root_);
   stack_.push_back(edge_range(root_.begin(),root_.end())); 
   if (root_.size()) {
     queue_.push(root_[0]);
   }
}

template<class N, class E>

graphwalker< N, E >::graphwalker	(	const graph< N, E > &	g,
		const N &	root
	)

creates a walker rooted by the node given

Definition at line 95 of file graphwalker.h.

References graphwalker< N, E >::graph_, graphwalker< N, E >::queue_, dbtoconf::root, graphwalker< N, E >::root_, and graphwalker< N, E >::stack_.

 : graph_(g)
{
   index_result rr = graph_.nodeIndex(root);
   if (!rr.second) // no such root node, no walker can be created!
     throw root;
     
   root_.push_back(edge_type(rr.first, 0));
   stack_.push_back(edge_range(root_.begin(),root_.end()));   
   queue_.push(root_[0]);
}

template<class N, class E>

graphwalker< N, E >::graphwalker ( ) [private]

Member Function Documentation

template<class N , class E >

graphwalker< N, E >::value_type graphwalker< N, E >::current ( ) const [inline]

Definition at line 109 of file graphwalker.h.

Referenced by KinematicTree::currentDecayVertex(), KinematicTree::currentParticle(), KinematicTree::currentProductionVertex(), KinematicTree::daughterParticles(), DDCheckConnect(), graph_combine(), graph_tree_output(), KinematicTree::motherParticle(), KinematicTree::movePointerToTheMother(), output(), KinematicTree::topParticle(), and DDCompactViewImpl::weight().

{
   const edge_range & er = stack_.back();
/*
   const N & n = graph_.nodeData(er.first->first);
   const E & e = er.first->first;
   return value_type(n,e);
*/   
   return value_type(graph_.nodeData(er.first->first), graph_.edgeData(er.first->second)); 
}

template<class N , class E >

graphwalker< N, E >::value_type graphwalker< N, E >::current_bfs ( ) const

Definition at line 122 of file graphwalker.h.

{
   const edge_type & e = queue_.front();
   return value_type(graph_.nodeData(e.first), graph_.edgeData(e.second)); 
}

template<class N , class E >

graphwalker< N, E >::result_type graphwalker< N, E >::firstChild ( )

Definition at line 143 of file graphwalker.h.

References query::result.

Referenced by KinematicTree::currentProductionVertex(), KinematicTree::daughterParticles(), graph_tree_output(), KinematicTree::motherParticle(), KinematicTree::movePointerToTheFirstChild(), KinematicTree::movePointerToTheTop(), and DDCompactViewImpl::weight().

{
   result_type result = false;
   const edge_range & adjEdges
     = graph_.edges(stack_.back().first->first);
   if (adjEdges.first != adjEdges.second) {
     stack_.push_back(adjEdges);
     result = true;
   }
   return result;
}

template<class N , class E >

graphwalker< N, E >::result_type graphwalker< N, E >::next ( void )

Definition at line 185 of file graphwalker.h.

References dbtoconf::parent, and query::result.

Referenced by DDCheckConnect(), graph_combine(), and output().

{
   result_type result = false;
   if (firstChild()) {
     result = true;
   }  
   else if(stack_.size()>1 && nextSibling()) {
     result = true;
   }  
   else {  
     while(parent()) {
       if(stack_.size()>1 && nextSibling()) {
         result = true;
         break;
       }
     }
   }       
   return result;
}

template<class N , class E >

graphwalker< N, E >::result_type graphwalker< N, E >::next_bfs ( )

Definition at line 206 of file graphwalker.h.

References query::result.

{
   result_type result(false);
   if (!queue_.empty()) {
     const edge_type & e = queue_.front();
     const edge_range & er = graph_.edges(e.first);
     const_edge_iterator it(er.first), ed(er.second);
     for (; it != ed; ++it) {
       queue_.push(*it);
     }
     queue_.pop();
     if (!queue_.empty()) {
       result=true;
     }
   }
   return result;
}

template<class N , class E >

graphwalker< N, E >::result_type graphwalker< N, E >::nextSibling ( )

Definition at line 157 of file graphwalker.h.

References query::result.

Referenced by KinematicTree::currentProductionVertex(), KinematicTree::daughterParticles(), graph_tree_output(), KinematicTree::isConsistent(), KinematicTree::motherParticle(), KinematicTree::movePointerToTheNextChild(), and DDCompactViewImpl::weight().

{
   result_type result = false;
   //if (stack_.size() > 1) { only if single-root should be enforced ...
     edge_range & siblings = stack_.back();
     if (siblings.first != (siblings.second - 1) ) {
       ++siblings.first;
       result = true;
     }  
   //}
   return result;
}

template<class N , class E >

graphwalker< N, E >::result_type graphwalker< N, E >::parent ( )

Definition at line 172 of file graphwalker.h.

References query::result.

Referenced by graph_tree_output(), KinematicTree::motherParticle(), and KinematicTree::movePointerToTheMother().

{
   //std::cout << "graphwalker::parent()" << std::endl;
   result_type result = false;
   if (stack_.size()>1) {
     stack_.pop_back();
     result = true;
   }
   return result;
}

template<class N , class E >

void graphwalker< N, E >::reset ( void )

Definition at line 130 of file graphwalker.h.

References sistrip::root_.

{
  //std::cout << "graphwalker::reset" << std::endl;
  stack_.clear();
  stack_.push_back(edge_range(root_.begin(),root_.end()));
  queue_.clear();
  if (root_.size()) {
    queue_.push(root_[0]);   
  }
}