Activity Diagrams

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

"""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.