Repeats and Branches
Enumerate edge-distinct trails and separately deduplicate the reconstructed strings.
Original synthetic inputs; computed records, not biological motion. The written trace below is the text equivalent.The problem
A branch node has more than one outgoing edge. That fact alone does not determine how many complete trails exist, because later choices can multiply or reconverge. Two different edge-order trails can also spell the same string when parallel edges carry identical labels. The useful report therefore separates three quantities: the branch nodes, the number of edge-distinct complete trails from a declared start, and the sorted set of distinct reconstructed strings.
Trace the program
The demo graph from ATGTGC has a branch at TG with two outgoing edges, TG to GT and TG to GC. Taking TG to GC immediately reaches a dead end before the GT loop is used, whereas taking TG to GT first returns to TG and then finishes along TG to GC, giving 1 complete trail and string ATGTGC. When two complete cycles share a branch node and return to it, the trail can traverse the cycles in either order and still consume every edge.
The live graph
Edit the edge list or declared start and run the program. The result reports branch nodes in first-occurrence order, the count of complete trails, and sorted distinct strings. 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
data = json.loads(input())
edges = [tuple(e) for e in data['edges']]
start = data['start']
if not edges or start not in nodes_of(edges):
raise ValueError('invalid input')
nodes = nodes_of(edges)
out = {v: 0 for v in nodes}
for a, b in edges:
out[a] += 1
branches = [v for v in nodes if out[v] > 1]
trails = []
def walk(v, used, path):
if len(used) == len(edges):
trails.append(path)
return
for i, (a, b) in enumerate(edges):
if i not in used and a == v:
walk(b, used | {i}, path + [b])
walk(start, frozenset(), [start])
strings = sorted({p[0] + ''.join((v[-1] for v in p[1:])) for p in trails})
result = {'branches': branches, 'trails': len(trails), 'strings': strings}
print(result)
{
"branches": [
"TG"
],
"trails": 1,
"strings": [
"ATGTGC"
]
}Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
Your turn
For each supplied graph and declared start, return every node whose outdegree exceeds one, the number of edge-distinct complete Euler trails from that start, and the sorted set of distinct reconstructed strings. Do not apply an arbitrary traversal tie-break that suppresses alternatives. Set result to an object with branches, trails and strings.
import json
data = json.loads(input())
edges = data['edges']
nodes = []
for a, b in edges:
for v in (a, b):
if v not in nodes:
nodes.append(v)
out = {v: 0 for v in nodes}
for a, b in edges:
out[a] += 1
branches = [v for v in nodes if out[v] > 1]
result = {'branches': branches, 'trails': 0, 'strings': []}
print(result)
For each supplied graph and declared start, return every node whose outdegree exceeds one, the number of edge-distinct complete Euler trails from that start, and the sorted set of distinct reconstructed strings. Do not apply an arbitrary traversal tie-break that suppresses alternatives. Set result to an object with branches, trails and strings.
{
"branches": [
"TG"
],
"trails": 0,
"strings": []
}Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
Boundaries and interpretation
Enumeration is exact only for the supplied finite graph and start. The number of trails can grow quickly, and parallel edges are counted separately even when their strings coincide. The distinct-string set is a text result, not a biological consensus. The page does not choose a most likely assembly, use coverage, or model sequencing errors; it makes alternative trail structure visible before any such claim.
A trail is identified by the order of edge ids, so swapping two parallel edges with identical labels produces a different trail but the same reconstructed string. The branch list uses outdegree in the declared graph, not the number of distinct outgoing labels. The count is exact for the supplied finite graph and start.
The trail list is produced from edge identifiers, so parallel edges yield distinct trails even when their labels are identical. The string set is computed after that enumeration and therefore cannot hide a trail from the count. This separation lets a reader compare how many routes exist with how many textual answers they produce.
Recap
- Branch outdegree is not the number of complete trails.
- Edge-distinct trails can collapse to one distinct string.
- Strings are sorted after enumeration, not used to suppress trails.
Synthetic data: CC0-1.0. No personal data are sent anywhere.