Splice an Euler Trail
Use Hierholzer splicing to consume every edge and spell the reconstructed string.
Original synthetic inputs; computed records, not biological motion. The written trace below is the text equivalent.The problem
A greedy walk can enter a dead end before every edge is used. Hierholzer's method postpones that problem by walking until it cannot continue, then backtracking to the most recent node with unused outgoing edges and splicing a cycle into the trail. The final node path is reversed from the postorder removal of nodes. The reconstructed string starts with the first node and appends only the last character of every later node, because consecutive nodes overlap by k minus one letters.
Trace the program
The demo has three edges AT to TG, TG to GC, and GC to CG. A walk from AT reaches CG after using all three edges, so the node path is AT, TG, GC, CG and the reconstruction is ATGCG. On a graph with a branch, the first walk can stop early and leave a cycle unused. The splice then inserts that cycle at the earlier node, which is why a node may appear twice in the final path.
The live graph
Edit the explicit edge list and run the program. The result contains has_path, the complete node path, and its reconstruction. Reset restores the demonstration graph.
import json
def nodes_of(edges):
nodes = []
for a, b in edges:
for v in (a, b):
if v not in nodes:
nodes.append(v)
return nodes
def degrees(nodes, edges):
out = {v: 0 for v in nodes}
inc = {v: 0 for v in nodes}
for a, b in edges:
out[a] += 1
inc[b] += 1
return (out, inc)
def weakly_connected(nodes, edges):
adj = {v: set() for v in nodes}
for a, b in edges:
adj[a].add(b)
adj[b].add(a)
seen = {nodes[0]}
stack = [nodes[0]]
while stack:
v = stack.pop()
for w in adj[v]:
if w not in seen:
seen.add(w)
stack.append(w)
return len(seen) == len(nodes)
edges = [tuple(e) for e in json.loads(input())['edges']]
if not edges:
raise ValueError('invalid input')
nodes = nodes_of(edges)
out, inc = degrees(nodes, edges)
bal = {v: out[v] - inc[v] for v in nodes}
plus = [v for v in nodes if bal[v] == 1]
minus = [v for v in nodes if bal[v] == -1]
start = None
if weakly_connected(nodes, edges):
if all((b == 0 for b in bal.values())):
start = nodes[0]
elif len(plus) == 1 and len(minus) == 1 and all((bal[v] == 0 for v in nodes if v not in (plus[0], minus[0]))):
start = plus[0]
if start is None:
result = {'has_path': False, 'path': None, 'reconstruction': None}
else:
at = {v: [] for v in nodes}
for i, (a, b) in enumerate(edges):
at[a].append(i)
used = [False] * len(edges)
pos = {v: 0 for v in nodes}
stack, path = ([start], [])
while stack:
v = stack[-1]
while pos[v] < len(at[v]) and used[at[v][pos[v]]]:
pos[v] += 1
if pos[v] < len(at[v]):
i = at[v][pos[v]]
used[i] = True
stack.append(edges[i][1])
else:
path.append(stack.pop())
path.reverse()
text = path[0] + ''.join((v[-1] for v in path[1:])) if path else ''
result = {'has_path': True, 'path': path, 'reconstruction': text}
print(result)
{
"has_path": true,
"path": [
"AT",
"TG",
"GC",
"CG"
],
"reconstruction": "ATGCG"
}Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
Your turn
For each supplied graph, return has_path, an Euler node path, and its reconstruction. Follow outgoing edges in input order when Hierholzer has a choice. If no Euler trail exists, return null path and null reconstruction rather than a partial walk. Set result to that object.
import json
result = {'has_path': True, 'path': [], 'reconstruction': ''}
print(result)
For each supplied graph, return has_path, an Euler node path, and its reconstruction. Follow outgoing edges in input order when Hierholzer has a choice. If no Euler trail exists, return null path and null reconstruction rather than a partial walk. Set result to that object.
{
"has_path": true,
"path": [],
"reconstruction": ""
}Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
Boundaries and interpretation
The page computes a trail through the declared edge multiset. It does not resolve repeats longer than k, choose between alternative trails, or prove that the reconstructed string is the biological source. Input order is a deterministic tie-break for the algorithm, not evidence about a sequencing instrument. A trail that uses every edge can still be one of several valid reconstructions.
The path length is the number of edges plus one, which is a useful check after splicing; a shorter path has left an edge unused. The reconstruction length is k plus the number of edges minus one, because each later node adds one new character.
The splice is driven by edge identifiers, not by node names, so two parallel edges remain distinguishable. After the walk, the path length must equal the number of edges plus one; a shorter path would mean some edge was skipped and is not reported as a successful trail. The reconstruction then adds one character per later node.
Recap
- Hierholzer splices unused cycles into a walk instead of abandoning it.
- A repeated node can still have unused outgoing edges.
- Reconstruction appends one character per later node.
Synthetic data: CC0-1.0. No personal data are sent anywhere.