Computes dominator tree and dominance frontiers of a digraph using the Lengauer-Tarjan algorithm. More...

#include <Dominators.H>

Inheritance diagram for Aleph::Lengauer_Tarjan_Dominators< GT, SA >:

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

Public Member Functions
	Lengauer_Tarjan_Dominators (SA __sa=SA()) noexcept
	Construct a dominator computation instance.

	Lengauer_Tarjan_Dominators (const Lengauer_Tarjan_Dominators &)=delete
	Dominator instances should not be copied (they hold internal state)

Lengauer_Tarjan_Dominators &	operator= (const Lengauer_Tarjan_Dominators &)=delete

	Lengauer_Tarjan_Dominators (Lengauer_Tarjan_Dominators &&)=default
	Move is allowed.

Lengauer_Tarjan_Dominators &	operator= (Lengauer_Tarjan_Dominators &&)=default

DynList< std::pair< Node , Node > >	compute_idom (GT &g, Node *root)
	Compute immediate dominators.

void	build_tree (GT &g, Node *root, GT &tree)
	Build the dominator tree as a separate graph.

Node *	get_idom (GT &g, Node root, Node node)
	Get the immediate dominator of a specific node.

bool	dominates (GT &g, Node root, Node d, Node *v)
	Test whether node d dominates node v.

DynMapTree< Node , DynSetTree< Node > >	dominance_frontiers (GT &g, Node *root)
	Compute dominance frontiers for all reachable nodes.

void	operator() (GT &g, Node *root, GT &tree)
	Build dominator tree (operator() alias).

Accessors
SA &	get_filter () noexcept
	Get the arc filter.

const SA &	get_filter () const noexcept
	Get the arc filter (const).

bool	has_computation () const noexcept
	Check if a computation has been performed.

GT *	get_graph () const noexcept
	Get the graph of the last computation.

Node *	get_root () const noexcept
	Get the root of the last computation.

long	get_num_reachable () const noexcept
	Get the number of reachable nodes in the last computation.

Private Types
using	Node = typename GT::Node

using	Arc = typename GT::Arc

Private Member Functions
void	compress (long v)
	Path compression for Union-Find (iterative).

void	dfs (Node *root_ptr)
	Iterative DFS to number nodes and build DFS tree.

long	eval (const long v)
	EVAL operation for the Union-Find forest.

void	do_compute (GT &g, Node *root)
	Core computation of dominators.

void	ensure_computed (GT &g, Node *root)
	Ensure computation is up to date.

Private Attributes
SA	sa

GT *	gptr = nullptr

Node *	root_ptr = nullptr

bool	is_computed = false

long	num_reachable = 0

Array< Node * >	vertex

Array< long >	par

Array< long >	semi

Array< long >	idom_arr

Array< long >	anc

Array< long >	label_arr

Array< DynList< long > >	pred

Detailed Description

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
class Aleph::Lengauer_Tarjan_Dominators< GT, SA >

Computes dominator tree and dominance frontiers of a digraph using the Lengauer-Tarjan algorithm.

This class implements the Lengauer-Tarjan algorithm for computing immediate dominators in a directed graph from a given root node. The algorithm runs in O(E * alpha(V)) time using a Union-Find structure with path compression.

The class caches its computation: calling multiple methods with the same graph and root reuses the previous result without recomputing.

Template Parameters

GT	The directed graph type.
SA	Arc filter class for the internal iterator. Defaults to Dft_Show_Arc<GT> which shows all arcs.

Note: This class uses NODE_COUNTER on graph nodes internally. After computation, node counters contain DFS numbers.; The graph must be a digraph. Behavior on undirected graphs is undefined.

Warning: This class is NOT thread-safe.

See also: Tarjan_Connected_Components

Definition at line 149 of file Dominators.H.

Member Typedef Documentation

◆ Arc

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

using Aleph::Lengauer_Tarjan_Dominators< GT, SA >::Arc = typename GT::Arc

private

Definition at line 154 of file Dominators.H.

◆ Node

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

using Aleph::Lengauer_Tarjan_Dominators< GT, SA >::Node = typename GT::Node

private

Definition at line 153 of file Dominators.H.

Constructor & Destructor Documentation

◆ Lengauer_Tarjan_Dominators() [1/3]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Lengauer_Tarjan_Dominators< GT, SA >::Lengauer_Tarjan_Dominators ( SA __sa = SA() )

inlinenoexcept

Construct a dominator computation instance.

Parameters

__sa	Arc filter functor. Defaults to Dft_Show_Arc<GT>.

Definition at line 392 of file Dominators.H.

◆ Lengauer_Tarjan_Dominators() [2/3]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Lengauer_Tarjan_Dominators< GT, SA >::Lengauer_Tarjan_Dominators ( const Lengauer_Tarjan_Dominators< GT, SA > & )

delete

Dominator instances should not be copied (they hold internal state)

◆ Lengauer_Tarjan_Dominators() [3/3]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Lengauer_Tarjan_Dominators< GT, SA >::Lengauer_Tarjan_Dominators ( Lengauer_Tarjan_Dominators< GT, SA > && )

default

Move is allowed.

Member Function Documentation

◆ build_tree()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Lengauer_Tarjan_Dominators< GT, SA >::build_tree	(	GT &	g,
		Node *	root,
		GT &	tree
	)

inline

Build the dominator tree as a separate graph.

Creates a new directed graph tree where each reachable node from the original graph is represented, and arcs go from idom to child. Nodes are mapped via NODE_COOKIE between the original graph and the tree (bidirectional mapping via GT::map_nodes).

Parameters

	g	The directed graph.
	root	Root node.
[out]	tree	Output dominator tree (cleared first).

Exceptions

std::domain_error If root is null.

Definition at line 443 of file Dominators.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::clear_graph(), Aleph::Lengauer_Tarjan_Dominators< GT, SA >::ensure_computed(), Aleph::Lengauer_Tarjan_Dominators< GT, SA >::idom_arr, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::Lengauer_Tarjan_Dominators< GT, SA >::num_reachable, root(), and Aleph::Lengauer_Tarjan_Dominators< GT, SA >::vertex.

Referenced by main(), and TEST().

◆ compress()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Lengauer_Tarjan_Dominators< GT, SA >::compress ( long v )

inlineprivate

Path compression for Union-Find (iterative).

Updates label[v] to hold the node with the minimum semi-dominator on the path from v to the tree root in the current forest.

Parameters

v	The node (DFS number) to compress.

Definition at line 178 of file Dominators.H.

References Aleph::Lengauer_Tarjan_Dominators< GT, SA >::anc, Aleph::and, Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Array< T >::is_empty(), Aleph::Lengauer_Tarjan_Dominators< GT, SA >::label_arr, Aleph::Array< T >::remove_last(), root(), and Aleph::Lengauer_Tarjan_Dominators< GT, SA >::semi.

Referenced by Aleph::Lengauer_Tarjan_Dominators< GT, SA >::eval().

◆ compute_idom()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

DynList< std::pair< Node , Node > > Aleph::Lengauer_Tarjan_Dominators< GT, SA >::compute_idom	(	GT &	g,
		Node *	root
	)

inline

Compute immediate dominators.

Returns a list of (node, idom) pairs for every node reachable from the root. The root's idom is nullptr.

Parameters

g	The directed graph.
root	Root node for dominator computation.

Returns: List of (node, immediate_dominator) pairs.

Exceptions

std::domain_error If root is null.

Definition at line 418 of file Dominators.H.

References Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Lengauer_Tarjan_Dominators< GT, SA >::ensure_computed(), Aleph::Lengauer_Tarjan_Dominators< GT, SA >::idom_arr, Aleph::Lengauer_Tarjan_Dominators< GT, SA >::num_reachable, root(), and Aleph::Lengauer_Tarjan_Dominators< GT, SA >::vertex.

Referenced by main().

◆ dfs()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Lengauer_Tarjan_Dominators< GT, SA >::dfs ( Node * root_ptr )

inlineprivate

Iterative DFS to number nodes and build DFS tree.

Parameters

root_ptr Root node pointer.

Definition at line 207 of file Dominators.H.

Referenced by Aleph::Lengauer_Tarjan_Dominators< GT, SA >::do_compute().

◆ do_compute()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Lengauer_Tarjan_Dominators< GT, SA >::do_compute	(	GT &	g,
		Node *	root
	)

inlineprivate

Core computation of dominators.

Performs DFS from root, computes semi-dominators in reverse DFS order using the Union-Find forest, then resolves immediate dominators in a forward pass.

Parameters

g	The directed graph.
root	The root node for dominator computation.

Definition at line 278 of file Dominators.H.

Referenced by Aleph::Lengauer_Tarjan_Dominators< GT, SA >::ensure_computed().

◆ dominance_frontiers()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

DynMapTree< Node , DynSetTree< Node > > Aleph::Lengauer_Tarjan_Dominators< GT, SA >::dominance_frontiers	(	GT &	g,
		Node *	root
	)

inline

Compute dominance frontiers for all reachable nodes.

The dominance frontier DF(x) of a node x is the set of nodes y where x dominates a predecessor of y but does not strictly dominate y. This is the key data structure for placing phi-functions in SSA form.

Uses the standard algorithm: for each join point (node with 2+ predecessors), walk up from each predecessor to its idom, adding the join point to each visited node's frontier.

Parameters