Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA > Class Template Reference

Tests Ore's sufficient condition for Hamiltonian graphs. More...

#include <hamiltonian.H>

Public Member Functions
	Test_Hamiltonian_Sufficiency (SN &&__sn=SN(), SA &&__sa=SA())
	Construct a Hamiltonian sufficiency tester.
bool	operator() (GT &g)
	Test if a graph satisfies Ore's Hamiltonian condition.

Private Member Functions
bool	are_adjacent (GT &g, typename GT::Node *src, typename GT::Node *tgt)
	Check if two nodes are adjacent in an undirected graph.
bool	test_graph (GT &g)
	Test Ore's condition for undirected graphs.
bool	has_arc (typename GT::Node *src, typename GT::Node *tgt)
	Check if arc src→tgt exists in a digraph.
bool	test_digraph (GT &g)
	Test Ore-like condition for directed graphs.

Private Attributes
SN &	sn
SA &	sa

Detailed Description

template<AlephGraph GT, NodeFilter< GT > SN = Dft_Show_Node<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
class Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >

Tests Ore's sufficient condition for Hamiltonian graphs.

This class tests whether a graph satisfies Ore's theorem, which provides a sufficient (but not necessary) condition for a graph to be Hamiltonian.

Ore's Theorem

For an undirected graph G with n ≥ 3 vertices: if for every pair of non-adjacent vertices u and v, deg(u) + deg(v) ≥ n, then G has a Hamiltonian cycle.

For directed graphs, the condition is extended to in-degree + out-degree.

Template Parameters

GT	Graph type (List_Graph, Array_Graph, etc.)
SN	Node filter for iteration (default: show all nodes)
SA	Arc filter for iteration (default: show all arcs)

Complexity

• Undirected: O(V²) - checks all pairs of non-adjacent vertices
• Directed: O(V² + E) - also counts in-degrees

Example

// Complete graph K5 satisfies Ore's condition
List_Graph<Node, Arc> k5;
// ... build K5 ...
 
Test_Hamiltonian_Sufficiency<decltype(k5)> test;
assert(test(k5) == true);  // All deg sums ≥ n for non-adjacent

Warning

A graph may be Hamiltonian without satisfying this condition. This is a sufficiency test only.

Author

Leandro R. León

Definition at line 132 of file hamiltonian.H.

Constructor & Destructor Documentation

Test_Hamiltonian_Sufficiency()

template<AlephGraph GT, NodeFilter< GT > SN = Dft_Show_Node<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::Test_Hamiltonian_Sufficiency ( SN &&  __sn = SN(), SA &&  __sa = SA()  )

inline

Construct a Hamiltonian sufficiency tester.

Parameters

__sn	Node filter (default: show all nodes)
__sa	Arc filter (default: show all arcs)

Definition at line 281 of file hamiltonian.H.

Member Function Documentation

are_adjacent()

template<AlephGraph GT, NodeFilter< GT > SN = Dft_Show_Node<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

bool Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::are_adjacent ( GT &  g, typename GT::Node *  src, typename GT::Node *  tgt  )

inlineprivate

Check if two nodes are adjacent in an undirected graph.

Parameters

[in]	g	The graph
[in]	src	First node
[in]	tgt	Second node

Returns

true if there is an edge between src and tgt

Definition at line 145 of file hamiltonian.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), and Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::sa.

Referenced by Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_graph().

has_arc()

template<AlephGraph GT, NodeFilter< GT > SN = Dft_Show_Node<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

bool Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::has_arc ( typename GT::Node *  src, typename GT::Node *  tgt  )

inlineprivate

Check if arc src→tgt exists in a digraph.

Parameters

src	Source node
tgt	Target node

Returns

true if arc src→tgt exists

Definition at line 208 of file hamiltonian.H.

References Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), and Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::sa.

Referenced by Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_digraph().

operator()()

template<AlephGraph GT, NodeFilter< GT > SN = Dft_Show_Node<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

bool Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::operator() ( GT &  g )

inline

Test if a graph satisfies Ore's Hamiltonian condition.

Automatically detects directed vs undirected and applies the appropriate test.

Parameters

g	Graph to test

Returns

true if Ore's sufficient condition is satisfied

Note

Returns true only guarantees the graph IS Hamiltonian. Returns false does NOT mean it isn't Hamiltonian.

Definition at line 299 of file hamiltonian.H.

References GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_digraph(), and test_graph().

test_digraph()

template<AlephGraph GT, NodeFilter< GT > SN = Dft_Show_Node<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

bool Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_digraph ( GT &  g )

inlineprivate

Test Ore-like condition for directed graphs.

For digraphs, checks that for each pair (u,v) without arc u→v: out-deg(u) + in-deg(v) ≥ n

This is based on Ghouila-Houri's theorem extension for digraphs.

Parameters

g	Directed graph to test

Returns

true if the digraph version of Ore's condition is satisfied

Definition at line 227 of file hamiltonian.H.

References Aleph::blossom_maximum_cardinality_matching(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::has_arc(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COUNTER, GraphCommon< GT, Node, Arc >::reset_counter_nodes(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::sa, and Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::sn.

Referenced by Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::operator()().

test_graph()

template<AlephGraph GT, NodeFilter< GT > SN = Dft_Show_Node<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

bool Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_graph ( GT &  g )

inlineprivate

Test Ore's condition for undirected graphs.

Checks that for all pairs of NON-ADJACENT vertices u, v: deg(u) + deg(v) ≥ n

Parameters

g	Undirected graph to test

Returns

true if Ore's condition is satisfied

Definition at line 164 of file hamiltonian.H.

References Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::are_adjacent(), Aleph::blossom_maximum_cardinality_matching(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), and Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::sn.

Member Data Documentation

sa

template<AlephGraph GT, NodeFilter< GT > SN = Dft_Show_Node<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

SA& Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::sa

private

Definition at line 135 of file hamiltonian.H.

Referenced by Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::are_adjacent(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::has_arc(), and Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_digraph().

sn

template<AlephGraph GT, NodeFilter< GT > SN = Dft_Show_Node<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

SN& Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::sn

private

Definition at line 134 of file hamiltonian.H.

Referenced by Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_digraph(), and Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_graph().

---

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

• hamiltonian.H