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

Stateful breadth-first traversal functor. More...

#include <tpl_graph_utils.H>

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

Private Member Functions
size_t	bft (const GT &g, typename GT::Node *start, Operation &op)

Private Attributes
SA	sa
size_t	count = 0

Detailed Description

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

Stateful breadth-first traversal functor.

Traverses a graph in breadth-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

Resets the Breadth_First control bit on all nodes and arcs.

Uses the Breadth_First control bit on both nodes and arcs.

See also

breadth_first_traversal, Depth_First_Traversal

Definition at line 414 of file tpl_graph_utils.H.

Constructor & Destructor Documentation

Breadth_First_Traversal()

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

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

inline

Construct a traversal functor using the arc filter __sa.

Definition at line 473 of file tpl_graph_utils.H.

Member Function Documentation

bft()

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

size_t Aleph::Breadth_First_Traversal< GT, Operation, SA >::bft ( const GT &  g, typename GT::Node *  start, Operation &  op  )

inlineprivate

Definition at line 419 of file tpl_graph_utils.H.

References ARC_BITS, Aleph::Breadth_First, Aleph::Breadth_First_Traversal< GT, Operation, SA >::count, Aleph::DynListQueue< T >::get(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), IS_ARC_VISITED, Aleph::DynListQueue< T >::is_empty(), IS_NODE_VISITED, Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_BITS, Aleph::DynListQueue< T >::put(), GraphCommon< GT, Node, Arc >::reset_bit_arcs(), GraphCommon< GT, Node, Arc >::reset_bit_nodes(), and Aleph::Breadth_First_Traversal< GT, Operation, SA >::sa.

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

operator()() [1/3]

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

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

inline

Traverse starting from the first node of the graph.

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

Side effects:

• Resets the Breadth_First control bit on all nodes and arcs.
• Uses the Breadth_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 489 of file tpl_graph_utils.H.

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

operator()() [2/3]

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

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

inline

Traverse starting from a given node.

Traverses the connected component reachable from p in breadth-first order.

Side effects:

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

Parameters

[in]	g	Graph to traverse.
[in]	p	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 509 of file tpl_graph_utils.H.

References Aleph::Breadth_First_Traversal< GT, Operation, SA >::bft().

operator()() [3/3]

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

size_t Aleph::Breadth_First_Traversal< GT, Operation, SA >::operator() ( const GT &  g, typename GT::Node *  p, Operation &  op  )

inline

Traverse starting from a given node (operation by reference).

Equivalent to the rvalue overload, but takes the operation by reference.

Parameters

[in]	g	Graph to traverse.
[in]	p	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 525 of file tpl_graph_utils.H.

References Aleph::Breadth_First_Traversal< GT, Operation, SA >::bft().

Member Data Documentation

count

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

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

private

Definition at line 417 of file tpl_graph_utils.H.

Referenced by Aleph::Breadth_First_Traversal< GT, Operation, SA >::bft().

sa

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

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

private

Definition at line 416 of file tpl_graph_utils.H.

Referenced by Aleph::Breadth_First_Traversal< GT, Operation, SA >::bft().

---

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

• tpl_graph_utils.H