#HowToThing #018 — Topological sorting, creating and visualizing a task dependency graph

018.ts

import { identity } from "@thi.ng/api";
import { topoSort } from "@thi.ng/arrays";
import { defDGraph } from "@thi.ng/dgraph";
import { toDot } from "@thi.ng/dgraph-dot";
import { comp, filter, map, mapcat, pairs, run, trace } from "@thi.ng/transducers";

interface Task {
    title: string;
    done?: boolean;
    // IDs of other tasks this task depends on (aka is blocked by)
    deps?: string[];
}

// collection of tasks
const tasks: Record<string, Task> = {
    launch: {
        title: "Launch newsletter",
        deps: ["howto20", "setup", "interview"],
    },
    interview: { title: "Do interview", deps: ["deck", "offline"] },
    howto20: { title: "Write #HowToThing 20", deps: ["howto19"] },
    howto18: { title: "Write #HowToThing 18", done: true },
    deck: { title: "Create presentation" },
    offline: { title: "Download offline assets", done: true },
    howto19: { title: "Write #HowToThing 19", deps: ["howto18", "interview"] },
    setup: { title: "Setup & configure newsletter" },
};

// compose a tranducer function consisting of 3 processing steps, which will
// later be applied by `showTasks()` to each individual task ID.
// even though you might know `map()` / `filter()` from vanilla JS, this approach
// here applies to SINGLE tasks (not arrays!) and also doesn't create any
// intermediate arrays. just another illustration of the flexibility of transducers,
// functional composition/synthesis from small pre-existing pieces of functionality
const xformTask = comp(
    // ignore completed tasks
    filter((id: string) => !tasks[id].done),
    // look up task title
    map((id) => tasks[id].title),
    // side effect: console.log with optional prefix
    trace("task:")
);

// helper function to display actual tasks from only a given collection of IDs
const showTasks = (ids: Iterable<string>) => {
    // apply the above transducer to all task IDs
    run(xformTask, ids);
    console.log("---");
};

// sort tasks in dependency order
// see: https://docs.thi.ng/umbrella/arrays/functions/topoSort.html
const order = topoSort(tasks, (task) => task.deps || []);

showTasks(order);
// task: Create presentation
// task: Do interview
// task: Write #HowToThing 19
// task: Write #HowToThing 20
// task: Setup & configure newsletter
// task: Launch newsletter

// for more advanced usage, let's build an actual dependency graph:

// helper type (for illustration)
type Edge = [string, string | null];

// the graph factory function accepts an iterable of graph edges, aka
// tuples/pairs of task IDs. e.g. the edge ["launch", "interview"] means the
// "launch" tasks depends on "interview". to also register nodes/tasks without
// any dependencies, we define pairs like so: [id, null]
const graph = defDGraph<string>(
    // `mapcat()` is similar to `Array.flatMap()`, but more flexible & lazy...
    // (e.g. it works with any JS iterable, not just arrays)
    mapcat(
        // function receives a tuple of [id, task]
        ([id, { deps }]) =>
            deps
                ? // could use `deps.map(...)` here, but using map() as
                  // iterator avoids allocating intermediate arrays
                  map<string, Edge>((d) => [id, d], deps)
                : // ...for tasks without any dependencies
                  <Edge[]>[[id, null]],
        // iterable of [key,value] pairs of an object
        // (same, but older than the now native `Object.entries()`)
        pairs(tasks)
    )
);

// again show tasks in topological sort order:
// (compared to above, there's slightly different LOCAL order when there're no
// deps, but GLOBAL dependency order is of course the same...)
showTasks(graph.sort());
// task: Create presentation
// task: Do interview
// task: Write #HowToThing 19
// task: Setup & configure newsletter
// task: Write #HowToThing 20
// task: Launch newsletter

// now ask some questions:

// what still needs to be done before the interview?
showTasks(graph.transitiveDependencies("interview"));
// task: Create presentation

// what else depends on howtothing #18 being done?
showTasks(graph.transitiveDependents("howto18"));
// task: Write #HowToThing 20
// task: Launch newsletter
// task: Write #HowToThing 19

// what could be done next after howtothing #18?
showTasks(graph.immediateDependents("howto18"));
// task: Write #HowToThing 19

// what does the launch depend on directly?
showTasks(graph.immediateDependencies("launch"));
// task: Write #HowToThing 20
// task: Setup & configure newsletter
// task: Do interview

// finally, output Graphviz diagram fileformat (DOT) to visualize the graph
// see: https://graphviz.org
console.log(
    toDot(graph, {
        // use task IDs as is (aka identity function)
        id: identity,
        // function to customize attribs for each single task/node
        spec: (id) => {
            const { done, title } = tasks[id];
            const node = { label: title };
            // highlight completed tasks
            return done
                ? { ...node, fillcolor: "#99ff99", fontcolor: "black" }
                : node;
        },
        // global graph attributes
        attribs: {
            // set rank direction such that dependencies are at the top and
            // dependents at the bottom
            rankdir: "BT",
            // base styling attribs for all nodes
            node: { fontname: "Helvetica", shape: "box", style: "filled" },
        },
    })
);