--- title: 'Activity Diagrams' source: 'https://academia.sh/en/courses/modeling-and-representation/activity-diagrams' course: 'Modeling and Representation' language: en updated: '2026-08-17T18:08:14+00:00' license: 'CC BY-SA 4.0' --- # Activity Diagrams Counting, with topological sort, how many total orderings the diagram accepts when it shows a workflow through prerequisites: ten tasks, thirteen prerequisites, 168 total orderings, a six-layer critical path, and where adding one prerequisite sends the 168. The previous lesson counted how the sequence notation shows one run in full and the other 23 runs not at all. Every message that notation wrote carried a sequence number, and those numbers stood as if they were mandatory. Yet most of the work in the shop does not wait on the rest: there is no priority between informing the customer and computing the cost, and the two can be done in either order. The activity notation corrects this. It does not write order, it writes **prerequisites**: it states which task can start after which tasks, not which one is done first. This frees the notation from telling a lie. In exchange, it does something else: it describes **not a single execution, but a set of executions** at once. This lesson's measure is the size of that set. ## A Partial Order Describes a Set The shop's workflow contains ten tasks: intake, allocating stock, assigning a technician, reserving a workbench, informing the customer, computing cost, processing, documenting, issuing an invoice, closing. There are thirteen prerequisites among them. These thirteen prerequisites establish a **partial order**: they fix the order of some task pairs and leave others free. What the system actually does, however, is a **total order**. While a work order runs, tasks happen one at a time and fall into a specific order; that run has exactly one order. The notation, on the other hand, accepts all of these orders at once. The number of accepted orders is the measure of the looseness the notation leaves. This number is how many distinct outputs the **topological sort** from the Data Structures course can produce. That lesson built the in-degree-based procedure and showed that the ordering is not unique — that the algorithm makes a choice whenever more than one vertex is in the queue — but it did not count how many distinct **results** those choices produce. This lesson does that count. The procedure is not rewritten; it is called exactly as it is. ## The Number Itself ```python """Activity notation: how many total orderings a partial order accepts at once. The ACTIVITY and total_orderings() definitions from the shared reference are built exactly as they are there; the topological sort is the in-degree-based procedure from the Data Structures course.""" from collections import deque from itertools import combinations ACTIVITY = { # task -> prerequisite tasks "intake": [], "allocate_stock": ["intake"], "assign_technician": ["intake"], "reserve_workbench": ["assign_technician"], "inform_customer": ["intake"], "compute_cost": ["allocate_stock"], "process": ["allocate_stock", "reserve_workbench"], "document": ["process"], "issue_invoice": ["compute_cost", "process"], "close": ["document", "issue_invoice", "inform_customer"], } def total_orderings(prereqs): tasks = list(prereqs) result = [] def visit(remaining, sequence): if not remaining: result.append(tuple(sequence)) return for i in remaining: if all(o in sequence for o in prereqs[i]): sequence.append(i) visit([x for x in remaining if x != i], sequence) sequence.pop() visit(tasks, []) return result def adjacency(prereqs): """Prerequisite mapping -> directed graph: an edge if a task depends on a prerequisite.""" adj = {i: [] for i in prereqs} for i, predecessors in prereqs.items(): for o in predecessors: adj[o].append(i) return adj def topological_sort(adj): """The in-degree-based procedure from the Data Structures course, unchanged.""" in_degree = {v: 0 for v in adj} for v in adj: for t in adj[v]: in_degree[t] += 1 queue = deque(sorted(v for v in in_degree if in_degree[v] == 0)) result = [] while queue: v = queue.popleft() result.append(v) for t in adj[v]: in_degree[t] -= 1 if in_degree[t] == 0: queue.append(t) return result if len(result) == len(adj) else None def layers(adj): in_degree = {v: 0 for v in adj} for v in adj: for t in adj[v]: in_degree[t] += 1 ready = sorted(v for v in in_degree if in_degree[v] == 0) result, processed = [], 0 while ready: result.append(ready) processed += len(ready) next_ready = [] for v in ready: for t in adj[v]: in_degree[t] -= 1 if in_degree[t] == 0: next_ready.append(t) ready = sorted(next_ready) return result if processed == len(adj) else None def transitive_predecessors(prereqs): """Transitive closure: the tasks that must necessarily come before each task.""" closure = {i: set(prereqs[i]) for i in prereqs} changed = True while changed: changed = False for i in closure: updated = set(closure[i]) for o in closure[i]: updated |= closure[o] if updated != closure[i]: closure[i] = updated changed = True return closure def incomparable_pairs(prereqs): closure = transitive_predecessors(prereqs) return [(a, b) for a, b in combinations(sorted(prereqs), 2) if b not in closure[a] and a not in closure[b]] def factorial(n): s = 1 for i in range(2, n + 1): s *= i return s TASKS = len(ACTIVITY) PREREQS = sum(len(v) for v in ACTIVITY.values()) ORDERINGS = total_orderings(ACTIVITY) print("SYSTEM : each run realizes a SINGLE execution order") print("NOTATION:", TASKS + PREREQS, "symbols =", TASKS, "tasks +", PREREQS, "prerequisites") print("COST :", len(ORDERINGS), "total orderings are accepted | drawing a single ordering gives coverage", round(1 / len(ORDERINGS), 4)) print() ADJ = adjacency(ACTIVITY) print("topological sort gives a single output:") print(" ", topological_sort(ADJ)) print("the same graph's number of valid outputs:", len(ORDERINGS)) LAYERS = layers(ADJ) print("layers (tasks that can start at the same time):") for i, layer in enumerate(LAYERS, 1): print(f" {i}. {layer}") print("critical path length:", len(LAYERS), "steps | sequential execution", TASKS, "steps") print() INCOMPARABLE = incomparable_pairs(ACTIVITY) PAIRS = factorial(TASKS) // (factorial(2) * factorial(TASKS - 2)) print("task pairs:", PAIRS, "| pairs whose order the prerequisites fix:", PAIRS - len(INCOMPARABLE), "| free pairs:", len(INCOMPARABLE)) print("acceptance without prerequisites:", factorial(TASKS), "-> acceptance with prerequisites:", len(ORDERINGS), "| narrowing", factorial(TASKS) // len(ORDERINGS), "x") print() print("if one prerequisite is added, where does 168 land") result = [] for a, b in INCOMPARABLE: for x, y in ((a, b), (b, a)): updated = {i: list(v) for i, v in ACTIVITY.items()} updated[y].append(x) if topological_sort(adjacency(updated)) is None: continue result.append((len(total_orderings(updated)), f"{x} -> {y}")) result.sort() print(" number of prerequisites that can be added:", len(result)) print(" the three choices that narrow the most:") for n, name in result[:3]: print(f" {name:38s} {len(ORDERINGS)} -> {n}") print(" the three choices that narrow the least:") for n, name in result[-3:]: print(f" {name:38s} {len(ORDERINGS)} -> {n}") print(" average of all of them:", round(sum(n for n, _ in result) / len(result), 1)) print(" the two choices that are meaningful in the workshop (DD9):") for x, y in (("inform_customer", "process"), ("document", "issue_invoice")): updated = {i: list(v) for i, v in ACTIVITY.items()} updated[y].append(x) print(f" {x + ' -> ' + y:38s} {len(ORDERINGS)} -> {len(total_orderings(updated))}") print() # DD10: decision node. The rework branch adds an optional task. BRANCH = {i: list(v) for i, v in ACTIVITY.items()} BRANCH["rework"] = ["process"] BRANCH["document"] = ["rework"] ORDERINGS2 = total_orderings(BRANCH) print("if a decision node is added (the rework branch):") print(" symbols", TASKS + PREREQS, "->", len(BRANCH) + sum(len(v) for v in BRANCH.values()) + 1, "(decision node included)") print(" branch A", len(ORDERINGS), "total orderings | branch B", len(ORDERINGS2), "total orderings | total accepted", len(ORDERINGS) + len(ORDERINGS2)) ``` ``` SYSTEM : each run realizes a SINGLE execution order NOTATION: 23 symbols = 10 tasks + 13 prerequisites COST : 168 total orderings are accepted | drawing a single ordering gives coverage 0.006 topological sort gives a single output: ['intake', 'allocate_stock', 'assign_technician', 'inform_customer', 'compute_cost', 'reserve_workbench', 'process', 'document', 'issue_invoice', 'close'] the same graph's number of valid outputs: 168 layers (tasks that can start at the same time): 1. ['intake'] 2. ['allocate_stock', 'assign_technician', 'inform_customer'] 3. ['compute_cost', 'reserve_workbench'] 4. ['process'] 5. ['document', 'issue_invoice'] 6. ['close'] critical path length: 6 steps | sequential execution 10 steps task pairs: 45 | pairs whose order the prerequisites fix: 31 | free pairs: 14 acceptance without prerequisites: 3628800 -> acceptance with prerequisites: 168 | narrowing 21600 x if one prerequisite is added, where does 168 land number of prerequisites that can be added: 28 the three choices that narrow the most: compute_cost -> assign_technician 168 -> 16 document -> compute_cost 168 -> 24 issue_invoice -> inform_customer 168 -> 30 the three choices that narrow the least: inform_customer -> issue_invoice 168 -> 138 compute_cost -> document 168 -> 144 assign_technician -> compute_cost 168 -> 152 average of all of them: 84.0 the two choices that are meaningful in the workshop (DD9): inform_customer -> process 168 -> 96 document -> issue_invoice 168 -> 96 if a decision node is added (the rework branch): symbols 23 -> 26 (decision node included) branch A 168 total orderings | branch B 324 total orderings | total accepted 492 ``` Three numbers: the system realizes **a single order** on every run, the notation writes **23 symbols**, the cost is accepting **168 total orderings**. Drawing a single order gives a coverage of 1/168, that is, 0.006. ## One Output and One Hundred Sixty-Eight Outputs The in-degree-based procedure returns one ordering, and that ordering is valid. But it is not the only valid one; the procedure always gives the same output because it makes its choice alphabetically whenever more than one task is in the queue. This is not a property of the notation; it is **a criterion put in place to make the procedure deterministic**. A different criterion would give a different order, and that order would be valid too. The answer to how many would be valid is 168. Of the forty-five task pairs, the prerequisites fix the order of 31, and **14 are left free**. The free pairs are not independent of one another — fixing one constrains the others — so the number is not two to the fourteenth power but the 168 found by exhaustive count. The real result here is how much work the notation is doing. If no prerequisite had been written, the ten tasks could be done in **3,628,800** distinct orders, the product going from ten down to one. Thirteen prerequisites bring this number down to 168: a **narrowing of 21,600 times**. The notation carries serious information. And yet 168 remains, and 168 is not zero. ## Concurrent Branches and Layers The layer list is the same procedure's second output: the set of tasks that enter the queue on each round. The shop's tasks split into six layers. In the second layer, three tasks become ready at once — informing the customer, allocating stock, assigning a technician — and none of the three waits on the others. The number of layers is the **critical path length**: the shortest number of steps in which all the work could finish with unlimited parallelism. Six steps stand against sequential execution's ten steps. The concurrent-branch notation is what writes this difference; a notation that does not draw the branches reads like a ten-step chain, and the four-step gain becomes invisible. The relationship between the layer structure and 168 is direct: the looseness arises exactly from tasks within a layer being free relative to one another. Concurrency and ambiguity are two names for the same fact here — **the notation can only state parallelism by leaving order free.** ## The Count of Adding One Prerequisite Twenty-eight distinct prerequisites can be added without creating a cycle. Each sends 168 to a different place, and the range is wide: the narrowest result is **16**, the widest is **152**, the average 84. The difference does not come from the length of the written sentence. Each choice is a single prerequisite and adds a single symbol to the notation; yet one symbol brings 168 down to 16 while another leaves it at 152 — saying almost nothing. **How much of the ambiguity a symbol removes is determined by where that symbol is placed**, and this share can vary by more than a factor of nine. The choice that narrows the most is not the choice that means the most in the shop. Forcing computing cost before assigning a technician brings 168 down to 16, but such a rule has no counterpart in how the shop actually operates. The two rules that are genuinely defensible in the shop — the customer is informed before processing begins, the document is prepared before the invoice is issued (**DD9**) — bring 168 down to **96**. The right number is not the smallest number; the right number is the one left by the constraints that genuinely exist. Writing a constraint that does not exist in order to narrow a notation replaces ambiguity with a lie. A side effect of this is that the two kinds of loss separated in the use case lesson show up here as well. Some of the 14 free pairs are **genuinely free** — the shop can do those two tasks in whichever order it likes. Some are only **unwritten**: the order is in fact fixed, but the prerequisite was never put on paper. The notation writes both the same way, because a partial order has no separate symbol for "free" versus "unknown." How many of the fourteen pairs are of which kind cannot be read from the diagram; it can only be separated by asking the process owner one pair at a time. Until that separation is made, the number 168 is the looseness's **upper bound**, not its measure. ## A Decision Node Multiplies Ambiguity The activity notation's third element is the decision: at some point the flow splits into two branches based on a condition. Such a branch exists in the shop — if the post-processing inspection fails, the work is reprocessed (**DD10**). Once the decision node is added, the notation rises from 23 symbols to 26. The number of accepted total orderings, however, is no longer 168 but the sum of the two branches: branch A gives 168, branch B gives **324**, the total is **492**. Adding one node and two edges nearly tripled the number of accepted executions. The reason is this: the notation writes **under which condition** a branch is chosen as text, but carries no structure that tests that text. To someone looking at the diagram, both branches are always open. A decision looks like something that splits the flow; measured, it turns out to be something that **merges**: it gathers two separate sets of executions under a single notation. ## Summary - The activity notation does not write order, it writes prerequisites; ten tasks and thirteen prerequisites build a partial order with **23 symbols**, and that partial order accepts **168 total orderings** at once. Drawing a single order gives a coverage of 0.006. - Topological sort gives a single output because it uses a criterion for choosing from the queue; the number of valid outputs is 168. Of the forty-five task pairs, 31 are fixed and 14 are free, and because the free pairs are not independent, the number is found by exhaustive count. - The ten tasks without prerequisites could be done in 3,628,800 orders; thirteen prerequisites narrow this by **21,600 times**. Unless the looseness is written, a reader mistakes 168 for 1. - The tasks split into six layers: critical path 6 steps, sequential execution 10 steps. Parallelism and ambiguity are two faces of the same fact; the notation can state parallelism only by leaving order free. - Of the 28 prerequisites that can be added without creating a cycle, one brings 168 down to 16 while another leaves it at 152; the two rules that are genuinely defensible in the shop give 96. The constraint that narrows the most is not the most correct constraint. - A decision node raises 23 symbols to 26 while carrying the accepted total orderings from 168 to **492**: a decision does not split the flow, it merges two sets of executions into a single notation. ## Next Step This lesson counted the executions the notation **over-accepts**: all 168 orders are valid, but the system does only one of them on any given run. The acceptance was excessive, and all of the excess was deliberate — a partial order is written precisely to be loose. The next notation produces the same excess without meaning to, and on top of that does the opposite as well. A state machine writes the states an object can pass through and the transitions between them; in the shop, a work order has four states and six transitions. This machine **rejects two** of the six sequences that genuinely occur and **accepts two** sequences that do not occur in the system. When two transitions are added to rescue the rejected ones, the rejected count drops to zero, but over-approximation rises from 2 to **26**. The lesson writes this as a rule: the price of closing under-approximation is over-approximation.