Python exercise: verify a dependency order without confusing it with reachability

Operation contract

The build graph names three steps and two dependencies. The proposed order lists every step exactly once and places each prerequisite before its dependent step. A second order violates one edge and is rejected. The checker does not generate an order or silently discard duplicate nodes; it validates graph and proposal shapes first.

Failure and ownership boundary

A cyclic graph has no valid complete order, but this verifier does not diagnose which cycle caused rejection. For construction use Python topological sort: dependency order and cycle rejection; for graph grouping use Python strongly connected components: partition a directed dependency graph. This exercise answers the narrower question of whether one submitted order satisfies the supplied edge set.

Working program

def valid_order(nodes, edges, proposed):
    if type(nodes) is not list or len(nodes) > 30 or any(type(node) is not str or not node for node in nodes) or len(set(nodes)) != len(nodes):
        raise ValueError("node set")
    if type(edges) is not list or len(edges) > 100 or any(type(edge) is not tuple or len(edge) != 2 or edge[0] not in nodes or edge[1] not in nodes for edge in edges):
        raise ValueError("edge set")
    if type(proposed) is not list or len(proposed) != len(nodes) or any(type(node) is not str for node in proposed) or set(proposed) != set(nodes):
        return False
    position = {node: index for index, node in enumerate(proposed)}
    return all(position[source] < position[target] for source, target in edges)

steps = ["read", "validate", "publish"]
edges = [("read", "validate"), ("validate", "publish")]
print(valid_order(steps, edges, ["read", "validate", "publish"]))
print(valid_order(steps, edges, ["validate", "read", "publish"]))

Output

True
False

Costs and limits

After validation, building positions costs O(V) expected dictionary work and checking E edges costs O(E). This implementation checks edge endpoint membership against a list during validation, so its actual bound includes O(EV); the 30-node/100-edge limits keep the fixture small. A larger verifier should build a node set once.

Common Mistakes

• A permutation is not valid merely because it lists every node.
• A false result does not identify a cycle or construct a repair.

Connected lessons

Python topological sort: dependency order and cycle rejection, Python strongly connected components: partition a directed dependency graph, Python graph BFS: mark a vertex when it enters the queue.