Tests whether a graph or digraph is Eulerian. More...

#include <eulerian.H>

Public Member Functions
	Test_Eulerian (SN &&__sn=SN(), SA &&__sa=SA())
	Construct an Eulerian tester with optional filters.

Eulerian_Type	compute (GT &g)
	Compute detailed Eulerian classification.

bool	operator() (GT &g)
	Test if a graph has an Eulerian cycle.

bool	has_eulerian_path (GT &g)
	Test if a graph has an Eulerian path.

bool	test_degree_only (GT &g)
	Check only degree conditions (without connectivity check).

Private Member Functions
bool	is_connected (GT &g)
	Check connectivity of undirected graph using DFS.

bool	is_strongly_connected (GT &g)
	Check strong connectivity of digraph using Kosaraju-like approach.

Eulerian_Type	analyze_graph (GT &g)
	Analyze Eulerian properties of an undirected graph.

Eulerian_Type	analyze_digraph (GT &g)
	Analyze Eulerian properties of a directed graph.

Private Attributes
SN &	sn

SA &	sa

Detailed Description

template<class GT, class SN = Dft_Show_Node<GT>, class SA = Dft_Show_Arc<GT>>
class Aleph::Test_Eulerian< GT, SN, SA >

Tests whether a graph or digraph is Eulerian.

A graph is Eulerian if it contains an Eulerian cycle (a cycle that visits every edge exactly once). This class tests the necessary and sufficient conditions for Eulerian graphs.

Conditions Tested

Undirected graphs:

Eulerian cycle: All vertices have even degree AND graph is connected
Eulerian path: Exactly 2 vertices have odd degree AND graph is connected

Directed graphs:

Eulerian cycle: in-degree == out-degree for all vertices AND strongly connected
Eulerian path: At most one vertex with out-in=1, at most one with in-out=1

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

Time: O(V + E) including connectivity check
Space: O(V) for connectivity check

Example: List_Graph<Node, Arc> g;

// Build a graph where all vertices have even degree

auto n1 = g.insert_node();

auto n2 = g.insert_node();

auto n3 = g.insert_node();

g.insert_arc(n1, n2);

g.insert_arc(n2, n3);

g.insert_arc(n3, n1); // Triangle - all degrees are 2

Test_Eulerian<decltype(g)> test;

assert(test(g) == true); // Graph is Eulerian

// Or use detailed result:

assert(test.compute(g) == Eulerian_Type::Cycle);

Aleph::List_Graph
Graph implemented with double-linked adjacency lists.
Definition tpl_graph.H:428

Aleph::List_Graph::insert_node
virtual Node * insert_node(Node *node) noexcept
Insertion of a node already allocated.
Definition tpl_graph.H:524

Aleph::List_Graph::insert_arc
Arc * insert_arc(Node *src_node, Node *tgt_node, void *a)
Definition tpl_graph.H:604

Aleph::Test_Eulerian
Tests whether a graph or digraph is Eulerian.
Definition eulerian.H:171

Aleph::Eulerian_Type::Cycle
@ Cycle
Graph has an Eulerian cycle.

Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693

test
void test(unsigned long n, gsl_rng *r)
Definition timeAllTree.C:318

See also: hamiltonian.H For Hamiltonian path/cycle testing; tpl_test_connectivity.H For connectivity testing

Author: Leandro R. León

Definition at line 170 of file eulerian.H.

Constructor & Destructor Documentation

◆ Test_Eulerian()

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

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

inline

Construct an Eulerian tester with optional filters.

Parameters

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

Definition at line 413 of file eulerian.H.

Member Function Documentation

◆ analyze_digraph()

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

Eulerian_Type Aleph::Test_Eulerian< GT, SN, SA >::analyze_digraph ( GT & g )

inlineprivate

Analyze Eulerian properties of a directed graph.

Parameters

g	The directed graph to test

Returns: Eulerian_Type classification

Definition at line 349 of file eulerian.H.

References Aleph::Cycle, Aleph::diff(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::Test_Eulerian< GT, SN, SA >::is_strongly_connected(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COUNTER, Aleph::None, Aleph::Path, GraphCommon< GT, Node, Arc >::reset_counter_nodes(), Aleph::Test_Eulerian< GT, SN, SA >::sa, and Aleph::Test_Eulerian< GT, SN, SA >::sn.

Referenced by Aleph::Test_Eulerian< GT, SN, SA >::compute().

◆ analyze_graph()

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

Eulerian_Type Aleph::Test_Eulerian< GT, SN, SA >::analyze_graph ( GT & g )

inlineprivate

Analyze Eulerian properties of an undirected graph.

Parameters

g	The undirected graph to test

Returns: Eulerian_Type classification

Definition at line 307 of file eulerian.H.

References Aleph::Cycle, GraphCommon< GT, Node, Arc >::get_num_arcs(), Aleph::Test_Eulerian< GT, SN, SA >::is_connected(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::None, Aleph::Path, and Aleph::Test_Eulerian< GT, SN, SA >::sn.

Referenced by Aleph::Test_Eulerian< GT, SN, SA >::compute().

◆ compute()

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

Eulerian_Type Aleph::Test_Eulerian< GT, SN, SA >::compute ( GT & g )

inline

Compute detailed Eulerian classification.

Determines whether the graph has an Eulerian cycle, path, or neither. This method checks both degree conditions AND connectivity.

Parameters

g	The graph to test

Returns: Eulerian_Type classification (Cycle, Path, or None)

Example: Test_Eulerian<decltype(g)> test;

auto result = test.compute(g);

if (result == Eulerian_Type::Cycle)

std::cout << "Has Eulerian cycle\n";

Aleph::Test_Eulerian::compute
Eulerian_Type compute(GT &g)
Compute detailed Eulerian classification.
Definition eulerian.H:436

Definition at line 436 of file eulerian.H.

References Aleph::Test_Eulerian< GT, SN, SA >::analyze_digraph(), Aleph::Test_Eulerian< GT, SN, SA >::analyze_graph(), and GraphCommon< GT, Node, Arc >::is_digraph().

Referenced by Aleph::Test_Eulerian< GT, SN, SA >::has_eulerian_path(), and Aleph::Test_Eulerian< GT, SN, SA >::operator()().

◆ has_eulerian_path()

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

bool Aleph::Test_Eulerian< GT, SN, SA >::has_eulerian_path ( GT & g )

inline

Test if a graph has an Eulerian path.

An Eulerian path visits every edge exactly once but may not return to the starting vertex.

Parameters

g	The graph to test

Returns: true if the graph contains an Eulerian path (cycle or path)

Note: Returns true for graphs with Eulerian cycles too.

Definition at line 472 of file eulerian.H.

References Aleph::Test_Eulerian< GT, SN, SA >::compute(), Aleph::Cycle, and Aleph::Path.

◆ is_connected()

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

bool Aleph::Test_Eulerian< GT, SN, SA >::is_connected ( GT & g )

inlineprivate

Check connectivity of undirected graph using DFS.

Only considers vertices with degree > 0 (isolated vertices don't affect Eulerian properties).

Parameters

g	The undirected graph

Returns: true if all non-isolated vertices are connected

Definition at line 184 of file eulerian.H.

References Aleph::Depth_First, GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_BITS, Aleph::DynList< T >::remove_first(), GraphCommon< GT, Node, Arc >::reset_nodes(), Aleph::Test_Eulerian< GT, SN, SA >::sa, and Aleph::Test_Eulerian< GT, SN, SA >::sn.

Referenced by Aleph::Test_Eulerian< GT, SN, SA >::analyze_graph().

◆ is_strongly_connected()

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

bool Aleph::Test_Eulerian< GT, SN, SA >::is_strongly_connected ( GT & g )

inlineprivate

Check strong connectivity of digraph using Kosaraju-like approach.

For Eulerian cycle in digraph, we need strong connectivity among vertices with edges.

Parameters

g	The directed graph

Returns: true if all non-isolated vertices are strongly connected

Definition at line 244 of file eulerian.H.

References Aleph::Depth_First, GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_BITS, NODE_COUNTER, Aleph::DynList< T >::remove_first(), GraphCommon< GT, Node, Arc >::reset_nodes(), Aleph::Test_Eulerian< GT, SN, SA >::sa, and Aleph::Test_Eulerian< GT, SN, SA >::sn.

Referenced by Aleph::Test_Eulerian< GT, SN, SA >::analyze_digraph().

◆ operator()()

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

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

inline

Test if a graph has an Eulerian cycle.

Automatically detects whether the graph is directed or undirected and applies the appropriate test. This method checks both degree conditions AND connectivity.

Parameters