Finds and constructs an Eulerian path or cycle using Hierholzer's algorithm. More...

#include <eulerian.H>

Classes
struct	Result
	Result type: path and its classification. More...

Public Member Functions
	Find_Eulerian_Path (SN &&__sn=SN(), SA &&__sa=SA())
	Construct an Eulerian path finder with optional filters.

Result	operator() (GT &g)
	Find an Eulerian path or cycle in the graph.

DynList< typename GT::Arc * >	find_path (GT &g)
	Get only the arc list (convenience method).

DynList< typename GT::Node * >	find_node_sequence (GT &g)
	Get the node sequence of the Eulerian path/cycle.

Private Member Functions
GT::Node *	find_start_vertex (GT &g, Eulerian_Type type)
	Find starting vertex for Eulerian path/cycle.

DynList< typename GT::Arc * >	hierholzer_undirected (GT &g, typename GT::Node *start)
	Hierholzer's algorithm for undirected graphs.

DynList< typename GT::Arc * >	hierholzer_directed (GT &g, typename GT::Node *start)
	Hierholzer's algorithm for directed graphs.

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::Find_Eulerian_Path< GT, SN, SA >

Finds and constructs an Eulerian path or cycle using Hierholzer's algorithm.

Hierholzer's algorithm efficiently constructs an Eulerian path or cycle in O(E) time. It works by:

Starting at an appropriate vertex (odd-degree for path, any for cycle)
Following edges until returning to start or getting stuck
Splicing in sub-tours from vertices with unused edges

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(E)
Space: O(E) for storing the path

Example: List_Graph<Node, Arc> g;

// Build triangle

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);

Find_Eulerian_Path<decltype(g)> finder;

auto [path, type] = finder(g);

if (type == Eulerian_Type::Cycle)

for (auto arc : path)

// Process arc...

Aleph::Find_Eulerian_Path
Finds and constructs an Eulerian path or cycle using Hierholzer's algorithm.
Definition eulerian.H:561

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::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

Author: Leandro R. León

Definition at line 560 of file eulerian.H.

Constructor & Destructor Documentation

◆ Find_Eulerian_Path()

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

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

inline

Construct an Eulerian path finder with optional filters.

Parameters

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

Definition at line 754 of file eulerian.H.

Member Function Documentation

◆ find_node_sequence()

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

DynList< typename GT::Node * > Aleph::Find_Eulerian_Path< GT, SN, SA >::find_node_sequence ( GT & g )

inline

Get the node sequence of the Eulerian path/cycle.

Parameters

g The graph

Returns: List of nodes in traversal order, empty if no path exists

Definition at line 833 of file eulerian.H.

References Aleph::Dlink::append(), Aleph::Find_Eulerian_Path< GT, SN, SA >::find_start_vertex(), GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::DynList< T >::get_first(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::HTList::is_empty(), Aleph::maps(), nodes, Aleph::None, Aleph::Find_Eulerian_Path< GT, SN, SA >::Result::path, and Aleph::Find_Eulerian_Path< GT, SN, SA >::Result::type.

◆ find_path()

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

DynList< typename GT::Arc * > Aleph::Find_Eulerian_Path< GT, SN, SA >::find_path ( GT & g )

inline

Get only the arc list (convenience method).

Parameters

g	The graph to search

Returns: List of arcs in Eulerian order, empty if none exists

Definition at line 822 of file eulerian.H.

◆ find_start_vertex()

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

GT::Node * Aleph::Find_Eulerian_Path< GT, SN, SA >::find_start_vertex	(	GT &	g,
		Eulerian_Type	type
	)

inlineprivate

Find starting vertex for Eulerian path/cycle.

For cycles: any vertex with edges For paths: a vertex with odd degree (undirected) or out-in=1 (directed)

Parameters

g	The graph
type	The Eulerian type (Cycle or Path)

Returns: Starting vertex, or nullptr if graph has no edges

Definition at line 575 of file eulerian.H.

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

Referenced by Aleph::Find_Eulerian_Path< GT, SN, SA >::find_node_sequence(), and Aleph::Find_Eulerian_Path< GT, SN, SA >::operator()().

◆ hierholzer_directed()

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

DynList< typename GT::Arc * > Aleph::Find_Eulerian_Path< GT, SN, SA >::hierholzer_directed	(	GT &	g,
		typename GT::Node *	start
	)

inlineprivate

Hierholzer's algorithm for directed graphs.

Parameters

g	The directed graph
start	Starting vertex

Returns: List of arcs forming the Eulerian path/cycle

Definition at line 691 of file eulerian.H.

References ARC_BITS, Aleph::Depth_First, Aleph::DynList< T >::get_first(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynList< T >::insert(), IS_ARC_VISITED, Aleph::HTList::is_empty(), Aleph::maps(), Aleph::next(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::DynList< T >::remove_first(), GraphCommon< GT, Node, Arc >::reset_arcs(), and Aleph::Find_Eulerian_Path< GT, SN, SA >::sa.

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

◆ hierholzer_undirected()

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

DynList< typename GT::Arc * > Aleph::Find_Eulerian_Path< GT, SN, SA >::hierholzer_undirected	(	GT &	g,
		typename GT::Node *	start
	)

inlineprivate

Hierholzer's algorithm for undirected graphs.

Parameters

g	The undirected graph
start	Starting vertex

Returns: List of arcs forming the Eulerian path/cycle

Definition at line 629 of file eulerian.H.

References ARC_BITS, Aleph::Depth_First, GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::DynList< T >::get_first(), Aleph::DynList< T >::insert(), IS_ARC_VISITED, Aleph::HTList::is_empty(), Aleph::maps(), Aleph::next(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::DynList< T >::remove_first(), GraphCommon< GT, Node, Arc >::reset_arcs(), and Aleph::Find_Eulerian_Path< GT, SN, SA >::sa.

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

◆ operator()()

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

Result Aleph::Find_Eulerian_Path< GT, SN, SA >::operator() ( GT & g )

inline

Find an Eulerian path or cycle in the graph.

Parameters

g	The graph to search

Returns: Result containing the path (if exists) and its type

Example: Find_Eulerian_Path<Graph> finder;

auto result = finder(g);

if (result.type != Eulerian_Type::None)

{

cout << "Found " << (result.type == Eulerian_Type::Cycle ? "cycle" : "path")

<< " with " << result.path.size() << " edges\n";

}

Aleph::HTList::size
size_t size() const noexcept
Count the number of elements of the list.
Definition htlist.H:1319

Aleph::Eulerian_Type::None
@ None
Graph is not Eulerian.