math::GraphWalker< N, E > Class Template Reference

#include <GraphWalker.h>

Public Types
using	bfs_type = std::queue< edge_type >
using	const_edge_iterator = typename math::Graph< N, E >::const_edge_iterator
using	edge_iterator = typename math::Graph< N, E >::edge_iterator
using	edge_list = typename math::Graph< N, E >::edge_list
using	edge_range = std::pair< const_edge_iterator, const_edge_iterator >
using	edge_type = typename math::Graph< N, E >::edge_type
using	index_result = typename math::Graph< N, E >::index_result
using	index_type = typename math::Graph< N, E >::index_type
using	result_type = bool
using	stack_type = std::vector< edge_range >
using	value_type = typename math::Graph< N, E >::value_type

Public Member Functions
value_type	current () const
value_type	current_bfs () const
result_type	firstChild ()
	GraphWalker (const Graph< N, E > &)
	creates a walker rooted by the first candidate root found in the underlying Graph More...
	GraphWalker (const Graph< N, E > &, const N &)
	creates a walker rooted by the node given More...
	GraphWalker ()=delete
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_

Detailed Description

template<class N, class E>
class math::GraphWalker< N, E >

a walker for an acyclic directed multigraph

Definition at line 12 of file GraphWalker.h.

Member Typedef Documentation

bfs_type

template<class N, class E>

using math::GraphWalker< N, E >::bfs_type = std::queue<edge_type>

Definition at line 25 of file GraphWalker.h.

const_edge_iterator

template<class N, class E>

using math::GraphWalker< N, E >::const_edge_iterator = typename math::Graph<N, E>::const_edge_iterator

Definition at line 19 of file GraphWalker.h.

edge_iterator

template<class N, class E>

using math::GraphWalker< N, E >::edge_iterator = typename math::Graph<N, E>::edge_iterator

Definition at line 18 of file GraphWalker.h.

edge_list

template<class N, class E>

using math::GraphWalker< N, E >::edge_list = typename math::Graph<N, E>::edge_list

Definition at line 17 of file GraphWalker.h.

edge_range

template<class N, class E>

using math::GraphWalker< N, E >::edge_range = std::pair<const_edge_iterator, const_edge_iterator>

Definition at line 22 of file GraphWalker.h.

edge_type

template<class N, class E>

using math::GraphWalker< N, E >::edge_type = typename math::Graph<N, E>::edge_type

Definition at line 16 of file GraphWalker.h.

index_result

template<class N, class E>

using math::GraphWalker< N, E >::index_result = typename math::Graph<N, E>::index_result

Definition at line 15 of file GraphWalker.h.

index_type

template<class N, class E>

using math::GraphWalker< N, E >::index_type = typename math::Graph<N, E>::index_type

Definition at line 14 of file GraphWalker.h.

result_type

template<class N, class E>

using math::GraphWalker< N, E >::result_type = bool

Definition at line 27 of file GraphWalker.h.

stack_type

template<class N, class E>

using math::GraphWalker< N, E >::stack_type = std::vector<edge_range>

Definition at line 24 of file GraphWalker.h.

value_type

template<class N, class E>

using math::GraphWalker< N, E >::value_type = typename math::Graph<N, E>::value_type

Definition at line 28 of file GraphWalker.h.

Constructor & Destructor Documentation

GraphWalker() [1/3]

template<class N, class E>

math::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 66 of file GraphWalker.h.

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

GraphWalker() [2/3]

template<class N, class E>

math::GraphWalker< N, E >::GraphWalker	(	const Graph< N, E > &	g,
		const N &	root
	)

creates a walker rooted by the node given

Definition at line 75 of file GraphWalker.h.

                                                                    : graph_(g) {
    index_result rr = graph_.nodeIndex(root);
    if (!rr.second)  // no such root node, no walker can be created!
      throw root;

    root_.emplace_back(edge_type(rr.first, 0));
    stack_.emplace_back(edge_range(root_.begin(), root_.end()));
    queue_.push(root_[0]);
  }

GraphWalker() [3/3]

template<class N, class E>

math::GraphWalker< N, E >::GraphWalker ( )

delete

Member Function Documentation

current()

template<class N , class E >

GraphWalker< N, E >::value_type math::GraphWalker< N, E >::current ( ) const

inline

Definition at line 86 of file GraphWalker.h.

Referenced by HGCalWaferValidation::DDFindHGCal(), HGCalWaferValidation::DDFindWafers(), graph_combine(), and HGCalWaferValidation::ProcessWaferLayer().

                                                                        {
    const edge_range &er = stack_.back();
    return value_type(graph_.nodeData(er.first->first), graph_.edgeData(er.first->second));
  }

current_bfs()

template<class N , class E >

GraphWalker< N, E >::value_type math::GraphWalker< N, E >::current_bfs

(

)

const

Definition at line 92 of file GraphWalker.h.

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

firstChild()

template<class N , class E >

GraphWalker< N, E >::result_type math::GraphWalker< N, E >::firstChild

(

)

Definition at line 108 of file GraphWalker.h.

Referenced by HGCalWaferValidation::DDFindHGCal(), and HGCalWaferValidation::DDFindWafers().

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

next()

template<class N , class E >

GraphWalker< N, E >::result_type math::GraphWalker< N, E >::next

(

void

)

Definition at line 140 of file GraphWalker.h.

Referenced by graph_combine().

                                                                {
    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;
  }

next_bfs()

template<class N , class E >

GraphWalker< N, E >::result_type math::GraphWalker< N, E >::next_bfs

(

)

Definition at line 158 of file GraphWalker.h.

                                                                    {
    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;
  }

nextSibling()

template<class N , class E >

GraphWalker< N, E >::result_type math::GraphWalker< N, E >::nextSibling

(

)

Definition at line 119 of file GraphWalker.h.

Referenced by HGCalWaferValidation::DDFindHGCal(), HGCalWaferValidation::DDFindWafers(), and HGCalWaferValidation::ProcessWaferLayer().

                                                                       {
    result_type result = false;
    edge_range &siblings = stack_.back();
    if (siblings.first != (siblings.second - 1)) {
      ++siblings.first;
      result = true;
    }
    return result;
  }

parent()

template<class N , class E >

GraphWalker< N, E >::result_type math::GraphWalker< N, E >::parent

(

)

Definition at line 130 of file GraphWalker.h.

Referenced by HGCalWaferValidation::DDFindHGCal(), and HGCalWaferValidation::DDFindWafers().

                                                                  {
    result_type result = false;
    if (stack_.size() > 1) {
      stack_.pop_back();
      result = true;
    }
    return result;
  }

reset()

template<class N , class E >

void math::GraphWalker< N, E >::reset

(

void

)

Definition at line 98 of file GraphWalker.h.

                                {
    stack_.clear();
    stack_.emplace_back(edge_range(root_.begin(), root_.end()));
    queue_.clear();
    if (root_.size()) {
      queue_.push(root_[0]);
    }
  }

stack()

template<class N, class E>

const stack_type& math::GraphWalker< N, E >::stack ( ) const

inline

Definition at line 55 of file GraphWalker.h.

Referenced by graph_combine().

{ return stack_; }

Member Data Documentation

graph_

template<class N, class E>

const Graph<N, E>& math::GraphWalker< N, E >::graph_

protected

Definition at line 62 of file GraphWalker.h.

queue_

template<class N, class E>

bfs_type math::GraphWalker< N, E >::queue_

protected

Definition at line 60 of file GraphWalker.h.

root_

template<class N, class E>

edge_list math::GraphWalker< N, E >::root_

protected

Definition at line 61 of file GraphWalker.h.

stack_

template<class N, class E>

stack_type math::GraphWalker< N, E >::stack_

protected

Definition at line 59 of file GraphWalker.h.

Referenced by math::GraphWalker< DDLogicalPart, DDPosData * >::stack().