CMS 3D CMS Logo

graphwalker< N, E > Class Template Reference

a walker for an acyclic directed multigraph More...

#include <DetectorDescription/Core/interface/graphwalker.h>

List of all members.

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  )  [inline]

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_.

00084  : graph_(g)
00085 {  // complexity = (no nodes) * (no edges)
00086    graph_.findRoots(root_);
00087    stack_.push_back(edge_range(root_.begin(),root_.end())); 
00088    if (root_.size()) {
00089      queue_.push(root_[0]);
00090    }
00091 }

template<class N, class E>
graphwalker< N, E >::graphwalker ( const graph< N, E > &  g,
const N &  root 
) [inline]

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_, graphwalker< N, E >::root_, and graphwalker< N, E >::stack_.

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

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.

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

Referenced by DDCheckConnect(), graph_combine(), graph_tree_output(), output(), and DDCompactViewImpl::weight().

00110 {
00111    const edge_range & er = stack_.back();
00112 /*
00113    const N & n = graph_.nodeData(er.first->first);
00114    const E & e = er.first->first;
00115    return value_type(n,e);
00116 */   
00117    return value_type(graph_.nodeData(er.first->first), graph_.edgeData(er.first->second)); 
00118 }

template<class N, class E>
graphwalker< N, E >::value_type graphwalker< N, E >::current_bfs (  )  const [inline]

Definition at line 122 of file graphwalker.h.

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

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

template<class N, class E>
graphwalker< N, E >::result_type graphwalker< N, E >::firstChild (  )  [inline]

Definition at line 143 of file graphwalker.h.

References graphwalker< N, E >::graph_, HLT_VtxMuL3::result, and graphwalker< N, E >::stack_.

Referenced by graph_tree_output(), graphwalker< N, E >::next(), and DDCompactViewImpl::weight().

00144 {
00145    result_type result = false;
00146    const edge_range & adjEdges
00147      = graph_.edges(stack_.back().first->first);
00148    if (adjEdges.first != adjEdges.second) {
00149      stack_.push_back(adjEdges);
00150      result = true;
00151    }
00152    return result;
00153 }

template<class N, class E>
graphwalker< N, E >::result_type graphwalker< N, E >::next (  )  [inline]

Definition at line 185 of file graphwalker.h.

References graphwalker< N, E >::firstChild(), graphwalker< N, E >::nextSibling(), graphwalker< N, E >::parent(), HLT_VtxMuL3::result, and graphwalker< N, E >::stack_.

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

00186 {
00187    result_type result = false;
00188    if (firstChild()) {
00189      result = true;
00190    }  
00191    else if(stack_.size()>1 && nextSibling()) {
00192      result = true;
00193    }  
00194    else {  
00195      while(parent()) {
00196        if(stack_.size()>1 && nextSibling()) {
00197          result = true;
00198          break;
00199        }
00200      }
00201    }       
00202    return result;
00203 }

template<class N, class E>
graphwalker< N, E >::result_type graphwalker< N, E >::next_bfs (  )  [inline]

Definition at line 206 of file graphwalker.h.

References e, graphwalker< N, E >::graph_, it, graphwalker< N, E >::queue_, and HLT_VtxMuL3::result.

00207 {
00208    result_type result(false);
00209    if (!queue_.empty()) {
00210      const edge_type & e = queue_.front();
00211      const edge_range & er = graph_.edges(e.first);
00212      const_edge_iterator it(er.first), ed(er.second);
00213      for (; it != ed; ++it) {
00214        queue_.push(*it);
00215      }
00216      queue_.pop();
00217      if (!queue_.empty()) {
00218        result=true;
00219      }
00220    }
00221    return result;
00222 }

template<class N, class E>
graphwalker< N, E >::result_type graphwalker< N, E >::nextSibling (  )  [inline]

Definition at line 157 of file graphwalker.h.

References HLT_VtxMuL3::result, and graphwalker< N, E >::stack_.

Referenced by graph_tree_output(), graphwalker< N, E >::next(), and DDCompactViewImpl::weight().

00158 {
00159    result_type result = false;
00160    //if (stack_.size() > 1) { only if single-root should be enforced ...
00161      edge_range & siblings = stack_.back();
00162      if (siblings.first != (siblings.second - 1) ) {
00163        ++siblings.first;
00164        result = true;
00165      }  
00166    //}
00167    return result;
00168 }

template<class N, class E>
graphwalker< N, E >::result_type graphwalker< N, E >::parent (  )  [inline]

Definition at line 172 of file graphwalker.h.

References HLT_VtxMuL3::result, and graphwalker< N, E >::stack_.

Referenced by graph_tree_output(), and graphwalker< N, E >::next().

00173 {
00174    //std::cout << "graphwalker::parent()" << std::endl;
00175    result_type result = false;
00176    if (stack_.size()>1) {
00177      stack_.pop_back();
00178      result = true;
00179    }
00180    return result;
00181 }

template<class N, class E>
void graphwalker< N, E >::reset ( void   )  [inline]

Definition at line 130 of file graphwalker.h.

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

00131 {
00132   //std::cout << "graphwalker::reset" << std::endl;
00133   stack_.clear();
00134   stack_.push_back(edge_range(root_.begin(),root_.end()));
00135   queue_.clear();
00136   if (root_.size()) {
00137     queue_.push(root_[0]);   
00138   }
00139 }

template<class N, class E>
const stack_type& graphwalker< N, E >::stack (  )  const [inline]

Definition at line 65 of file graphwalker.h.

Referenced by graph_combine(), and graph_tree_output().

00065 { return stack_;}

Member Data Documentation

template<class N, class E>
const graph<N,E>& graphwalker< N, E >::graph_ [protected]

Definition at line 73 of file graphwalker.h.

Referenced by graphwalker< N, E >::current(), graphwalker< N, E >::current_bfs(), graphwalker< N, E >::firstChild(), graphwalker< N, E >::graphwalker(), and graphwalker< N, E >::next_bfs().

template<class N, class E>
bfs_type graphwalker< N, E >::queue_ [protected]

Definition at line 70 of file graphwalker.h.

Referenced by graphwalker< N, E >::current_bfs(), graphwalker< N, E >::graphwalker(), graphwalker< N, E >::next_bfs(), and graphwalker< N, E >::reset().

template<class N, class E>
edge_list graphwalker< N, E >::root_ [protected]

Definition at line 71 of file graphwalker.h.

Referenced by graphwalker< N, E >::graphwalker(), and graphwalker< N, E >::reset().

template<class N, class E>
stack_type graphwalker< N, E >::stack_ [protected]

Definition at line 69 of file graphwalker.h.

Referenced by graphwalker< N, E >::current(), graphwalker< N, E >::firstChild(), graphwalker< N, E >::graphwalker(), graphwalker< N, E >::next(), graphwalker< N, E >::nextSibling(), graphwalker< N, E >::parent(), graphwalker< N, E >::reset(), and graphwalker< ReferenceCountingPointer, ReferenceCountingPointer >::stack().

The documentation for this class was generated from the following file:
Generated on Tue Jun 9 18:23:15 2009 for CMSSW by  doxygen 1.5.4