Balance and Weak Connectivity
Decide whether a directed multigraph has an Euler trail using degrees and weak connectivity.
Original synthetic inputs; computed records, not biological motion. The written trace below is the text equivalent.The problem
An Euler trail uses every edge exactly once. In a directed graph, an open trail has one node whose outgoing count exceeds its incoming count by one, one node with the opposite imbalance, and zero imbalance everywhere else. A circuit has zero imbalance at every incident node. Those degree facts are necessary but not sufficient: two disconnected balanced cycles satisfy every degree equation and still have no single trail through all edges.
Trace the program
The demo graph is the three-edge path from ATGCG: AT to TG, TG to GC, and GC to CG. AT has imbalance plus one, CG has minus one, and the two middle nodes balance. The nodes form one weak component, so the classification is an open path from AT to CG. The program removes isolated nodes from the connectivity test because they carry no edge and cannot join an edge-using trail.
The live graph
Edit the explicit edge list and run the program. The result reports whether a trail exists, whether it is a path or a cycle, and the deterministic endpoints. 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]
if not weakly_connected(nodes, edges):
result = {'has_path': False, 'kind': 'none', 'start': None, 'end': None}
elif all((b == 0 for b in bal.values())):
result = {'has_path': True, 'kind': 'cycle', 'start': nodes[0], 'end': 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]))):
result = {'has_path': True, 'kind': 'path', 'start': plus[0], 'end': minus[0]}
else:
result = {'has_path': False, 'kind': 'none', 'start': None, 'end': None}
print(result)
{
"has_path": true,
"kind": "path",
"start": "AT",
"end": "CG"
}Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
Your turn
For each supplied directed graph, return has_path, kind as path, cycle or none, and deterministic start and end nodes. Use first node order for a circuit start. Return null for both endpoints when no trail uses every edge. Test weak connectivity among nodes incident to edges. Set result to that object.
import json
result = {'has_path': False, 'kind': 'none', 'start': None, 'end': None}
print(result)
For each supplied directed graph, return has_path, kind as path, cycle or none, and deterministic start and end nodes. Use first node order for a circuit start. Return null for both endpoints when no trail uses every edge. Test weak connectivity among nodes incident to edges. Set result to that object.
{
"has_path": false,
"kind": "none",
"start": null,
"end": null
}Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
Boundaries and interpretation
The input is an explicit finite graph, not a claim about a sequenced genome. Weak connectivity ignores edge direction, which is the right test for one trail through every edge; strong connectivity is a different and stronger condition. Degree balance alone can accept disconnected components. The page does not compute an Euler trail yet, and it does not claim that a balanced graph has a unique biological interpretation.
The degree rule counts edge occurrences, so two parallel edges contribute two to both the outgoing and incoming totals. A self-loop contributes one to each count at the same node. A node with no incident edge is left out of the connectivity test because it cannot help a trail.
The classification uses edge multiplicities, so a repeated edge changes the degree counts even when its endpoints are unchanged. Parallel edges must be counted separately rather than collapsed into one adjacency. The connectivity test is also over the incident nodes, which means an isolated node does not make a valid trail fail.
Recap
- An open Euler trail has one plus-one imbalance and one minus-one imbalance.
- A circuit has zero imbalance at every incident node.
- Balance without weak connectivity is not enough for a trail.
Synthetic data: CC0-1.0. No personal data are sent anywhere.