Hierholzer's algorithm
Hierholzer's Algorithm is an efficient way to find Eulerian circuits in a graph.
Hierholzer's algorithm is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Description
Algorithm: Hierholzer's Algorithm
Input: Graph G = (V, E) represented as adjacency list
Output: Eulerian circuit as ordered list of vertices
Function FindEulerianCircuit(Graph G):
// Initialize empty circuit and stack
Circuit = empty list
Stack = empty stack
// Start from any vertex with non-zero degree
current = any vertex v in V where degree(v) > 0
Push current to Stack
While Stack is not empty:
if OutDegree(current) == 0:
// Add to circuit when no more unused edges
Add current to front of Circuit
current = Pop from Stack
else:
// Follow an unused edge
Push current to Stack
next = any adjacent vertex with unused edge from current
Remove edge (current, next) from G
current = next
Return Circuit
Function VerifyEulerianCircuit(Graph G):
For each vertex v in G:
If InDegree(v) ≠ OutDegree(v):
Return false
If Graph is not strongly connected:
Return false
Return true
Main Algorithm:
1. If not VerifyEulerianCircuit(G):
Return "No Eulerian circuit exists"
2. Circuit = FindEulerianCircuit(G)
3. If Circuit contains all edges:
Return Circuit
Else:
Return "No Eulerian circuit exists"
Preconditions:
- Graph must be connected
- All vertices must have equal in-degree and out-degree
Time Complexity: O(|E|) where E is the number of edges
Space Complexity: O(|V|) where V is the number of vertices- Task
Implement the Hierholze's Algorithm in your language and test it using the same examples as in the OCaml entry.
scope # Hierholzer's algorithm - translation of Pluto
# find the Eulerian circuit
local proc findCircuit( adj :: sequence ) :: sequence
local path, circuit, currV := seq(), seq(), 1;
if size adj > 0 then
path[ 1 ] := currV;
while size path > 0 do
if size adj[ currV ] <> 0 then
path[ size path + 1 ] := currV;
currV := purge( adj[ currV ] ) # remove the final element
else
circuit[ size circuit + 1 ] := currV;
currV := purge( path ) # remove the final element
fi
od
fi;
return reverse( circuit )
end;
local proc printCircuit( s :: sequence )
io.write( if size s > 0 then s[ 1 ] else "(empty)" fi );
for i from 2 to size s do io.write( " -> ", s[ i ] ) od;
io.write( "\n" )
end;
# first adjacency list test case
printCircuit( findCircuit( seq( seq( 2 ), seq( 3 ), seq( 1 ) ) ) );
# second adjacency list test case
printCircuit( findCircuit( seq( seq( 2, 7 ), seq( 3 ), seq( 1, 4 ), seq( 5 )
, seq( 3, 6 ), seq( 1 ), seq( 5 )
)
)
)
end- Output:
1 -> 2 -> 3 -> 1 1 -> 7 -> 5 -> 6 -> 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 1
using System;
using System.Collections.Generic;
using System.Linq;
public static class HierholzesAlgorithm
{
public static void Main(string[] args)
{
var adjacencyList1 = new List<List<int>>();
adjacencyList1.Add(new List<int> { 1 });
adjacencyList1.Add(new List<int> { 2 });
adjacencyList1.Add(new List<int> { 0 });
PrintCircuit(adjacencyList1);
var adjacencyList2 = new List<List<int>>();
adjacencyList2.Add(new List<int> { 1, 6 });
adjacencyList2.Add(new List<int> { 2 });
adjacencyList2.Add(new List<int> { 0, 3 });
adjacencyList2.Add(new List<int> { 4 });
adjacencyList2.Add(new List<int> { 2, 5 });
adjacencyList2.Add(new List<int> { 0 });
adjacencyList2.Add(new List<int> { 4 });
PrintCircuit(adjacencyList2);
}
public static void PrintCircuit(List<List<int>> adjacencyList)
{
if (adjacencyList.Count == 0)
{
return;
}
var path = new Stack<int>();
var circuit = new List<int>();
int currentVertex = 0; // Start at vertex 0
path.Push(currentVertex);
while (path.Count > 0)
{
if (adjacencyList[currentVertex].Count > 0)
{
path.Push(currentVertex);
int nextVertex = adjacencyList[currentVertex].Last();
adjacencyList[currentVertex].RemoveAt(adjacencyList[currentVertex].Count - 1);
currentVertex = nextVertex;
}
else // Back-tracking
{
circuit.Add(currentVertex);
currentVertex = path.Pop();
}
}
// Print the circuit
for (int i = circuit.Count - 1; i >= 0; i--)
{
Console.Write(circuit[i]);
if (i != 0)
{
Console.Write(" => ");
}
}
Console.WriteLine();
}
}
- Output:
0 => 1 => 2 => 0 0 => 6 => 4 => 5 => 0 => 1 => 2 => 3 => 4 => 2 => 0
Based on code from https://www.geeksforgeeks.org/hierholzers-algorithm-directed-graph/
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
void printCircuit(vector< vector<int> > adj) {
// adj represents the adjacency list of
// the directed graph
// edge_count represents the number of edges
// emerging from a vertex
unordered_map<int,int> edge_count;
for (size_t i = 0; i < adj.size(); i++) {
//find the count of edges to keep track
//of unused edges
edge_count[i] = adj[i].size();
}
if (!adj.size())
return; //empty graph
// Maintain a stack to keep vertices
stack<int> curr_path;
// vector to store final circuit
vector<int> circuit;
// start from any vertex
curr_path.push(0);
int curr_v = 0; // Current vertex
while (!curr_path.empty()) {
// If there's remaining edge
if (edge_count[curr_v]) {
// Push the vertex
curr_path.push(curr_v);
// Find the next vertex using an edge
int next_v = adj[curr_v].back();
// and remove that edge
edge_count[curr_v]--;
adj[curr_v].pop_back();
// Move to next vertex
curr_v = next_v;
}
// back-track to find remaining circuit
else
{
circuit.push_back(curr_v);
// Back-tracking
curr_v = curr_path.top();
curr_path.pop();
}
}
// we've got the circuit, now print it in reverse
for (int i=circuit.size()-1; i>=0; i--) {
cout << circuit[i];
if (i) cout<<" -> ";
}
}
// Driver program to check the above function
int main() {
vector< vector<int> > adj1, adj2;
// First adjacency list
adj1.resize(3);
// Build the edges
adj1[0].push_back(1);
adj1[1].push_back(2);
adj1[2].push_back(0);
printCircuit(adj1);
cout << endl;
// Second adjacency list
adj2.resize(7);
adj2[0].push_back(1);
adj2[0].push_back(6);
adj2[1].push_back(2);
adj2[2].push_back(0);
adj2[2].push_back(3);
adj2[3].push_back(4);
adj2[4].push_back(2);
adj2[4].push_back(5);
adj2[5].push_back(0);
adj2[6].push_back(4);
printCircuit(adj2);
return 0;
}
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
import 'dart:collection';
void printCircuit(List<List<int>> adj) {
// Edge count map to track unused edges
Map<int, int> edgeCount = {};
for (var i = 0; i < adj.length; i++) {
edgeCount[i] = adj[i].length;
}
if (adj.isEmpty) return;
// Stack for current path
Queue<int> currPath = Queue<int>();
// List to store final circuit
List<int> circuit = [];
currPath.addFirst(0);
var currV = 0;
while (currPath.isNotEmpty) {
if (edgeCount[currV]! > 0) {
currPath.addFirst(currV);
var nextV = adj[currV].last;
edgeCount[currV] = edgeCount[currV]! - 1;
adj[currV].removeLast();
currV = nextV;
} else {
circuit.add(currV);
currV = currPath.first;
currPath.removeFirst();
}
}
// Print circuit in reverse
String result = circuit.reversed.join(" -> ");
print(result);
}
void main() {
// First adjacency list
var adj1 = List.generate(3, (_) => <int>[]);
adj1[0].add(1);
adj1[1].add(2);
adj1[2].add(0);
printCircuit(adj1);
// Second adjacency list
var adj2 = List.generate(7, (_) => <int>[]);
adj2[0].addAll([1, 6]);
adj2[1].add(2);
adj2[2].addAll([0, 3]);
adj2[3].add(4);
adj2[4].addAll([2, 5]);
adj2[5].add(0);
adj2[6].add(4);
printCircuit(adj2);
}
- Output:
Same as C++ entry.
proc prcircuit adja[][] .
if len adja[][] = 0 : return
curr = 1
path[] &= curr
while len path[] > 0
if len adja[curr][] > 0
path[] &= curr
next = adja[curr][len adja[curr][]]
len adja[curr][] -1
curr = next
else
circ[] &= curr
curr = path[$]
len path[] -1
.
.
for i = len circ[] downto 1
write circ[i]
if i <> 1 : write " => "
.
print ""
.
prcircuit [ [ 2 ] [ 3 ] [ 1 ] ]
prcircuit [ [ 2 7 ] [ 3 ] [ 1 4 ] [ 5 ] [ 3 6 ] [ 1 ] [ 5 ] ]- Output:
1 => 2 => 3 => 1 1 => 7 => 5 => 6 => 1 => 2 => 3 => 4 => 5 => 3 => 1
defmodule HierholzersAlgorithm do
def main(_) do
# First adjacency list example
adjacency_list1 = [
[1], # Vertex 0 connects to vertex 1
[2], # Vertex 1 connects to vertex 2
[0] # Vertex 2 connects to vertex 0
]
IO.puts("Circuit for Adjacency List 1:")
print_circuit(adjacency_list1)
# Second adjacency list example
adjacency_list2 = [
[1, 6], # Vertex 0 connects to vertices 1, 6
[2], # Vertex 1 connects to vertex 2
[0, 3], # Vertex 2 connects to vertices 0, 3
[4], # Vertex 3 connects to vertex 4
[2, 5], # Vertex 4 connects to vertices 2, 5
[0], # Vertex 5 connects to vertex 0
[4] # Vertex 6 connects to vertex 4
]
IO.puts("\nCircuit for Adjacency List 2:")
print_circuit(adjacency_list2)
end
def print_circuit([]), do: :ok
def print_circuit(adjacency_list) do
path = [0] # Start with vertex 0 on the path stack
circuit = []
adj_map = create_adjacency_map(adjacency_list, 0, %{})
final_circuit = find_circuit(0, path, circuit, adj_map)
print_result(:lists.reverse(final_circuit))
end
defp create_adjacency_map([], _, map), do: map
defp create_adjacency_map([neighbors | rest], index, map) do
create_adjacency_map(rest, index + 1, Map.put(map, index, neighbors))
end
defp find_circuit(_current_vertex, [], circuit, _), do: circuit
defp find_circuit(current_vertex, path, circuit, adj_map) do
case Map.fetch(adj_map, current_vertex) do
{:ok, []} ->
# No more neighbors - backtrack
new_circuit = [current_vertex | circuit]
[new_current_vertex | rest_path] = path
find_circuit(new_current_vertex, rest_path, new_circuit, adj_map)
{:ok, neighbors} ->
# Has neighbors - move forward
next_vertex = List.last(neighbors)
remaining_neighbors = List.delete_at(neighbors, -1)
new_adj_map = Map.put(adj_map, current_vertex, remaining_neighbors)
new_path = [current_vertex | path]
find_circuit(next_vertex, new_path, circuit, new_adj_map)
:error ->
# Vertex not found - backtrack
new_circuit = [current_vertex | circuit]
[new_current_vertex | rest_path] = path
find_circuit(new_current_vertex, rest_path, new_circuit, adj_map)
end
end
defp print_result([]), do: IO.puts("")
defp print_result([vertex]), do: IO.puts("#{vertex}")
defp print_result([vertex | rest]) do
IO.write("#{vertex} => ")
print_result(rest)
end
end
# Call the main function to execute the program
HierholzersAlgorithm.main(:ok)
- Output:
Circuit for Adjacency List 1: 0 => 2 => 1 => 0 Circuit for Adjacency List 2: 0 => 2 => 4 => 3 => 2 => 1 => 0 => 5 => 4 => 6 => 0
-module(hierholzers_algorithm).
-export([main/1, print_circuit/1]).
main(_) ->
% First adjacency list example
AdjacencyList1 = [
[1], % Vertex 0 connects to vertex 1
[2], % Vertex 1 connects to vertex 2
[0] % Vertex 2 connects to vertex 0
],
print_circuit(AdjacencyList1),
% Second adjacency list example
AdjacencyList2 = [
[1, 6], % Vertex 0 connects to vertices 1, 6
[2], % Vertex 1 connects to vertex 2
[0, 3], % Vertex 2 connects to vertices 0, 3
[4], % Vertex 3 connects to vertex 4
[2, 5], % Vertex 4 connects to vertices 2, 5
[0], % Vertex 5 connects to vertex 0
[4] % Vertex 6 connects to vertex 4
],
print_circuit(AdjacencyList2).
print_circuit([]) ->
ok;
print_circuit(AdjacencyList) ->
Path = [0], % Start with vertex 0 on the path stack
Circuit = [],
CurrentVertex = 0,
% Convert adjacency list to mutable array-like structure using dict
AdjDict = create_adjacency_dict(AdjacencyList, 0, dict:new()),
FinalCircuit = find_circuit(CurrentVertex, Path, Circuit, AdjDict),
print_result(lists:reverse(FinalCircuit)).
% Helper function to create a dictionary from adjacency list
create_adjacency_dict([], _, Dict) ->
Dict;
create_adjacency_dict([Neighbors | Rest], Index, Dict) ->
create_adjacency_dict(Rest, Index + 1, dict:store(Index, Neighbors, Dict)).
% Main algorithm implementation
find_circuit(CurrentVertex, [], Circuit, _) ->
Circuit;
find_circuit(CurrentVertex, Path, Circuit, AdjDict) ->
case dict:find(CurrentVertex, AdjDict) of
{ok, []} ->
% No more neighbors - backtrack
NewCircuit = [CurrentVertex | Circuit],
case Path of
[] -> NewCircuit;
[NewCurrentVertex | RestPath] ->
find_circuit(NewCurrentVertex, RestPath, NewCircuit, AdjDict)
end;
{ok, Neighbors} ->
% Has neighbors - move forward
NextVertex = lists:last(Neighbors),
RemainingNeighbors = lists:droplast(Neighbors),
NewAdjDict = dict:store(CurrentVertex, RemainingNeighbors, AdjDict),
NewPath = [CurrentVertex | Path],
find_circuit(NextVertex, NewPath, Circuit, NewAdjDict);
error ->
% Vertex not found - backtrack
NewCircuit = [CurrentVertex | Circuit],
case Path of
[] -> NewCircuit;
[NewCurrentVertex | RestPath] ->
find_circuit(NewCurrentVertex, RestPath, NewCircuit, AdjDict)
end
end.
% Print the circuit with arrows
print_result([]) ->
io:format("~n");
print_result([Vertex]) ->
io:format("~w~n", [Vertex]);
print_result([Vertex | Rest]) ->
io:format("~w => ", [Vertex]),
print_result(Rest).
- Output:
0 => 2 => 1 => 0 0 => 2 => 4 => 3 => 2 => 1 => 0 => 5 => 4 => 6 => 0
module circuit_mod
implicit none
contains
subroutine printCircuit(adj, n)
integer, intent(in) :: n
integer, intent(in) :: adj(0:n-1, n)
integer :: edge_count(0:n-1)
integer :: curr_path(n), top
integer :: circuit(n), circuit_index
integer :: curr_v, next_v, i
! Initialize edge_count
edge_count = 0
do i = 0, n-1
edge_count(i) = count(adj(i, :) /= -1)
end do
if (n == 0) return ! empty graph
! Initialize stack and circuit
top = -1
circuit_index = 0
curr_v = 0
do
if (edge_count(curr_v) > 0) then
! Push the vertex
top = top + 1
curr_path(top) = curr_v
! Find the next vertex using an edge
next_v = adj(curr_v, edge_count(curr_v))
edge_count(curr_v) = edge_count(curr_v) - 1
! Move to next vertex
curr_v = next_v
else
! Add to circuit
circuit_index = circuit_index + 1
circuit(circuit_index) = curr_v
! Back-tracking
if (top == -1) exit
curr_v = curr_path(top)
top = top - 1
end if
end do
! Print the circuit in reverse
do i = circuit_index, 1, -1
write(*, fmt='(i0)', advance='no') circuit(i)
if (i > 1) write(*, fmt='(" -> ")', advance='no')
end do
write(*, *)
end subroutine printCircuit
end module circuit_mod
program main
use circuit_mod
implicit none
integer :: adj1(0:2, 3), adj2(0:6, 7)
integer :: i
! Initialize adjacency lists
adj1 = -1
adj1(0, 1) = 1
adj1(1, 1) = 2
adj1(2, 1) = 0
adj2 = -1
adj2(0, 1) = 1
adj2(0, 2) = 6
adj2(1, 1) = 2
adj2(2, 1) = 0
adj2(2, 2) = 3
adj2(3, 1) = 4
adj2(4, 1) = 2
adj2(4, 2) = 5
adj2(5, 1) = 0
adj2(6, 1) = 4
call printCircuit(adj1, 3)
write(*, *)
call printCircuit(adj2, 7)
end program main
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
' Stack implementation
Type Stack
dato(99) As Integer
top As Integer
End Type
' Stack operations
Sub initStack(st As Stack Ptr)
st->top = 0
End Sub
Function isEmpty(st As Stack Ptr) As Boolean
Return (st->top = 0)
End Function
Sub push(st As Stack Ptr, value As Integer)
st->top += 1
st->dato(st->top) = value
End Sub
Function pop(st As Stack Ptr) As Integer
Dim As Integer value = st->dato(st->top)
st->top -= 1
Return value
End Function
Function peek_(st As Stack Ptr) As Integer
Return st->dato(st->top)
End Function
' Adjacency list implementation
Type AdjList
edges(99) As Integer
count As Integer
End Type
' Subroutine to print the Eulerian circuit
Sub printCircuit(adj() As AdjList, size As Integer)
If size = 0 Then Exit Sub ' If the adjacency list is empty, we exit
Dim As Stack currPath, circuit
initStack(@currPath)
initStack(@circuit)
' Start with vertex 0
push(@currPath, 0)
While Not isEmpty(@currPath)
Dim As Integer currV = peek_(@currPath)
If adj(currV).count > 0 Then
' Get next vertex from adjacency list
Dim As Integer nextV = adj(currV).edges(1)
' Remove edge (shift remaining edges left)
For i As Integer = 1 To adj(currV).count - 1
adj(currV).edges(i) = adj(currV).edges(i + 1)
Next
adj(currV).count -= 1
push(@currPath, nextV)
Else
' Backtrack and add to circuit
push(@circuit, pop(@currPath))
End If
Wend
' Print the circuit in reverse order
While Not isEmpty(@circuit)
Print pop(@circuit);
If Not isEmpty(@circuit) Then Print " -> ";
Wend
Print
End Sub
' Main program
Sub main()
' First adjacency list
Dim adj1(0 To 2) As AdjList
With adj1(0)
.edges(1) = 1
.count = 1
End With
With adj1(1)
.edges(1) = 2
.count = 1
End With
With adj1(2)
.edges(1) = 0
.count = 1
End With
printCircuit(adj1(), 3)
' Second adjacency list
Dim adj2(0 To 6) As AdjList
With adj2(0)
.edges(1) = 1
.edges(2) = 6
.count = 2
End With
With adj2(1)
.edges(1) = 2
.count = 1
End With
With adj2(2)
.edges(1) = 0
.edges(2) = 3
.count = 2
End With
With adj2(3)
.edges(1) = 4
.count = 1
End With
With adj2(4)
.edges(1) = 2
.edges(2) = 5
.count = 2
End With
With adj2(5)
.edges(1) = 0
.count = 1
End With
With adj2(6)
.edges(1) = 4
.count = 1
End With
printCircuit(adj2(), 7)
End Sub
main()
Sleep
- Output:
0 -> 1 -> 2 -> 0 0 -> 1 -> 2 -> 0 -> 6 -> 4 -> 2 -> 3 -> 4 -> 5 -> 0
package main
import (
"fmt"
)
// printCircuit finds and prints an Eulerian circuit in a directed graph
// using Hierholzer's algorithm.
// It assumes the graph has an Eulerian circuit starting from vertex 0.
// NOTE: This function modifies the input adjacency list 'adj'.
func printCircuit(adj [][]int) {
if len(adj) == 0 {
fmt.Println("Empty graph")
return // empty graph
}
// edgeCount represents the number of edges emerging from a vertex
// Equivalent to Python's edge_count dictionary
edgeCount := make(map[int]int)
for i := 0; i < len(adj); i++ {
// Find the count of edges to keep track of unused edges
edgeCount[i] = len(adj[i])
}
// Maintain a stack to keep vertices
// Equivalent to Python's curr_path list used as a stack
currPath := []int{}
// Slice to store final circuit
// Equivalent to Python's circuit list
circuit := []int{}
// Start from vertex 0 (or any vertex if guaranteed to be part of circuit)
currPath = append(currPath, 0)
currV := 0 // Current vertex
for len(currPath) > 0 {
// If there's a remaining edge from the current vertex
if edgeCount[currV] > 0 {
// Push the current vertex onto the path before exploring the edge
currPath = append(currPath, currV)
// Find the next vertex using an edge
// Equivalent to Python's adj[curr_v][-1]
lastNeighborIndex := len(adj[currV]) - 1
nextV := adj[currV][lastNeighborIndex]
// Decrement the edge count for the current vertex
edgeCount[currV]--
// Remove that edge (modifies the original adj slice)
// Equivalent to Python's adj[curr_v].pop()
adj[currV] = adj[currV][:lastNeighborIndex]
// Move to the next vertex
currV = nextV
} else {
// If no more edges from currV, it means we've completed a cycle (or sub-cycle)
// Add the vertex to the final circuit
circuit = append(circuit, currV)
// Backtrack: Pop the last vertex from the path and make it the current one
// Equivalent to Python's curr_v = curr_path[-1]; curr_path.pop()
lastElementIndex := len(currPath) - 1
currV = currPath[lastElementIndex]
currPath = currPath[:lastElementIndex] // Pop from stack
}
}
// We've got the circuit, now print it in reverse
// Equivalent to Python's reverse iteration and printing
for i := len(circuit) - 1; i >= 0; i-- {
fmt.Print(circuit[i])
if i > 0 {
fmt.Print(" -> ")
}
}
fmt.Println() // Add a final newline
}
func main() {
// --- Input Graph 1 ---
// Equivalent to Python's adj1 initialization
adj1 := make([][]int, 3)
// No need to initialize inner slices with make if using append
// adj1[0] = make([]int, 0, 1) // Optional pre-allocation
// adj1[1] = make([]int, 0, 1)
// adj1[2] = make([]int, 0, 1)
// Build the edges
adj1[0] = append(adj1[0], 1)
adj1[1] = append(adj1[1], 2)
adj1[2] = append(adj1[2], 0)
fmt.Println("Circuit for Graph 1:")
printCircuit(adj1) // Note: adj1 will be modified
fmt.Println()
// --- Input Graph 2 ---
// Equivalent to Python's adj2 initialization
adj2 := make([][]int, 7)
// adj2[0] = make([]int, 0, 2) // Optional pre-allocation
// ... and so on
adj2[0] = append(adj2[0], 1)
adj2[0] = append(adj2[0], 6)
adj2[1] = append(adj2[1], 2)
adj2[2] = append(adj2[2], 0)
adj2[2] = append(adj2[2], 3)
adj2[3] = append(adj2[3], 4)
adj2[4] = append(adj2[4], 2)
adj2[4] = append(adj2[4], 5)
adj2[5] = append(adj2[5], 0)
adj2[6] = append(adj2[6], 4)
fmt.Println("Circuit for Graph 2:")
printCircuit(adj2) // Note: adj2 will be modified
fmt.Println()
}
- Output:
Circuit for Graph 1: 0 -> 1 -> 2 -> 0 Circuit for Graph 2: 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
import Data.Array.Diff
findEulerianCircuit :: DiffArray Int [Int] -> Maybe [Int]
findEulerianCircuit graph0 = go graph0 [] [start]
where
start = fst $ bounds graph0
go graph circuit []
| all null (elems graph) = Just circuit
| otherwise = Nothing
go graph circuit (current:stack)
| null edges = go graph (current:circuit) stack
| otherwise = go graph1 circuit (next:current:stack)
where
edges = graph ! current
next = head edges
graph1 = graph // [(current, tail edges)]
graph1, graph2 :: DiffArray Int [Int]
graph1 = listArray (0,2) [[1],[2],[0]]
graph2 = listArray (0,6) [[1,6],[2],[0,3],[4],[2,5],[0],[4]]
- Output:
ghci> findEulerianCircuit graph1 Just [0,1,2,0] ghci> findEulerianCircuit graph2 Just [0,1,2,0,6,4,2,3,4,5,0]
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public final class HierholzesAlgorithm {
public static void main(String[] args) {
List<List<Integer>> adjacencyList1 = new ArrayList<List<Integer>>();
adjacencyList1.addLast( Stream.of( 1 ).collect(Collectors.toList()) );
adjacencyList1.addLast( Stream.of( 2 ).collect(Collectors.toList()) );
adjacencyList1.addLast( Stream.of( 0 ).collect(Collectors.toList()) );
printCircuit(adjacencyList1);
List<List<Integer>> adjacencyList2 = new ArrayList<List<Integer>>();
adjacencyList2.addLast( Stream.of( 1, 6 ).collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 2 ) .collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 0, 3 ).collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 4 ) .collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 2, 5 ).collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 0 ) .collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 4 ) .collect(Collectors.toList()) );
printCircuit(adjacencyList2);
}
public static void printCircuit(List<List<Integer>> adjacencyList) {
if ( adjacencyList.isEmpty() ) {
return;
}
Stack<Integer> path = new Stack<Integer>();
List<Integer> circuit = new ArrayList<Integer>();
int currentVertex = 0; // Start at vertex 0
path.push(currentVertex);
while ( ! path.isEmpty() ) {
if ( ! adjacencyList.get(currentVertex).isEmpty() ) {
path.push(currentVertex);
final int nextVertex = adjacencyList.get(currentVertex).getLast();
adjacencyList.get(currentVertex).removeLast();
currentVertex = nextVertex;
} else { // Back-tracking
circuit.add(currentVertex);
currentVertex = path.pop();
}
}
for ( int i = circuit.size() - 1; i >= 0; i-- ) { // Print the circuit
System.out.print(circuit.get(i));
if ( i != 0 ) {
System.out.print(" => ");
}
}
System.out.println();
}
}
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
function printCircuit(adj) {
// adj represents the adjacency list of the directed graph
// edge_count represents the number of edges emerging from a vertex
let edge_count = new Map();
// Initialize edge count for each vertex
for (let i = 0; i < adj.length; i++) {
edge_count.set(i, adj[i].length);
}
if (!adj.length) {
return; // empty graph
}
// Maintain a stack to keep vertices
let curr_path = [];
// Array to store final circuit
let circuit = [];
// Start from vertex 0
curr_path.push(0);
let curr_v = 0; // Current vertex
while (curr_path.length > 0) {
// If there's remaining edge
if (edge_count.get(curr_v) > 0) {
// Push the vertex
curr_path.push(curr_v);
// Find the next vertex using an edge
let next_v = adj[curr_v][adj[curr_v].length - 1];
// Remove that edge
edge_count.set(curr_v, edge_count.get(curr_v) - 1);
adj[curr_v].pop();
// Move to next vertex
curr_v = next_v;
}
// Back-track to find remaining circuit
else {
circuit.push(curr_v);
// Back-tracking
curr_v = curr_path[curr_path.length - 1];
curr_path.pop();
}
}
// Print the circuit in reverse
let result = "";
for (let i = circuit.length - 1; i >= 0; i--) {
result += circuit[i];
if (i > 0) {
result += " -> ";
}
}
console.log(result);
}
// Test the function
function main() {
// First adjacency list
let adj1 = new Array(3);
for (let i = 0; i < adj1.length; i++) {
adj1[i] = [];
}
// Build the edges
adj1[0].push(1);
adj1[1].push(2);
adj1[2].push(0);
printCircuit(adj1);
// Second adjacency list
let adj2 = new Array(7);
for (let i = 0; i < adj2.length; i++) {
adj2[i] = [];
}
adj2[0].push(1);
adj2[0].push(6);
adj2[1].push(2);
adj2[2].push(0);
adj2[2].push(3);
adj2[3].push(4);
adj2[4].push(2);
adj2[4].push(5);
adj2[5].push(0);
adj2[6].push(4);
printCircuit(adj2);
}
// Run the program
main();
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
""" Function to print the Eulerian circuit """
function print_circuit(adj)
isempty(adj) && return # If the adjacency list is empty, do nothing
curr_path = [0] # Start with vertex 0
circuit = Int[]
while !isempty(curr_path)
curr_v = curr_path[end]
if !isempty(adj[begin + curr_v])
next_v = popfirst!(adj[begin + curr_v]) # Get next vertex from list
push!(curr_path, next_v) # Push the new vertex to curr_path stack
else
# Backtrack and add to the circuit
push!(circuit, pop!(curr_path))
end
end
# Print the circuit in reverse order
for i in length(circuit):-1:1
print(circuit[i])
i > 1 && print(" -> ")
end
println()
end
# testing code
const adj1, adj2 = Vector{Vector{Int}}(), Vector{Vector{Int}}()
# First adjacency list
push!(adj1, [1], [2], [0])
print_circuit(adj1)
# Second adjacency list
push!(adj2, [1, 6], [2], [0, 3], [4], [2, 5], [0], [4])
print_circuit(adj2)
- Output:
0 -> 1 -> 2 -> 0 0 -> 1 -> 2 -> 0 -> 6 -> 4 -> 2 -> 3 -> 4 -> 5 -> 0
import java.util.Stack
fun main() {
val adjacencyList1 = mutableListOf<MutableList<Int>>()
adjacencyList1.add(mutableListOf(1))
adjacencyList1.add(mutableListOf(2))
adjacencyList1.add(mutableListOf(0))
printCircuit(adjacencyList1)
val adjacencyList2 = mutableListOf<MutableList<Int>>()
adjacencyList2.add(mutableListOf(1, 6))
adjacencyList2.add(mutableListOf(2))
adjacencyList2.add(mutableListOf(0, 3))
adjacencyList2.add(mutableListOf(4))
adjacencyList2.add(mutableListOf(2, 5))
adjacencyList2.add(mutableListOf(0))
adjacencyList2.add(mutableListOf(4))
printCircuit(adjacencyList2)
}
fun printCircuit(adjacencyList: MutableList<MutableList<Int>>) {
if (adjacencyList.isEmpty()) {
return
}
val path = Stack<Int>()
val circuit = mutableListOf<Int>()
var currentVertex = 0 // Start at vertex 0
path.push(currentVertex)
while (path.isNotEmpty()) {
if (adjacencyList[currentVertex].isNotEmpty()) {
path.push(currentVertex)
val nextVertex = adjacencyList[currentVertex].last()
adjacencyList[currentVertex].removeAt(adjacencyList[currentVertex].size - 1)
currentVertex = nextVertex
} else { // Back-tracking
circuit.add(currentVertex)
currentVertex = path.pop()
}
}
// Print the circuit
for (i in circuit.size - 1 downTo 0) {
print(circuit[i])
if (i != 0) {
print(" => ")
}
}
println()
}
- Output:
0 => 1 => 2 => 0 0 => 6 => 4 => 5 => 0 => 1 => 2 => 3 => 4 => 2 => 0
function print_circuit(adjacency_list)
if #adjacency_list == 0 then
return
end
local path = {}
local circuit = {}
local current_vertex = 1 -- Lua arrays are 1-based
table.insert(path, current_vertex)
while #path > 0 do
if #adjacency_list[current_vertex] > 0 then
table.insert(path, current_vertex)
local next_vertex = table.remove(adjacency_list[current_vertex])
current_vertex = next_vertex
else
table.insert(circuit, current_vertex)
current_vertex = table.remove(path)
end
end
-- Print the circuit
for i = #circuit, 1, -1 do
io.write(circuit[i])
if i ~= 1 then
io.write(" => ")
end
end
print()
end
local adjacency_list1 = {
{2},
{3},
{1}
}
print_circuit(adjacency_list1)
local adjacency_list2 = {
{2, 7},
{3},
{1, 4},
{5},
{3, 6},
{1},
{5}
}
print_circuit(adjacency_list2)
- Output:
1 => 2 => 3 => 1 1 => 7 => 5 => 6 => 1 => 2 => 3 => 4 => 5 => 3 => 1
(* Function to print the Eulerian circuit *)
printCircuit[adj_ /; adj === {}] := Return[] (* If adjacency list is empty, do nothing *)
printCircuit[adj_Association] := Module[{
currPath = {1}, (* Start with vertex 1 *)
circuit = {},
currentAdj = adj,
currV, nextV
},
While[Length[currPath] > 0,
currV = Last[currPath]; (* Get the last element of currPath *)
If[Length[currentAdj[currV]] > 0,
nextV = First[currentAdj[currV]]; (* Get next vertex from list *)
(* Remove the used vertex - this creates a new association *)
currentAdj = Association[Append[
Normal[currentAdj /. (currV -> vertices_) :>
(currV -> Rest[vertices])],
currV -> Rest[currentAdj[currV]]
]];
currPath = Append[currPath, nextV]; (* Append the new vertex to currPath *)
,
(* Backtrack and add to the circuit *)
circuit = Append[circuit, Last[currPath]];
currPath = Most[currPath];
]
];
(* Print the circuit in reverse order *)
result = Reverse[circuit];
If[Length[result] > 0,
Print[StringRiffle[ToString /@ result, " -> "]]
];
]
(* More elegant version using helper function to remove first element *)
removeFirst[assoc_, key_] := Module[{values = assoc[key]},
If[Length[values] > 0,
ReplacePart[assoc, key -> Rest[values]],
assoc
]
]
(* Cleaner version of the function *)
printCircuit[adj_ /; adj === {}] := Return[]
printCircuit[adj_Association] := Module[{
currPath = {1},
circuit = {},
currentAdj = adj,
currV, nextV
},
While[Length[currPath] > 0,
currV = Last[currPath];
If[Length[currentAdj[currV]] > 0,
nextV = First[currentAdj[currV]];
currentAdj = removeFirst[currentAdj, currV];
currPath = Append[currPath, nextV];
,
circuit = Append[circuit, Last[currPath]];
currPath = Most[currPath];
]
];
(* Print the circuit in reverse order *)
result = Reverse[circuit];
If[Length[result] > 0,
Print[StringRiffle[ToString /@ result, " -> "]]
];
]
(* Testing code *)
(* First adjacency list *)
adj1 = <|1 -> {2}, 2 -> {3}, 3 -> {1}|>;
printCircuit[adj1]
(* Second adjacency list *)
adj2 = <|1 -> {2, 7}, 2 -> {3}, 3 -> {1, 4}, 4 -> {5}, 5 -> {3, 6}, 6 -> {5}, 7 -> {1}|>;
printCircuit[adj2]
- Output:
1 -> 2 -> 3 -> 1 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 5 -> 3 -> 1 -> 7 -> 1
(* Function to print the Eulerian circuit *)
let print_circuit adj =
if Array.length adj = 0 then
() (* If the adjacency list is empty, do nothing *)
else
let curr_path = Stack.create () in
let circuit = Stack.create () in
(* Start with vertex 0 *)
Stack.push 0 curr_path;
while not (Stack.is_empty curr_path) do
let curr_v = Stack.top curr_path in
if adj.(curr_v) <> [] then
(* Get the next vertex from the adjacency list *)
let next_v = List.hd adj.(curr_v) in
adj.(curr_v) <- List.tl adj.(curr_v); (* Remove the edge *)
Stack.push next_v curr_path
else
(* Backtrack and add to the circuit *)
Stack.push (Stack.pop curr_path) circuit
done;
(* Print the circuit in reverse order *)
let rec print_stack s =
if not (Stack.is_empty s) then (
Printf.printf "%d" (Stack.pop s);
if not (Stack.is_empty s) then Printf.printf " -> ";
print_stack s
)
in
print_stack circuit;
Printf.printf "\n"
(* Main function *)
let () =
(* First adjacency list *)
let adj1 = Array.make 3 [] in
adj1.(0) <- [1];
adj1.(1) <- [2];
adj1.(2) <- [0];
print_circuit adj1;
(* Second adjacency list *)
let adj2 = Array.make 7 [] in
adj2.(0) <- [1; 6];
adj2.(1) <- [2];
adj2.(2) <- [0; 3];
adj2.(3) <- [4];
adj2.(4) <- [2; 5];
adj2.(5) <- [0];
adj2.(6) <- [4];
print_circuit adj2;
- Output:
0 -> 1 -> 2 -> 0 0 -> 1 -> 2 -> 0 -> 6 -> 4 -> 2 -> 3 -> 4 -> 5 -> 0
You may Attempt This Online!
\\ Function to print the Eulerian circuit
print_circuit(adj) = {
my(curr_path, circuit, curr_v, next_v);
\\ If the adjacency list is empty, do nothing
if (#adj == 0, return());
curr_path = [1]; \\ Start with vertex 1
circuit = [];
while (#curr_path > 0,
curr_v = curr_path[#curr_path]; \\ Get the last element of curr_path
if (#adj[curr_v] > 0,
next_v = adj[curr_v][1]; \\ Get next vertex from list
adj[curr_v] = vecextract(adj[curr_v], "^1"); \\ Remove the used vertex (remove first element)
curr_path = concat(curr_path, [next_v]); \\ Append the new vertex to curr_path
,
\\ Backtrack and add to the circuit
circuit = concat(circuit, [curr_path[#curr_path]]);
curr_path = vecextract(curr_path, Str("^", #curr_path)); \\ Remove last element
)
);
\\ Print the circuit in reverse order
for (i = 1, #circuit,
print1(circuit[#circuit - i + 1]);
if (i < #circuit, print1(" -> "))
);
print("");
}
\\ First adjacency list
adj1 = List();
listput(adj1, [2]); \\ Vertex 1
listput(adj1, [3]); \\ Vertex 2
listput(adj1, [1]); \\ Vertex 3
print_circuit(adj1);
\\ Second adjacency list
adj2 = List();
listput(adj2, [2, 7]); \\ Vertex 1
listput(adj2, [3]); \\ Vertex 2
listput(adj2, [1, 4]); \\ Vertex 3
listput(adj2, [5]); \\ Vertex 4
listput(adj2, [3, 6]); \\ Vertex 5
listput(adj2, [5]); \\ Vertex 6
listput(adj2, [1]); \\ Vertex 7
print_circuit(adj2);- Output:
1 -> 2 -> 3 -> 1 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 5 -> 3 -> 1 -> 7 -> 1
use strict;
use warnings;
sub print_circuit {
my ($adjacency_list) = @_;
return if !@$adjacency_list;
my @path;
my @circuit;
my $current_vertex = 0; # Start at vertex 0
push @path, $current_vertex;
while (@path) {
if (@{$adjacency_list->[$current_vertex]}) {
push @path, $current_vertex;
my $next_vertex = pop @{$adjacency_list->[$current_vertex]};
$current_vertex = $next_vertex;
} else {
push @circuit, $current_vertex;
$current_vertex = pop @path;
}
}
# Print the circuit
for my $i (reverse 0..$#circuit) {
print $circuit[$i];
print " => " if $i != 0;
}
print "\n";
}
my @adjacency_list1 = (
[1],
[2],
[0]
);
print_circuit(\@adjacency_list1);
my @adjacency_list2 = (
[1, 6],
[2],
[0, 3],
[4],
[2, 5],
[0],
[4]
);
print_circuit(\@adjacency_list2);
- Output:
0 => 1 => 2 => 0 0 => 6 => 4 => 5 => 0 => 1 => 2 => 3 => 4 => 2 => 0
Using 1-based indices. As with all other entries on this page, no attempt to implement VerifyEulerianCircuit().
with javascript_semantics
function hierholser(sequence adj)
integer t = 1
sequence cycle = {t}
adj = deep_copy(adj)
while length(adj[t]) do
cycle &= adj[t][$]
adj[t] = adj[t][1..$-1]
t = cycle[$]
end while
assert(sum(apply(adj,length))=0,"not all edges taken")
return cycle
end function
for adj in {{{2},{3},{1}}, {{2,7},{3},{1,4},{5},{3,6},{1},{5}}} do
printf(1,"%s\n",{join(hierholser(adj)," -> ",fmt:="%d")})
end for
- Output:
1 -> 2 -> 3 -> 1 1 -> 7 -> 5 -> 6 -> 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 1
alternative
with javascript_semantics
function hierholser(sequence adj)
sequence curr_path = {1}, // start with vertex 1
circuit = {}
adj = deep_copy(adj)
while length(curr_path) do
integer v = curr_path[$]
if length(adj[v])!=0 then
// get the next vertex from the adjacency list
integer n = adj[v][1]
adj[v] = adj[v][2..$]
curr_path &= n
else
// backtrack and add to the circuit
circuit &= v
curr_path = curr_path[1..$-1]
end if
end while
assert(sum(apply(adj,length))=0,"not all edges taken")
circuit = reverse(circuit)
return circuit
end function
for adj in {{{2},{3},{1}}, {{2,7},{3},{1,4},{5},{3,6},{1},{5}}} do
printf(1,"%s\n",{join(hierholser(adj)," -> ",fmt:="%d")})
end for
- Output:
More closely matches output of FreeBASIC, Julia, OCaml, and Wren (but still with the 1-based indices)
1 -> 2 -> 3 -> 1 1 -> 2 -> 3 -> 1 -> 7 -> 5 -> 3 -> 4 -> 5 -> 6 -> 1
As with Lua, numbering the vertices from 1 is more natural for Pluto.
do -- Hierholzer's algorithm - based on the Wren and Lua samples
-- find the Eulerian circuit
local function findCircuit( adj : table ) : table
local path, circuit, currV = {}, {}, 1
if # adj > 0 then
path[ 1 ] = currV
while # path > 0 do
if # adj[ currV ] != 0 then
path:insert( currV )
currV = adj[ currV ]:remove()
else
circuit:insert( currV )
currV = path:remove()
end
end
end
return circuit:reverse()
end
local function printCircuit( s : table )
print( if # s > 0 then s:concat( " -> " ) else "(empty)" end )
end
-- first adjacency list
printCircuit( findCircuit( { { 2 }, { 3 }, { 1 } } ) )
-- second adjacency list
printCircuit( findCircuit( { { 2, 7 }, { 3 }, { 1, 4 }, { 5 }, { 3, 6 }, { 1 }, { 5 } } ) )
end
- Output:
1 -> 2 -> 3 -> 1 1 -> 7 -> 5 -> 6 -> 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 1
Structure Stack
Array Data.i(100)
top.i
EndStructure
Procedure InitStack(*s.Stack)
*s\top = -1
EndProcedure
Procedure PushStack(*s.Stack, value.i)
*s\top + 1
*s\data(*s\top) = value
EndProcedure
Procedure.i PopStack(*s.Stack)
Protected value.i = *s\data(*s\top)
*s\top - 1
ProcedureReturn value
EndProcedure
Procedure.i TopStack(*s.Stack)
ProcedureReturn *s\data(*s\top)
EndProcedure
Procedure.i IsEmptyStack(*s.Stack)
ProcedureReturn Bool(*s\top = -1)
EndProcedure
Structure Graph
Array adj.i(100,100)
Array sizes.i(100)
vertices.i
EndStructure
Procedure PrintCircuit(*g.Graph)
Protected curr_path.Stack, circuit.Stack
Dim edge_count.i(100)
InitStack(@curr_path)
InitStack(@circuit)
For i = 0 To *g\vertices - 1
edge_count(i) = *g\sizes(i)
Next
PushStack(@curr_path, 0)
Protected curr_v.i = 0
While Not IsEmptyStack(@curr_path)
If edge_count(curr_v) > 0
PushStack(@curr_path, curr_v)
Protected next_v.i = *g\adj(curr_v, edge_count(curr_v) - 1)
edge_count(curr_v) - 1
curr_v = next_v
Else
PushStack(@circuit, curr_v)
curr_v = TopStack(@curr_path)
PopStack(@curr_path)
EndIf
Wend
While Not IsEmptyStack(@circuit)
Print(Str(PopStack(@circuit)));
If Not IsEmptyStack(@circuit)
Print(" -> ")
EndIf
Wend
PrintN("")
EndProcedure
OpenConsole()
Define g1.Graph
g1\vertices = 3
g1\adj(0,0) = 1 : g1\sizes(0) = 1
g1\adj(1,0) = 2 : g1\sizes(1) = 1
g1\adj(2,0) = 0 : g1\sizes(2) = 1
PrintCircuit(@g1)
Define g2.Graph
g2\vertices = 7
g2\adj(0,0) = 1 : g2\adj(0,1) = 6 : g2\sizes(0) = 2
g2\adj(1,0) = 2 : g2\sizes(1) = 1
g2\adj(2,0) = 0 : g2\adj(2,1) = 3 : g2\sizes(2) = 2
g2\adj(3,0) = 4 : g2\sizes(3) = 1
g2\adj(4,0) = 2 : g2\adj(4,1) = 5 : g2\sizes(4) = 2
g2\adj(5,0) = 0 : g2\sizes(5) = 1
g2\adj(6,0) = 4 : g2\sizes(6) = 1
PrintCircuit(@g2)
PrintN(#CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
Based on code from https://www.geeksforgeeks.org/hierholzers-algorithm-directed-graph/
#!/usr/bin/python
# coding=UTF-8
from __future__ import print_function
def printCircuit(adj):
# adj represents the adjacency list of
# the directed graph
# edge_count represents the number of edges
# emerging from a vertex
edge_count = dict()
for i in range(len(adj)):
# find the count of edges to keep track
# of unused edges
edge_count[i] = len(adj[i])
if len(adj) == 0:
return # empty graph
# Maintain a stack to keep vertices
curr_path = []
# vector to store final circuit
circuit = []
# start from any vertex
curr_path.append(0)
curr_v = 0 # Current vertex
while len(curr_path):
# If there's remaining edge
if edge_count[curr_v]:
# Push the vertex
curr_path.append(curr_v)
# Find the next vertex using an edge
next_v = adj[curr_v][-1]
# and remove that edge
edge_count[curr_v] -= 1
adj[curr_v].pop()
# Move to next vertex
curr_v = next_v
# back-track to find remaining circuit
else:
circuit.append(curr_v)
# Back-tracking
curr_v = curr_path[-1]
curr_path.pop()
# we've got the circuit, now print it in reverse
for i in range(len(circuit) - 1, -1, -1):
print(circuit[i], end = "")
if i:
print(" -> ", end = "")
# Driver Code
if __name__ == "__main__":
# Input Graph 1
adj1 = [0] * 3
for i in range(3):
adj1[i] = []
# Build the edges
adj1[0].append(1)
adj1[1].append(2)
adj1[2].append(0)
printCircuit(adj1)
print()
# Input Graph 2
adj2 = [0] * 7
for i in range(7):
adj2[i] = []
adj2[0].append(1)
adj2[0].append(6)
adj2[1].append(2)
adj2[2].append(0)
adj2[2].append(3)
adj2[3].append(4)
adj2[4].append(2)
adj2[4].append(5)
adj2[5].append(0)
adj2[6].append(4)
printCircuit(adj2)
print()
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
# Function to print the Eulerian circuit
print_circuit <- function(adj) {
if (length(adj) == 0) {
return() # If the adjacency list is empty, do nothing
}
curr_path <- c(1) # Start with vertex 1 (R uses 1-based indexing)
circuit <- c()
while (length(curr_path) > 0) {
curr_v <- curr_path[length(curr_path)] # Get the last element of curr_path
if (length(adj[[curr_v]]) > 0) {
next_v <- adj[[curr_v]][1] # Get next vertex from list
adj[[curr_v]] <- adj[[curr_v]][-1] # Remove the used vertex
curr_path <- c(curr_path, next_v) # Append the new vertex to curr_path
} else {
# Backtrack and add to the circuit
circuit <- c(circuit, curr_path[length(curr_path)])
curr_path <- curr_path[-length(curr_path)]
}
}
# Print the circuit in reverse order
for (i in seq_along(circuit)) {
cat(circuit[length(circuit) - i + 1])
if (i < length(circuit)) {
cat(" -> ")
}
}
cat("\n")
}
# Testing code
adj1 <- list()
adj2 <- list()
# First adjacency list
adj1[[1]] <- c(2) # Note: R uses 1-based indexing
adj1[[2]] <- c(3)
adj1[[3]] <- c(1)
print_circuit(adj1)
# Second adjacency list
adj2[[1]] <- c(2, 7)
adj2[[2]] <- c(3)
adj2[[3]] <- c(1, 4)
adj2[[4]] <- c(5)
adj2[[5]] <- c(3, 6)
adj2[[6]] <- c(5)
adj2[[7]] <- c(1)
print_circuit(adj2)
- Output:
1 -> 2 -> 3 -> 1 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 5 -> 3 -> 1 -> 7 -> 1
#lang racket
(require racket/hash)
;; Main function that runs the algorithm on two example graphs
(define (main)
;; First adjacency list example
(define adj-list1
'((1) ; Vertex 0 connects to vertex 1
(2) ; Vertex 1 connects to vertex 2
(0))) ; Vertex 2 connects to vertex 0
(print-circuit adj-list1)
;; Second adjacency list example
(define adj-list2
'((1 6) ; Vertex 0 connects to vertices 1, 6
(2) ; Vertex 1 connects to vertex 2
(0 3) ; Vertex 2 connects to vertices 0, 3
(4) ; Vertex 3 connects to vertex 4
(2 5) ; Vertex 4 connects to vertices 2, 5
(0) ; Vertex 5 connects to vertex 0
(4))) ; Vertex 6 connects to vertex 4
(print-circuit adj-list2))
;; Print the Eulerian circuit
(define (print-circuit adj-list)
(if (null? adj-list)
(void)
(let ([adj-hash (create-adjacency-hash adj-list)]
[start-vertex 0])
(define final-circuit
(find-circuit start-vertex (list start-vertex) '() adj-hash))
(print-result (reverse final-circuit)))))
;; Convert adjacency list to hash table
(define (create-adjacency-hash adj-list)
(for/hash ([i (in-naturals 0)]
[neighbors adj-list])
(values i neighbors)))
;; Main Hierholzer algorithm implementation
(define (find-circuit current-vertex path circuit adj-hash)
(cond
[(null? path) circuit]
[else
(define neighbors (hash-ref adj-hash current-vertex '()))
(cond
[(null? neighbors)
;; No more neighbors - backtrack
(define new-circuit (cons current-vertex circuit))
(cond
[(null? path) new-circuit]
[else
(define-values (new-current rest-path) (values (car path) (cdr path)))
(find-circuit new-current rest-path new-circuit adj-hash)])]
[else
;; Has neighbors - move forward
(define next-vertex (last neighbors))
(define remaining-neighbors (drop-right neighbors 1))
(define new-adj-hash (hash-set adj-hash current-vertex remaining-neighbors))
(define new-path (cons current-vertex path))
(find-circuit next-vertex new-path circuit new-adj-hash)])]))
;; Print the result with arrows
(define (print-result lst)
(cond
[(null? lst) (newline)]
[(null? (cdr lst)) (printf "~a~n" (car lst))]
[else
(printf "~a => " (car lst))
(print-result (cdr lst))]))
;; Run main
(main)
- Output:
0 => 2 => 1 => 0 0 => 2 => 4 => 3 => 2 => 1 => 0 => 5 => 4 => 6 => 0
say join ' -> ', .&hierholser for ([1],[2],[0]), ([1,6],[2],[0,3],[4],[2,5],[0],[4]);
sub hierholser (@graph) {
my @cycle = 0;
@cycle.push: @graph[@cycle.tail].pop while @graph[@cycle.tail].elems;
@cycle;
}
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
You may Attempt This Online!
use std::collections::HashMap;
use std::vec::Vec;
fn print_circuit(mut adj: Vec<Vec<usize>>) {
// adj represents the adjacency list of
// the directed graph
// edge_count represents the number of edges
// emerging from a vertex
let mut edge_count: HashMap<usize, usize> = HashMap::new();
for i in 0..adj.len() {
//find the count of edges to keep track
//of unused edges
edge_count.insert(i, adj[i].len());
}
if adj.is_empty() {
return; //empty graph
}
// Maintain a stack to keep vertices
let mut curr_path: Vec<usize> = Vec::new();
// vector to store final circuit
let mut circuit: Vec<usize> = Vec::new();
// start from any vertex
curr_path.push(0);
let mut curr_v: usize = 0; // Current vertex
while !curr_path.is_empty() {
// If there's remaining edge
if *edge_count.get(&curr_v).unwrap() > 0 {
// Push the vertex
curr_path.push(curr_v);
// Find the next vertex using an edge
let next_v = adj[curr_v].pop().unwrap();
// and remove that edge
*edge_count.get_mut(&curr_v).unwrap() -= 1;
// Move to next vertex
curr_v = next_v;
}
// back-track to find remaining circuit
else {
circuit.push(curr_v);
// Back-tracking
curr_v = curr_path.pop().unwrap();
}
}
// we've got the circuit, now print it in reverse
for i in (0..circuit.len()).rev() {
print!("{}", circuit[i]);
if i > 0 {
print!(" -> ");
}
}
}
// Driver program to check the above function
fn main() {
let mut adj1: Vec<Vec<usize>> = Vec::new();
// First adjacency list
adj1.resize(3, Vec::new());
// Build the edges
adj1[0].push(1);
adj1[1].push(2);
adj1[2].push(0);
print_circuit(adj1);
println!();
// Second adjacency list
let mut adj2: Vec<Vec<usize>> = Vec::new();
adj2.resize(7, Vec::new());
adj2[0].push(1);
adj2[0].push(6);
adj2[1].push(2);
adj2[2].push(0);
adj2[2].push(3);
adj2[3].push(4);
adj2[4].push(2);
adj2[4].push(5);
adj2[5].push(0);
adj2[6].push(4);
print_circuit(adj2);
}
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
import scala.collection.mutable.Stack
import scala.collection.mutable.ListBuffer
object HierholzerAlgorithm {
def main(args: Array[String]): Unit = {
val adjacencyList1 = ListBuffer(List(1), List(2), List(0))
printCircuit(adjacencyList1)
val adjacencyList2 = ListBuffer(List(1, 6), List(2), List(0, 3), List(4), List(2, 5), List(0), List(4))
printCircuit(adjacencyList2)
}
def printCircuit(adjacencyList: ListBuffer[List[Int]]): Unit = {
if (adjacencyList.isEmpty) {
return
}
val path = Stack[Int]()
val circuit = ListBuffer[Int]()
var currentVertex = 0 // Start at vertex 0
path.push(currentVertex)
while (path.nonEmpty) {
if (adjacencyList(currentVertex).nonEmpty) {
path.push(currentVertex)
val nextVertex = adjacencyList(currentVertex).last
adjacencyList(currentVertex) = adjacencyList(currentVertex).init
currentVertex = nextVertex
} else { // Back-tracking
circuit += currentVertex
currentVertex = path.pop()
}
}
// Print the circuit
println(circuit.reverse.mkString(" => "))
}
}
- Output:
0 => 1 => 2 => 0 0 => 6 => 4 => 5 => 0 => 1 => 2 => 3 => 4 => 2 => 0
func printCircuit(_ adjacencyList: inout [[Int]]) {
guard !adjacencyList.isEmpty else {
return
}
var path: [Int] = []
var circuit: [Int] = []
var currentVertex = 0 // Start at vertex 0
path.append(currentVertex)
while !path.isEmpty {
if !adjacencyList[currentVertex].isEmpty {
path.append(currentVertex)
let nextVertex = adjacencyList[currentVertex].last!
adjacencyList[currentVertex].removeLast()
currentVertex = nextVertex
} else {
circuit.append(currentVertex)
currentVertex = path.removeLast()
}
}
// Print the circuit
for i in stride(from: circuit.count - 1, through: 0, by: -1) {
print(circuit[i], terminator: i != 0 ? " => " : "\n")
}
}
var adjacencyList1 = [
[1],
[2],
[0]
]
printCircuit(&adjacencyList1)
var adjacencyList2 = [
[1, 6],
[2],
[0, 3],
[4],
[2, 5],
[0],
[4]
]
printCircuit(&adjacencyList2)
- Output:
0 => 1 => 2 => 0 0 => 6 => 4 => 5 => 0 => 1 => 2 => 3 => 4 => 2 => 0
proc print_circuit {adjacency_list} {
# Check if adjacency list is empty
if {[llength $adjacency_list] == 0} {
return
}
set path {}
set circuit {}
set current_vertex 0 ;# Tcl lists are 0-based
# Add current vertex to path
lappend path $current_vertex
while {[llength $path] > 0} {
# Get the adjacency list for current vertex
set current_adj_list [lindex $adjacency_list $current_vertex]
if {[llength $current_adj_list] > 0} {
# Add current vertex to path
lappend path $current_vertex
# Remove and get the first element from adjacency list
set next_vertex [lindex $current_adj_list 0]
set current_adj_list [lreplace $current_adj_list 0 0]
# Update the adjacency list in the main list
set adjacency_list [lreplace $adjacency_list $current_vertex $current_vertex $current_adj_list]
set current_vertex $next_vertex
} else {
# Add current vertex to circuit
lappend circuit $current_vertex
# Remove and get the last element from path
set current_vertex [lindex $path end]
set path [lreplace $path end end]
}
}
# Print the circuit in reverse order
set circuit_length [llength $circuit]
for {set i [expr {$circuit_length - 1}]} {$i >= 0} {incr i -1} {
puts -nonewline [lindex $circuit $i]
if {$i != 0} {
puts -nonewline " => "
}
}
puts ""
}
# Test cases
set adjacency_list1 {{1} {2} {0}}
print_circuit $adjacency_list1
set adjacency_list2 {{1 6} {2} {0 3} {4} {2 5} {0} {4}}
print_circuit $adjacency_list2
- Output:
0 => 1 => 2 => 0 0 => 1 => 2 => 0 => 6 => 4 => 2 => 3 => 4 => 5 => 0
import "./seq" for Stack
/* Function to print the Eulerian circuit */
var printCircuit = Fn.new { |adj|
// if the adjacency list is empty, do nothing
if (adj.isEmpty) return
var currPath = Stack.new()
var circuit = Stack.new()
currPath.push(0) // start with vertex 0
while (!currPath.isEmpty) {
var currV = currPath.peek()
if (!adj[currV].isEmpty) {
// get the next vertex from the adjacency list
var nextV = adj[currV][0]
adj[currV].removeAt(0) // remove the edge
currPath.push(nextV)
} else {
// backtrack and add to the circuit
circuit.push(currPath.pop())
}
}
// print the circuit in reverse order
var printStack // recursive
printStack = Fn.new { |s|
if (!s.isEmpty) {
System.write(s.pop())
if (!s.isEmpty) System.write(" -> ")
printStack.call(s)
}
}
printStack.call(circuit)
System.print()
}
// first adjacency list
var adj1 = [ [1], [2], [0] ]
printCircuit.call(adj1)
// second adjacency list
var adj2 = [ [1, 6], [2], [0, 3], [4], [2, 5], [0], [4] ]
printCircuit.call(adj2)
- Output:
0 -> 1 -> 2 -> 0 0 -> 1 -> 2 -> 0 -> 6 -> 4 -> 2 -> 3 -> 4 -> 5 -> 0
// Rosetta Code problem: https://rosettacode.org/wiki/Hierholze's_Algorithm
// by Jjuanhdez, 11/2024
rem Initialize arrays and stacks
dim adj(10, 10) rem adjacency list
dim adjCnt(10) rem count of edges for each vertex
dim currPath(100) rem current path stack
dim circuit(100) rem final circuit stack
// currPathTop rem top of current path stack
// circuitTop rem top of circuit stack
rem First adjacency list
initArrays()
adj(0,0) = 1: adjCnt(0) = 1
adj(1,0) = 2: adjCnt(1) = 1
adj(2,0) = 0: adjCnt(2) = 1
printCircuit()
rem Second adjacency list
initArrays()
adj(0,0) = 1: adj(0,1) = 6: adjCnt(0) = 2
adj(1,0) = 2: adjCnt(1) = 1
adj(2,0) = 0: adj(2,1) = 3: adjCnt(2) = 2
adj(3,0) = 4: adjCnt(3) = 1
adj(4,0) = 2: adj(4,1) = 5: adjCnt(4) = 2
adj(5,0) = 0: adjCnt(5) = 1
adj(6,0) = 4: adjCnt(6) = 1
printCircuit()
end
sub initArrays()
currPathTop = 0
circuitTop = 0
for i = 0 to 9
adjCnt(i) = 0
for j = 0 to 9
adj(i,j) = -1
next j
next i
end sub
sub pushCurrPath(value)
currPath(currPathTop) = value
currPathTop = currPathTop + 1
end sub
sub popCurrPath()
currPathTop = currPathTop - 1
return currPath(currPathTop)
end sub
sub pushCircuit(value)
circuit(circuitTop) = value
circuitTop = circuitTop + 1
end sub
rem Subroutine to print the Eulerian circuit
sub printCircuit()
pushCurrPath(0)
while currPathTop > 0
currV = currPath(currPathTop - 1)
if adjCnt(currV) > 0 then
nextV = adj(currV, adjCnt(currV) - 1)
adjCnt(currV) = adjCnt(currV) - 1
pushCurrPath(nextV)
else
v = popCurrPath()
pushCircuit(v)
endif
wend
for i = circuitTop - 1 to 0 step -1
print circuit(i);
if i > 0 print " -> ";
next i
print
end sub
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
const std = @import("std");
fn printCircuit(adj: []const []const u32, allocator: std.mem.Allocator) !void {
// adj represents the adjacency list of the directed graph
// edge_count represents the number of edges emerging from a vertex
var edge_count = std.AutoHashMap(u32, u32).init(allocator);
defer edge_count.deinit();
for (adj, 0..) |edges, i| {
// find the count of edges to keep track of unused edges
try edge_count.put(@intCast(i), @intCast(edges.len));
}
if (adj.len == 0) return; // empty graph
// Maintain a stack to keep vertices
var curr_path = std.ArrayList(u32).init(allocator);
defer curr_path.deinit();
// vector to store final circuit
var circuit = std.ArrayList(u32).init(allocator);
defer circuit.deinit();
// Create mutable copies of adjacency lists
var adj_mutable = try allocator.alloc(std.ArrayList(u32), adj.len);
defer {
for (adj_mutable) |*list| {
list.deinit();
}
allocator.free(adj_mutable);
}
for (adj, 0..) |edges, i| {
adj_mutable[i] = std.ArrayList(u32).init(allocator);
try adj_mutable[i].appendSlice(edges);
}
// start from any vertex
try curr_path.append(0);
var curr_v: u32 = 0; // Current vertex
while (curr_path.items.len > 0) {
// If there's remaining edge
if (edge_count.get(curr_v).? > 0) {
// Push the vertex
try curr_path.append(curr_v);
// Find the next vertex using an edge
const next_v = adj_mutable[curr_v].items[adj_mutable[curr_v].items.len - 1];
// and remove that edge
edge_count.put(curr_v, edge_count.get(curr_v).? - 1) catch unreachable;
_ = adj_mutable[curr_v].pop();
// Move to next vertex
curr_v = next_v;
} else {
// back-track to find remaining circuit
try circuit.append(curr_v);
// Back-tracking
curr_v = curr_path.items[curr_path.items.len - 1];
_ = curr_path.pop();
}
}
// we've got the circuit, now print it in reverse
const stdout = std.io.getStdOut().writer();
var i: usize = circuit.items.len;
while (i > 0) {
i -= 1;
try stdout.print("{}", .{circuit.items[i]});
if (i > 0) try stdout.print(" -> ", .{});
}
try stdout.print("\n", .{});
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
// First adjacency list
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var adj1 = try allocator.alloc([]const u32, 3);
defer allocator.free(adj1);
adj1[0] = &[_]u32{1};
adj1[1] = &[_]u32{2};
adj1[2] = &[_]u32{0};
try printCircuit(adj1, allocator);
// Second adjacency list
var adj2 = try allocator.alloc([]const u32, 7);
defer allocator.free(adj2);
adj2[0] = &[_]u32{1, 6};
adj2[1] = &[_]u32{2};
adj2[2] = &[_]u32{0, 3};
adj2[3] = &[_]u32{4};
adj2[4] = &[_]u32{2, 5};
adj2[5] = &[_]u32{0};
adj2[6] = &[_]u32{4};
try printCircuit(adj2, allocator);
}
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0