#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

◆ 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 68 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 77 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 ( )

privatedelete

Member Function Documentation

◆ current()

template<class N , class E >

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

inline

Definition at line 88 of file GraphWalker.h.

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

Referenced by graph_combine().

◆ current_bfs()

template<class N , class E >

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

Definition at line 94 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 110 of file GraphWalker.h.

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

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

Referenced by graph_combine().

◆ next_bfs()

template<class N , class E >

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

Definition at line 160 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 121 of file GraphWalker.h.

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

                                                                   {
     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 100 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 54 of file GraphWalker.h.

54 { return stack_; }

Referenced by graph_combine().

Member Data Documentation

◆ graph_

template<class N, class E>

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

protected

Definition at line 61 of file GraphWalker.h.

◆ queue_

template<class N, class E>

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

protected

Definition at line 59 of file GraphWalker.h.

◆ root_

template<class N, class E>

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

protected

Definition at line 60 of file GraphWalker.h.

◆ stack_

template<class N, class E>

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

protected

Definition at line 58 of file GraphWalker.h.

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

Public Types

Public Member Functions

Protected Attributes

Private Member Functions

Detailed Description

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

Member Typedef Documentation

◆ bfs_type

◆ const_edge_iterator

◆ edge_iterator

◆ edge_list

◆ edge_range

◆ edge_type

◆ index_result

◆ index_type

◆ result_type

◆ stack_type

◆ value_type

Constructor & Destructor Documentation

◆ GraphWalker() [1/3]

◆ GraphWalker() [2/3]

◆ GraphWalker() [3/3]

Member Function Documentation

◆ current()

◆ current_bfs()

◆ firstChild()

◆ next()

◆ next_bfs()

◆ nextSibling()

◆ parent()

◆ reset()

◆ stack()

Member Data Documentation

◆ graph_

◆ queue_

◆ root_

◆ stack_

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