eulerian_example.C File Reference

Eulerian paths/cycles in Aleph-w (eulerian.H) with classic demos and rich visual explanations. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <vector>
#include <tclap/CmdLine.h>
#include <tpl_graph.H>
#include <eulerian.H>

Include dependency graph for eulerian_example.C:

Go to the source code of this file.

Typedefs
using	SNode = Graph_Node< string >
using	IArc = Graph_Arc< int >
using	UGraph = List_Graph< SNode, IArc >
using	DGraph = List_Digraph< SNode, IArc >

Functions
void	print_section (const string &title)
void	print_subsection (const string &title)
template<typename G >
void	print_graph (const string &label, G &g)
void	demo_eulerian_cycle ()
void	demo_konigsberg ()
void	demo_directed ()
void	demo_practical ()
void	demo_hierholzer ()
void	demo_eulerian_type ()
int	main (int argc, char *argv[])

Detailed Description

Eulerian paths/cycles in Aleph-w (eulerian.H) with classic demos and rich visual explanations.

Overview

This program demonstrates Eulerian paths and cycles.

• Eulerian: visits every edge exactly once.
• (Contrast: Hamiltonian visits every vertex exactly once.)

It contains multiple demo sections (undirected, directed, historical example, algorithm walkthrough), selectable via the command line.

Data model used by this example

• Undirected graph type:
  • UGraph = List_Graph<Graph_Node<string>, Graph_Arc<int>>
• Directed graph type:
  • DGraph = List_Digraph<Graph_Node<string>, Graph_Arc<int>>
• Node info: label (string)
• Arc info: integer value (int) used by the demo

Usage / CLI

This example uses TCLAP and a section selector:

• --section / -s <section>: one of cycle, konigsberg, directed, practical, hierholzer, types, all (default).
• --help: show help.

# Run all demonstrations
./eulerian_example
 
# Run one section
./eulerian_example --section konigsberg
./eulerian_example -s directed
 
# Show help
./eulerian_example --help

Algorithms

Eulerian conditions (undirected)

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

Why: to traverse every edge exactly once, every time you enter a vertex you must also leave it, except possibly at the start/end.

Eulerian conditions (directed)

• Eulerian cycle:
  • for all vertices: in-degree == out-degree, and
  • the vertices incident to at least one edge must belong to a single strongly connected region.
• Eulerian path:
  • at most 1 vertex with (out-degree - in-degree) == 1 (start)
  • at most 1 vertex with (in-degree - out-degree) == 1 (end)
  • all other vertices: in-degree == out-degree

Note

Aleph-w's Test_Eulerian performs a practical reachability check for Eulerian cycles in digraphs (among non-isolated vertices). For Eulerian paths in digraphs, the classification in this demo is based on in/out degree balance.

Constructing an Eulerian trail: Hierholzer

Find_Eulerian(G):
  1. Check Eulerian conditions
  2. Choose start vertex
  3. Follow unused edges to form a cycle/trail
  4. While edges remain unused, splice additional cycles

Running time is linear in the number of edges.

Historical context: Königsberg bridges (1736)

The city of Königsberg had 7 bridges connecting 4 land areas:

   A
  /|\
 / | \
B--+--C
 \ | /
  \|/
   D

Euler proved the requested walk is impossible because all 4 vertices have odd degree (more than two odd-degree vertices => no Eulerian path).

Visual example (undirected)

Graph:
  A---B
  |\ /|
  | X |
  |/ \|
  C---D
 
Degrees: A=3, B=3, C=3, D=3 (all odd!)
Result: No Eulerian path (4 odd vertices > 2)

Modify (add one edge) to make exactly two vertices odd:

  A---B---E
  |\ /|
  | X |
  |/ \|
  C---D
 
Result: Eulerian path exists (A and E are odd)

Complexity

Let V be the number of vertices and E the number of edges.

• Eulerian tests: O(V + E)
• Hierholzer construction: O(E)

Pitfalls and edge cases

• In directed graphs, degree balance alone is not sufficient; connectivity among non-isolated vertices matters.
• Multiple Eulerian trails may exist; adjacency iteration order can change the produced trail.

References / see also

• eulerian.H
• hamiltonian_example.C
• bfs_dfs_example.C

Author

Leandro Rabindranath León

Date

2024

Copyright

GNU General Public License

Definition in file eulerian_example.C.

Typedef Documentation

DGraph

using DGraph = List_Digraph<SNode, IArc>

Definition at line 169 of file eulerian_example.C.

IArc

using IArc = Graph_Arc<int>

Definition at line 167 of file eulerian_example.C.

SNode

using SNode = Graph_Node<string>

Definition at line 166 of file eulerian_example.C.

UGraph

using UGraph = List_Graph<SNode, IArc>

Definition at line 168 of file eulerian_example.C.

Function Documentation

demo_directed()

void demo_directed

(

)

Definition at line 350 of file eulerian_example.C.

References Aleph::maps(), print_section(), and print_subsection().

Referenced by main().

demo_eulerian_cycle()

void demo_eulerian_cycle

(

)

Definition at line 221 of file eulerian_example.C.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), print_graph(), print_section(), and print_subsection().

Referenced by main().

demo_eulerian_type()

void demo_eulerian_type

(

)

Definition at line 628 of file eulerian_example.C.

References Aleph::maps(), and print_section().

Referenced by main().

demo_hierholzer()

void demo_hierholzer

(

)

Definition at line 504 of file eulerian_example.C.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), print_section(), print_subsection(), and Aleph::HTList::size().

Referenced by main().

demo_konigsberg()

void demo_konigsberg

(

)

Definition at line 291 of file eulerian_example.C.

References Aleph::maps(), print_section(), and test().

Referenced by main().

demo_practical()

void demo_practical

(

)

Definition at line 422 of file eulerian_example.C.

References Aleph::maps(), print_graph(), print_section(), and print_subsection().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 691 of file eulerian_example.C.

References demo_directed(), demo_eulerian_cycle(), demo_eulerian_type(), demo_hierholzer(), demo_konigsberg(), demo_practical(), and Aleph::maps().

print_graph()

template<typename G >

void print_graph	(	const string &	label,
		G &	g
	)

Definition at line 188 of file eulerian_example.C.

References Aleph::maps().

Referenced by demo_eulerian_cycle(), and demo_practical().

print_section()

void print_section

(

const string &

title

)

Definition at line 175 of file eulerian_example.C.

References Aleph::maps().

Referenced by demo_directed(), demo_eulerian_cycle(), demo_eulerian_type(), demo_hierholzer(), demo_konigsberg(), and demo_practical().

print_subsection()

void print_subsection

(

const string &

title

)

Definition at line 182 of file eulerian_example.C.

References Aleph::maps().

Referenced by demo_directed(), demo_eulerian_cycle(), demo_hierholzer(), and demo_practical().