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...
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 ()=delete

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

template<class N, class E>

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

Definition at line 26 of file GraphWalker.h.

template<class N, class E>

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

Definition at line 20 of file GraphWalker.h.

template<class N, class E>

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

Definition at line 19 of file GraphWalker.h.

template<class N, class E>

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

Definition at line 18 of file GraphWalker.h.

template<class N, class E>

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

Definition at line 23 of file GraphWalker.h.

template<class N, class E>

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

Definition at line 17 of file GraphWalker.h.

template<class N, class E>

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

Definition at line 16 of file GraphWalker.h.

template<class N, class E>

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

Definition at line 15 of file GraphWalker.h.

template<class N, class E>

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

Definition at line 28 of file GraphWalker.h.

template<class N, class E>

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

Definition at line 25 of file GraphWalker.h.

template<class N, class E>

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

Definition at line 29 of file GraphWalker.h.

Constructor & Destructor Documentation

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 69 of file GraphWalker.h.

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

 : 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]);
   }
}

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 80 of file GraphWalker.h.

References math::GraphWalker< N, E >::graph_, math::GraphWalker< N, E >::queue_, pyrootRender::root, math::GraphWalker< N, E >::root_, findQualityFiles::rr, and math::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_.emplace_back(edge_type(rr.first, 0));
   stack_.emplace_back(edge_range(root_.begin(),root_.end()));   
   queue_.push(root_[0]);
}

template<class N, class E>

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

privatedelete

Member Function Documentation

template<class N , class E >

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

inline

Definition at line 93 of file GraphWalker.h.

References math::GraphWalker< N, E >::graph_, and math::GraphWalker< N, E >::stack_.

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

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

template<class N , class E >

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

(

)

const

Definition at line 100 of file GraphWalker.h.

References MillePedeFileConverter_cfg::e, math::GraphWalker< N, E >::graph_, and math::GraphWalker< N, E >::queue_.

{
   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 math::GraphWalker< N, E >::firstChild

(

)

Definition at line 118 of file GraphWalker.h.

References math::GraphWalker< N, E >::graph_, mps_fire::result, and math::GraphWalker< N, E >::stack_.

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

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

template<class N , class E >

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

(

void

)

Definition at line 154 of file GraphWalker.h.

References math::GraphWalker< N, E >::firstChild(), math::GraphWalker< N, E >::nextSibling(), math::GraphWalker< N, E >::parent(), mps_fire::result, and math::GraphWalker< N, E >::stack_.

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 math::GraphWalker< N, E >::next_bfs

(

)

Definition at line 175 of file GraphWalker.h.

References MillePedeFileConverter_cfg::e, math::GraphWalker< N, E >::graph_, math::GraphWalker< N, E >::queue_, and mps_fire::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 math::GraphWalker< N, E >::nextSibling

(

)

Definition at line 131 of file GraphWalker.h.

References mps_fire::result, and math::GraphWalker< N, E >::stack_.

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

{
   result_type result = false;
   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 math::GraphWalker< N, E >::parent

(

)

Definition at line 143 of file GraphWalker.h.

References mps_fire::result, and math::GraphWalker< N, E >::stack_.

Referenced by Vispa.Gui.ConnectableWidget.ConnectableWidget::addMenuEntry(), Vispa.Views.LineDecayView.LineDecayContainer::applyFilter(), Vispa.Views.BoxDecayView.BoxDecayContainer::arrangeUsingRelations(), Vispa.Views.BoxDecayView.BoxDecayContainer::autolayoutAlgorithm(), Vispa.Gui.ZoomableScrollableWidgetOwner.ZoomableScrollableWidgetOwner::autosizeScrollArea(), Vispa.Views.BoxDecayView.BoxDecayContainer::autosizeScrollArea(), Vispa.Gui.PortWidget.PortWidget::connectionPoint(), Vispa.Main.StartupScreen.StartupScreen::createDescriptionWidget(), Vispa.Views.BoxDecayView.BoxDecayContainer::dataAccessor(), Vispa.Views.LineDecayView.LineDecayContainer::dataAccessor(), Vispa.Views.LineDecayView.DecayLine::dataAccessor(), Vispa.Views.LineDecayView.LineDecayContainer::delete(), Vispa.Views.LineDecayView.DecayNode::delete(), Vispa.Views.LineDecayView.DecayLine::delete(), Vispa.Gui.VispaWidget.VispaWidget::delete(), Vispa.Gui.VispaWidget.VispaWidget::dragWidget(), Vispa.Share.ImageExporter.ImageExporter::exportImageDialog(), Vispa.Views.LineDecayView.DecayLine::extendedSize(), graph_tree_output(), Vispa.Gui.VispaWidget.VispaWidget::keyPressEvent(), Vispa.Gui.MenuWidget.MenuWidget::leaveEvent(), Vispa.Gui.ConnectableWidget.ConnectableWidget::leaveEvent(), Vispa.Gui.PortWidget.PortWidget::moduleParent(), Vispa.Gui.WidgetContainer.WidgetContainer::mouseDoubleClickEvent(), Vispa.Gui.VispaWidget.VispaWidget::mouseDoubleClickEvent(), Vispa.Gui.PortConnection.PointToPointConnection::mousePressEvent(), Vispa.Gui.VispaWidget.VispaWidget::mousePressEvent(), Vispa.Views.LineDecayView.ParticleWidget::mousePressEvent(), Vispa.Views.LineDecayView.DecayNode::move(), math::GraphWalker< N, E >::next(), Vispa.Views.LineDecayView.LineDecayContainer::noDecorationsMode(), Vispa.Views.LineDecayView.LineDecayContainer::operationId(), Vispa.Views.LineDecayView.DecayLine::paint(), Vispa.Gui.VispaWidget.VispaWidget::paintEvent(), Vispa.Gui.ConnectableWidget.ConnectableWidget::positionizeMenuWidget(), Vispa.Views.LineDecayView.DecayLine::qtLineStyle(), Vispa.Views.WidgetView.WidgetView::restoreSelection(), Vispa.Views.WidgetView.WidgetView::select(), Vispa.Gui.PortConnection.PointToPointConnection::select(), Vispa.Gui.VispaWidget.VispaWidget::select(), Vispa.Views.LineDecayView.LineDecayContainer::select(), Vispa.Views.LineDecayView.LineDecayContainer::sizeHint(), Vispa.Views.LineDecayView.LineDecayContainer::tabController(), Vispa.Views.BoxDecayView.BoxDecayContainer::toggleCollapsed(), Vispa.Views.LineDecayView.DecayNode::unite(), Vispa.Views.PropertyView.PropertyView::valueChanged(), Vispa.Views.BoxDecayView.BoxDecayContainer::widgetByObject(), Vispa.Gui.VispaWidgetOwner.VispaWidgetOwner::widgetDoubleClicked(), and Vispa.Gui.VispaWidgetOwner.VispaWidgetOwner::widgetDragged().

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

template<class N , class E >

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

(

void

)

Definition at line 107 of file GraphWalker.h.

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

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

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(), and graph_tree_output().

{ return stack_;}

Member Data Documentation

template<class N, class E>

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

protected

Definition at line 62 of file GraphWalker.h.

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

template<class N, class E>

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

protected

Definition at line 60 of file GraphWalker.h.

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

template<class N, class E>

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

protected

Definition at line 61 of file GraphWalker.h.

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

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< N, E >::current(), math::GraphWalker< N, E >::firstChild(), math::GraphWalker< N, E >::GraphWalker(), math::GraphWalker< N, E >::next(), math::GraphWalker< N, E >::nextSibling(), math::GraphWalker< N, E >::parent(), math::GraphWalker< N, E >::reset(), and math::GraphWalker< DDLogicalPart, DDPosData * >::stack().