Test whether a cycle is reachable from a given node. More...

#include <tpl_test_cycle.H>

Public Member Functions
	Test_For_Cycle (SA arc_filter=SA())
	Construct a cycle tester with optional arc filter.

bool	operator() (const GT &g, typename GT::Node *src_node) const
	Test whether a cycle is reachable from the given source node.

Private Member Functions
bool	test_cycle (typename GT::Node *curr) const

bool	test_cycle (const GT &g, typename GT::Node *s) const

Private Attributes
GT::Node *	src = nullptr

SA	sa

Detailed Description

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

Test whether a cycle is reachable from a given node.

The Test_For_Cycle class performs a depth-first search starting from a specified source node to detect whether there exists any path that returns to that source, forming a cycle.

This is a single-source cycle detection algorithm. It only checks for cycles reachable from the specified node. If the node is not part of any cycle, the algorithm returns false, even if the graph contains cycles elsewhere.

Algorithm:

The algorithm uses depth-first traversal with the following logic:

Mark all outgoing arcs from the source node
For each unmarked adjacent node, recursively explore its paths
If any path returns to the source node, a cycle is detected
Uses the Test_Cycle control bit to mark visited nodes and arcs

Complexity:

Time: O(V + E) where V is the number of nodes and E is the number of arcs reachable from the source node.
Space: O(V) for the recursion stack in the worst case.

Usage example:

Graph g;
auto n1 = g.insert_node(1);
auto n2 = g.insert_node(2);
auto n3 = g.insert_node(3);
g.insert_arc(n1, n2);
g.insert_arc(n2, n3);
 
Test_For_Cycle<Graph> cycle_test;
assert(!cycle_test(g, n1)); // No cycle yet
 
g.insert_arc(n3, n1); // Create triangle
assert(cycle_test(g, n1));  // Cycle detected

Warning: This algorithm modifies the Test_Cycle control bit on all visited nodes and arcs. If you need this bit for other purposes, save and restore it, or use a different algorithm.

Note: For undirected graphs, the algorithm correctly handles bidirectional edges by marking arcs as visited. This prevents false detection of trivial 2-cycles (e.g., going from A to B and back via the same edge).

Template Parameters

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

See also: test_for_cycle() Free function alternative in tpl_graph_utils.H; has_cycle() To check if any cycle exists in the graph; is_graph_acyclique() To verify the entire graph is acyclic

Definition at line 107 of file tpl_test_cycle.H.

Constructor & Destructor Documentation

◆ Test_For_Cycle()

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

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

inline

Construct a cycle tester with optional arc filter.

Parameters

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

Definition at line 187 of file tpl_test_cycle.H.

Member Function Documentation

◆ operator()()

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

bool Aleph::Test_For_Cycle< GT, SA >::operator()	(	const GT &	g,
		typename GT::Node *	src_node
	)		const

inline

Test whether a cycle is reachable from the given source node.

Performs a depth-first search starting from src_node to detect whether there exists any path that returns to src_node, forming a cycle.

Parameters

[in]	g	Graph to search (not modified, but control bits are used).
[in]	src_node	Source node to start the search from.

Returns: true if a cycle reachable from src_node is found; false otherwise.

Exceptions

std::invalid_argument if src_node is nullptr.

Note: This algorithm only verifies the existence of a cycle reachable from src_node. It does not return the cycle itself or any information about its composition.; The algorithm uses the Test_Cycle control bit on both nodes and arcs. These bits are reset at the beginning of the algorithm.