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

#include <tpl_spanning_tree.H>

Collaboration diagram for Aleph::Find_Depth_First_Spanning_Tree< GT, SA >:

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

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

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

Private Member Functions
bool	build_tree (typename GT::Node gnode, typename GT::Arc garc, typename GT::Node *tnode)

bool	build_tree (GT &g, typename GT::Node *gnode, GT &tree)

Private Attributes
SA	sa

GT *	gptr = nullptr

GT *	tptr = nullptr

Detailed Description

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

Compute a depth-first spanning tree of a graph.

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

A spanning tree is a subgraph that includes all vertices of the original graph connected by the minimum number of edges (V-1 edges for V vertices) without forming any cycles.

Algorithm:

Start from a source node and mark it as visited
For each unvisited adjacent node, recursively build the tree
Copy visited nodes and traversed arcs to the output tree
Maintain node/arc mappings between original graph and tree

Complexity:

Time: O(V + E) where V is vertices and E is edges
Space: O(V) for recursion stack + 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_Depth_First_Spanning_Tree<decltype(g)> dfs_tree;
auto root = dfs_tree(g, tree);
 
if (root != nullptr)
  std::cout << "Spanning tree has " << tree.get_num_nodes() << " nodes\n";

Note: The algorithm uses the Spanning_Tree control bit on nodes and arcs. These bits are reset at the beginning of the algorithm.; After execution, nodes and arcs in tree are mapped to their corresponding elements in g via cookies.

Template Parameters

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

See also: Find_Breadth_First_Spanning_Tree For BFS-based spanning tree; graph_to_tree_node() To convert to Tree_Node representation

Definition at line 111 of file tpl_spanning_tree.H.

Constructor & Destructor Documentation

◆ Find_Depth_First_Spanning_Tree()

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

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

inline

Construct a DFS 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 209 of file tpl_spanning_tree.H.

Member Function Documentation

◆ build_tree() [1/2]

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

bool Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::build_tree	(	GT &	g,
		typename GT::Node *	gnode,
		GT &	tree
	)

inlineprivate

Definition at line 163 of file tpl_spanning_tree.H.

References build_tree(), Aleph::clear_graph(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::gptr, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_ARC_VISITED, IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), NODE_BITS, GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::sa, Aleph::Spanning_Tree, and Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::tptr.

◆ build_tree() [2/2]

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

bool Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::build_tree	(	typename GT::Node *	gnode,
		typename GT::Arc *	garc,
		typename GT::Node *	tnode
	)

inlineprivate

Definition at line 118 of file tpl_spanning_tree.H.

References ARC_BITS, build_tree(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::gptr, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_ARC_VISITED, IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_arcs(), GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), NODE_BITS, Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::sa, Aleph::Spanning_Tree, and Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::tptr.

◆ operator()() [1/2]

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

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

inline

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

Constructs a spanning tree of the graph using depth-first traversal. After execution, tree contains the spanning tree with nodes and arcs mapped to their corresponding elements in g.

Parameters

[in]	g	Source graph to compute spanning tree from.
[out]	tree	Output graph that will contain the spanning tree. Will be cleared before construction.

Returns: Pointer to the root node (first node of g) if the graph is connected and a spanning tree exists; nullptr otherwise.

Exceptions

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

Note: Uses the Spanning_Tree control bit on nodes and arcs.

Definition at line 229 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(), and Aleph::maps().

◆ operator()() [2/2]

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

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

inline

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

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

Parameters

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