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

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

#include <hamiltonian.H>

Public Member Functions
	Test_Dirac_Condition (SN &&__sn=SN(), SA &&__sa=SA())
	Construct a Dirac condition tester.
bool	operator() (GT &g)
	Test if a graph satisfies Dirac's Hamiltonian condition.
size_t	min_required_degree (GT &g) const
	Get the minimum degree required by Dirac's condition.
std::pair< size_t, typename GT::Node * >	find_min_degree_vertex (GT &g)
	Find the vertex with minimum degree.

Private Member Functions
bool	test_graph (GT &g)
	Test Dirac's condition for undirected graphs.
bool	test_digraph (GT &g)
	Test Dirac-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_Dirac_Condition< GT, SN, SA >

Tests Dirac's sufficient condition for Hamiltonian graphs.

Dirac's theorem provides a simpler sufficient condition than Ore's: For an undirected simple graph G with n ≥ 3 vertices, if deg(v) ≥ n/2 for every vertex v, then G is Hamiltonian.

Comparison with Ore's Theorem

Property	Dirac	Ore
Complexity	O(V)	O(V²)
Condition	deg(v) ≥ n/2 for all v	deg(u)+deg(v) ≥ n for non-adjacent
Strictness	More restrictive	Less restrictive

Note

Dirac's condition implies Ore's condition, but not vice versa. A graph satisfying Dirac's condition also satisfies Ore's.

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)

Example

List_Graph<Node, Arc> g;
// Build complete graph K5 (each vertex has degree 4 ≥ 5/2)
// ...
 
Test_Dirac_Condition<decltype(g)> test;
if (test(g))
  std::cout << "Graph satisfies Dirac's condition (is Hamiltonian)\n";

Warning

This tests sufficiency, not necessity. A graph may be Hamiltonian without satisfying Dirac's condition.

Author

Leandro R. León

Definition at line 350 of file hamiltonian.H.

Constructor & Destructor Documentation

Test_Dirac_Condition()

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

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

inline

Construct a Dirac condition tester.

Parameters

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

Definition at line 433 of file hamiltonian.H.

Member Function Documentation

find_min_degree_vertex()

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

std::pair< size_t, typename GT::Node * > Aleph::Test_Dirac_Condition< GT, SN, SA >::find_min_degree_vertex ( GT &  g )

inline

Find the vertex with minimum degree.

Useful for understanding why a graph fails Dirac's condition.

Parameters

g

The graph

Returns

Pair of (minimum degree found, the vertex with that degree)

Definition at line 474 of file hamiltonian.H.

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

min_required_degree()

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

size_t Aleph::Test_Dirac_Condition< GT, SN, SA >::min_required_degree ( GT &  g ) const

inline

Get the minimum degree required by Dirac's condition.

Parameters

g

The graph

Returns

The minimum degree required (⌈n/2⌉)

Definition at line 461 of file hamiltonian.H.

References GraphCommon< GT, Node, Arc >::get_num_nodes().

Referenced by demo_dirac().

operator()()

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

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

inline

Test if a graph satisfies Dirac's Hamiltonian condition.

Parameters

g	Graph to test

Returns

true if deg(v) ≥ n/2 for all vertices

Note

This is faster than Ore's test: O(V) vs O(V²)

Definition at line 447 of file hamiltonian.H.

References GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::Test_Dirac_Condition< 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_Dirac_Condition< GT, SN, SA >::test_digraph ( GT &  g )

inlineprivate

Test Dirac-like condition for directed graphs.

For digraphs, checks that min(out-deg, in-deg) ≥ n/2 for all vertices. This is a generalization of Dirac's theorem for directed graphs.

Parameters

g	Directed graph to test

Returns

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

Definition at line 393 of file hamiltonian.H.

References 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(), NODE_COUNTER, GraphCommon< GT, Node, Arc >::reset_counter_nodes(), Aleph::Test_Dirac_Condition< GT, SN, SA >::sa, and Aleph::Test_Dirac_Condition< GT, SN, SA >::sn.

Referenced by Aleph::Test_Dirac_Condition< 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_Dirac_Condition< GT, SN, SA >::test_graph ( GT &  g )

inlineprivate

Test Dirac's condition for undirected graphs.

Checks that deg(v) ≥ n/2 for all vertices v.

Parameters

g	Undirected graph to test

Returns

true if Dirac's condition is satisfied

Definition at line 363 of file hamiltonian.H.

References 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_Dirac_Condition< 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_Dirac_Condition< GT, SN, SA >::sa

private

Definition at line 353 of file hamiltonian.H.

Referenced by Aleph::Test_Dirac_Condition< 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_Dirac_Condition< GT, SN, SA >::sn

private

Definition at line 352 of file hamiltonian.H.

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

---

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

• hamiltonian.H