Compute a breadth-first spanning tree of a graph. More...

#include <tpl_spanning_tree.H>

Public Member Functions
	Find_Breadth_First_Spanning_Tree (SA arc_filter=SA())
	Construct a BFS spanning tree builder with optional arc filter.

void	operator() (GT &g, typename GT::Node *gnode, GT &tree)
	Build a breadth-first spanning tree starting from a specific node.

GT::Node *	operator() (GT &g, GT &tree)
	Build a breadth-first spanning tree starting from the first node.

Private Member Functions
void	build_tree (GT &g, typename GT::Node *gp, GT &tree)

Private Attributes
SA	sa

Detailed Description

template<class GT, class SA = Dft_Show_Arc<GT>>
class Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >

Compute a breadth-first spanning tree of a graph.

This class performs a breadth-first traversal starting from a specified node and constructs the spanning tree according to the BFS visit order.

Unlike DFS spanning trees, BFS spanning trees have the property that the path from the root to any node in the tree is the shortest path (in terms of number of edges) in the original graph.

Algorithm:

Start from a source node and add its adjacent arcs to a queue
Process arcs from the queue, adding unvisited nodes to the tree
For each newly added node, enqueue its adjacent arcs
Continue until all reachable nodes are visited

Complexity:

Time: O(V + E) where V is vertices and E is edges
Space: O(V) for the queue + O(V + E) for output tree

Usage example:

List_Graph<Graph_Node<int>, Graph_Arc<int>> g;
// ... populate graph ...
 
List_Graph<Graph_Node<int>, Graph_Arc<int>> tree;
Find_Breadth_First_Spanning_Tree<decltype(g)> bfs_tree;
auto start = g.get_first_node();
bfs_tree(g, start, tree);

Note: The algorithm uses the Spanning_Tree control bit on nodes and arcs.

Template Parameters

GT	Graph type (must satisfy Aleph graph concept).
SA	Arc filter type (default: `Dft_Show_Arc<GT>`).

Exceptions

std::bad_alloc If memory allocation fails for tree or internal queue.

See also: Find_Depth_First_Spanning_Tree For DFS-based spanning tree

Definition at line 314 of file tpl_spanning_tree.H.

Constructor & Destructor Documentation

◆ Find_Breadth_First_Spanning_Tree()

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

Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::Find_Breadth_First_Spanning_Tree ( SA arc_filter = SA() )

inline

Construct a BFS spanning tree builder with optional arc filter.

Parameters

arc_filter Arc filter to control which arcs are traversed (default: show all arcs).

Definition at line 395 of file tpl_spanning_tree.H.

Member Function Documentation

◆ build_tree()

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

void Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::build_tree	(	GT &	g,
		typename GT::Node *	gp,
		GT &	tree
	)

inlineprivate

Definition at line 319 of file tpl_spanning_tree.H.

References ARC_BITS, Aleph::clear_graph(), 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(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_ARC_VISITED, Aleph::DynListQueue< T >::is_empty(), IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_arcs(), GraphCommon< GT, Node, Arc >::map_nodes(), 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(), Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::sa, and Aleph::Spanning_Tree.

◆ operator()() [1/2]

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

GT::Node * Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::operator()	(	GT &	g,
		GT &	tree
	)

inline

Build a breadth-first spanning tree starting from the first node.

Constructs a spanning tree using the first node of the graph as root.

Parameters

[in]	g	Source graph to compute spanning tree from.
[out]	tree	Output graph that will contain the spanning tree.

Returns: Pointer to the tree node corresponding to the root.

Exceptions

std::bad_alloc	If memory allocation fails.
std::domain_error	If the graph is empty.

Definition at line 434 of file tpl_spanning_tree.H.

References ah_domain_error_if, build_tree(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), and NODE_COOKIE.

◆ operator()() [2/2]

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

void Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::operator()	(	GT &	g,
		typename GT::Node *	gnode,
		GT &	tree
	)

inline

Build a breadth-first spanning tree starting from a specific node.

Constructs a spanning tree of the graph using breadth-first traversal starting from the specified source node.

Parameters

[in]	g	Source graph to compute spanning tree from.
[in]	gnode	Starting node for the BFS traversal.
[out]	tree	Output graph that will contain the spanning tree. Will be cleared before construction.

Exceptions

std::bad_alloc	If memory allocation fails.
std::invalid_argument	If `gnode` is `nullptr`.

Note: Uses the Spanning_Tree control bit on nodes and arcs.; After execution, nodes and arcs in tree are mapped to their corresponding elements in g via cookies.

Definition at line 414 of file tpl_spanning_tree.H.

References ah_invalid_argument_if, build_tree(), and Aleph::maps().