eulerian.H File Reference

Eulerian graph detection and path/cycle finding. More...

#include <tpl_graph.H>
#include <tpl_graph_utils.H>

Include dependency graph for eulerian.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Test_Eulerian< GT, SN, SA >
	Tests whether a graph or digraph is Eulerian. More...
class	Aleph::Find_Eulerian_Path< GT, SN, SA >
	Finds and constructs an Eulerian path or cycle using Hierholzer's algorithm. More...
struct	Aleph::Find_Eulerian_Path< GT, SN, SA >::Result
	Result type: path and its classification. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Enumerations
enum class	Aleph::Eulerian_Type { Aleph::Cycle , Aleph::Path , Aleph::None }
	Enumeration for Eulerian graph classification. More...

Detailed Description

Eulerian graph detection and path/cycle finding.

This file provides algorithms to test whether a graph or digraph is Eulerian (contains an Eulerian cycle) or semi-Eulerian (contains an Eulerian path).

Definitions

• Eulerian Cycle: A cycle that visits every edge exactly once
• Eulerian Path: A path that visits every edge exactly once
• Eulerian Graph: Contains an Eulerian cycle
• Semi-Eulerian Graph: Contains an Eulerian path but not a cycle

Conditions for Eulerian Graphs

Undirected Graphs

• Eulerian cycle: Connected + all vertices have even degree
• Eulerian path: Connected + exactly 0 or 2 vertices have odd degree

Directed Graphs

• Eulerian cycle: Strongly connected + in-degree = out-degree for all
• Eulerian path: Weakly connected + at most one vertex with out-in=1, at most one with in-out=1, rest balanced

Complexity

Operation	Time
Test Eulerian	O(V + E)
With connectivity check	O(V + E)

Usage Example

List_Graph<Node, Arc> g;
// ... build graph ...
 
Test_Eulerian<decltype(g)> test;
 
// Simple check (backward compatible)
if (test(g))
  std::cout << "Graph has Eulerian cycle\n";
 
// Detailed check
auto result = test.compute(g);
switch (result) {
  case Eulerian_Type::Cycle: cout << "Has Eulerian cycle\n"; break;
  case Eulerian_Type::Path:  cout << "Has Eulerian path\n"; break;
  case Eulerian_Type::None:  cout << "Not Eulerian\n"; break;
}

See also

tpl_graph.H Graph data structures

hamiltonian.H Hamiltonian path/cycle algorithms

tpl_test_connectivity.H Connectivity testing

Author

Leandro Rabindranath León

Definition in file eulerian.H.