Aleph::Depth_First_Traversal< GT, Operation, SA > Class Template Reference

Stateful depth-first traversal functor. More...

#include <tpl_graph_utils.H>

Collaboration diagram for Aleph::Depth_First_Traversal< GT, Operation, SA >:

Public Member Functions
	Depth_First_Traversal (SA __sa=SA())
	Construct a traversal functor using the arc filter __sa.
size_t	operator() (const GT &g, Operation op=Operation())
	Traverse starting from the first node of the graph.
size_t	operator() (const GT &g, typename GT::Node *sn, Operation op=Operation())
	Traverse starting from a given node.

Private Member Functions
bool	__dft (typename GT::Node *node, typename GT::Arc *arc=nullptr)
size_t	dft (const GT &g, typename GT::Node *start_node, Operation &__op)

Private Attributes
Operation *	op_ptr = nullptr
SA	sa
size_t	count = 0
const GT *	g_ptr = nullptr

Detailed Description

template<class GT, class Operation = Default_Visit_Op<GT>, class SA = Dft_Show_Arc<GT>>
class Aleph::Depth_First_Traversal< GT, Operation, SA >

Stateful depth-first traversal functor.

Traverses a graph in depth-first order, invoking an operation for each discovered node.

Template parameters:

• GT: graph type
• Operation: visit functor
• SA: arc filter used by the internal iterator

Operation must provide: bool operator()(const GT& g, typename GT::Node* node, typename GT::Arc* from).

If the operation returns true, traversal stops early.

Note

Uses the Depth_First control bit on both nodes and arcs.

See also

depth_first_traversal, Breadth_First_Traversal

Definition at line 165 of file tpl_graph_utils.H.

Constructor & Destructor Documentation

Depth_First_Traversal()

template<class GT , class Operation = Default_Visit_Op<GT>, class SA = Dft_Show_Arc<GT>>

Aleph::Depth_First_Traversal< GT, Operation, SA >::Depth_First_Traversal ( SA  __sa = SA() )

inline

Construct a traversal functor using the arc filter __sa.

Definition at line 221 of file tpl_graph_utils.H.

Member Function Documentation

__dft()

template<class GT , class Operation = Default_Visit_Op<GT>, class SA = Dft_Show_Arc<GT>>

bool Aleph::Depth_First_Traversal< GT, Operation, SA >::__dft ( typename GT::Node *  node, typename GT::Arc *  arc = nullptr  )

inlineprivate

Definition at line 174 of file tpl_graph_utils.H.

References Aleph::Depth_First_Traversal< GT, Operation, SA >::__dft(), ARC_BITS, Aleph::Depth_First_Traversal< GT, Operation, SA >::count, Aleph::Depth_First, Aleph::Depth_First_Traversal< GT, Operation, SA >::g_ptr, GraphCommon< GT, Node, Arc >::get_num_nodes(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_BITS, Aleph::Depth_First_Traversal< GT, Operation, SA >::op_ptr, and Aleph::Depth_First_Traversal< GT, Operation, SA >::sa.

Referenced by Aleph::Depth_First_Traversal< GT, Operation, SA >::__dft(), and Aleph::Depth_First_Traversal< GT, Operation, SA >::dft().

dft()

template<class GT , class Operation = Default_Visit_Op<GT>, class SA = Dft_Show_Arc<GT>>

size_t Aleph::Depth_First_Traversal< GT, Operation, SA >::dft ( const GT &  g, typename GT::Node *  start_node, Operation &  __op  )

inlineprivate

Definition at line 203 of file tpl_graph_utils.H.

References Aleph::Depth_First_Traversal< GT, Operation, SA >::__dft(), Aleph::Depth_First_Traversal< GT, Operation, SA >::count, Aleph::Depth_First, Aleph::Depth_First_Traversal< GT, Operation, SA >::g_ptr, Aleph::maps(), Aleph::Depth_First_Traversal< GT, Operation, SA >::op_ptr, GraphCommon< GT, Node, Arc >::reset_bit_arcs(), and GraphCommon< GT, Node, Arc >::reset_bit_nodes().

Referenced by Aleph::Depth_First_Traversal< GT, Operation, SA >::operator()(), and Aleph::Depth_First_Traversal< GT, Operation, SA >::operator()().

operator()() [1/2]

template<class GT , class Operation = Default_Visit_Op<GT>, class SA = Dft_Show_Arc<GT>>

size_t Aleph::Depth_First_Traversal< GT, Operation, SA >::operator() ( const GT &  g, Operation  op = Operation()  )

inline

Traverse starting from the first node of the graph.

Traverses the connected component reachable from g.get_first_node() in depth-first order.

Side effects:

• Resets the Depth_First control bit on all nodes and arcs.
• Uses the Depth_First control bit on both nodes and arcs.

Parameters

[in]	g	Graph to traverse.
[in]	op	Visit operation.

Returns

Number of discovered nodes.

Exceptions

bad_alloc

If there is not enough memory.

Definition at line 237 of file tpl_graph_utils.H.

References Aleph::Depth_First_Traversal< GT, Operation, SA >::dft(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node().

operator()() [2/2]

template<class GT , class Operation = Default_Visit_Op<GT>, class SA = Dft_Show_Arc<GT>>

size_t Aleph::Depth_First_Traversal< GT, Operation, SA >::operator() ( const GT &  g, typename GT::Node *  sn, Operation  op = Operation()  )

inline

Traverse starting from a given node.

Traverses the connected component reachable from sn in depth-first order.

Side effects:

• Resets the Depth_First control bit on all nodes and arcs.
• Uses the Depth_First control bit on both nodes and arcs.

Parameters

[in]	g	Graph to traverse.
[in]	sn	Starting node (must be non-null and belong to g).
[in]	op	Visit operation.

Returns

Number of discovered nodes.

Exceptions

bad_alloc

If there is not enough memory.

Definition at line 257 of file tpl_graph_utils.H.

References Aleph::Depth_First_Traversal< GT, Operation, SA >::dft().

Member Data Documentation

count

template<class GT , class Operation = Default_Visit_Op<GT>, class SA = Dft_Show_Arc<GT>>

size_t Aleph::Depth_First_Traversal< GT, Operation, SA >::count = 0

private

Definition at line 169 of file tpl_graph_utils.H.

Referenced by Aleph::Depth_First_Traversal< GT, Operation, SA >::__dft(), and Aleph::Depth_First_Traversal< GT, Operation, SA >::dft().

g_ptr

template<class GT , class Operation = Default_Visit_Op<GT>, class SA = Dft_Show_Arc<GT>>

const GT* Aleph::Depth_First_Traversal< GT, Operation, SA >::g_ptr = nullptr

private

Definition at line 170 of file tpl_graph_utils.H.

Referenced by Aleph::Depth_First_Traversal< GT, Operation, SA >::__dft(), and Aleph::Depth_First_Traversal< GT, Operation, SA >::dft().

op_ptr

template<class GT , class Operation = Default_Visit_Op<GT>, class SA = Dft_Show_Arc<GT>>

Operation* Aleph::Depth_First_Traversal< GT, Operation, SA >::op_ptr = nullptr

private

Definition at line 167 of file tpl_graph_utils.H.

Referenced by Aleph::Depth_First_Traversal< GT, Operation, SA >::__dft(), and Aleph::Depth_First_Traversal< GT, Operation, SA >::dft().

sa

template<class GT , class Operation = Default_Visit_Op<GT>, class SA = Dft_Show_Arc<GT>>

SA Aleph::Depth_First_Traversal< GT, Operation, SA >::sa

private

Definition at line 168 of file tpl_graph_utils.H.

Referenced by Aleph::Depth_First_Traversal< GT, Operation, SA >::__dft().

---

The documentation for this class was generated from the following file:

• tpl_graph_utils.H