We closed the previous module with a confession: all our trees hid a silent assumption — that every node has exactly one parent. The moment a TaskFlow task depends on several others at once — "deploy API" needs both "migrate DB" and "configure server" to finish — the hierarchy falls short. And if someone accidentally creates a circular dependency on top of that, the tree simply cannot represent it. The structure that can handle all of this is the graph: the most general one in the course, the one that subsumes lists and trees as special cases, and the one that models social networks, maps, the web, and a project's dependencies. In this lesson we'll learn its vocabulary; still no representation code (that comes in the next lesson) and no algorithms (they're waiting in 07-03 with the visited promised back in module 5).

1. From tree to graph: why we need something more general
2. Formal definition: vertices and edges
3. Essential terminology (with diagrams)
4. The tree as a special case of graph
5. Modeling TaskFlow's dependencies as a directed graph
6. Graphs in the real world

Let's recall the two concrete limitations we ran into at the end of module 6:

• Multiple parents: in a tree, "deploy API" could only hang from "migrate DB" or from "configure server", never from both. But in a real project it depends on both.
• Possible cycles: nothing stops a TaskFlow user from declaring that A depends on B, B on C, and C on A. A tree can't even express that; a graph can, and it will also give us algorithms to detect it and warn the user.

A graph removes both restrictions: any node can connect to any other, in any direction, even forming cycles. In exchange, we lose the tree's comfortable guarantees (a single root, no cycles, a single path between any two nodes), which is why graph algorithms will have to be more careful. That's the price of generality.

A graph is a pair G = (V, E) where:

• V is a set of vertices (also called nodes): the entities. In TaskFlow, the tasks.
• E is a set of edges: the relationships between pairs of vertices. In TaskFlow, the dependencies.

For example, with three tasks:

Notice that here the edges are ordered pairs: (migrate_db, deploy_api) is not the same as (deploy_api, migrate_db). That takes us straight into the terminology.

• In a directed graph (or digraph), every edge has a direction: it goes from a source to a target and is drawn with an arrow. "Migrating the DB unblocks deploying the API" is not symmetric.
• In an undirected graph, the edge is mutual: if A is connected to B, B is connected to A. "Anna and Bruno are friends".

A graph is weighted when every edge carries a number (its weight): cost, distance, hours... In TaskFlow, an edge's weight will be the hours it takes to complete the transition between two tasks. If all we care about is whether there's a connection, the graph is unweighted.

The degree measures how many edges touch a vertex. In directed graphs it splits in two:

In the "deploy API" diagram: in-degree 2 (it waits for two tasks), out-degree whatever it unblocks afterwards.

• A path is a sequence of vertices connected by consecutive edges: design_schema → migrate_db → deploy_api. Its length is its number of edges (2 in the example).
• A cycle is a path that starts and ends at the same vertex without repeating edges. In a dependency graph, a cycle is a fatal error: nobody can start.

This cycle (design_ui → implement_ui → review_docs → design_ui) means none of the three tasks can ever get off the ground. Does "cycle detection" ring a bell? In module 2 we detected cycles in linked lists with Floyd's algorithm; in graphs we'll need a different technique (lesson 07-03), but the problem is a sibling.

An undirected graph is connected if you can reach any vertex from any other. If not, it splits into connected components: "islands" of vertices connected among themselves but isolated from the rest. In TaskFlow, two components are two projects that share no dependency at all.

• A dense graph has many edges: close to the maximum possible, which with n directed vertices is n · (n - 1).
• A sparse graph has few: on the order of n.

Real dependency graphs are almost always sparse (each task depends on 1–3 tasks, not on all 200 in the project). This detail, which looks minor, will decide in the next lesson how the graph should be represented in memory.

A DAG (Directed Acyclic Graph) is a directed graph with no cycles. It's the star of this module: a well-formed TaskFlow project is exactly a DAG. It allows multiple parents (unlike the tree) but forbids vicious circles (unlike the general graph).

Observe: "deploy_api" and "integration_tests" have multiple parents (impossible in a tree) and yet there is no cycle anywhere. This DAG will be the recurring example of the whole module.

Now we can place module 6 on the map: a tree is a connected, acyclic graph (and in its rooted version, directed with in-degree 1 at every vertex except the root, which has 0). The course's entire hierarchy of structures fits:

Each row relaxes one restriction from the previous one. The algorithms we'll see work on general graphs and therefore also on every special case: BFS on a tree is exactly the level-order traversal from module 6.

One detail remains to pin down, and we'll carry it through the whole module: which way the arrows point. There are two possible conventions and both are legitimate; the important thing is to pick one and never mix them.

• Option A: A → B means "A depends on B".
• Option B: A → B means "B depends on A" (A must finish first; the arrow points at what A unblocks).

In this course we adopt option B: the edge migrate_db → deploy_api reads "finishing migrate_db brings deploy_api closer to being unblocked". It's the natural convention for the algorithms ahead: following the arrows means moving forward in project time, and the "valid execution order" will come from walking them forward.

With this convention, and remembering that every TaskFlow task is still the usual dict (id, title, priority, status, assigned_to, tags, hours), the complete mental model is:

• Vertex: a task's id (the full dict lives elsewhere, in an id → task dictionary, as in module 5's index).
• Edge A → B: B depends on A.
• In-degree of B: number of B's pending dependencies. When it reaches 0... B is runnable. Hold on to this idea: it's the seed of topological order (07-03).
• Edge weight (when there is one): hours or cost of the transition (07-04).

The same vocabulary models very different systems; only what counts as a vertex and what counts as an edge changes:

Notice that pip install solves exactly the same problem as TaskFlow: given a dependency DAG, find a valid installation order and complain if there are cycles. When we implement topological order in 07-03, you'll have understood how a package manager works on the inside.

• Mixing the two arrow conventions. If one day you draw A → B as "A depends on B" and another day as "B depends on A", your algorithms will produce inverted results. Write the convention down (ours: the arrow points at what gets unblocked) and stick to it.
• Confusing a path with an edge. That a path exists from A to C does not mean the direct edge A → C exists. They are different questions and, as we'll see, with very different computational costs.
• Assuming every directed graph is a DAG. The absence of cycles must be checked, not assumed; real data (entered by users) contains accidental cycles more often than you'd imagine.
• Forgetting isolated vertices. A task with no dependencies at all (incoming or outgoing) is still a vertex of the graph. The sets V and E are independent: there can be vertices with no edges.
• Tip: before writing any code, draw the graph (mermaid or paper). With graphs, a good drawing prevents half of all modeling mistakes.

For each system, say whether its natural graph is directed or undirected, weighted or not, and whether you expect it to be a DAG: (a) the "derived from" history between versions of a document; (b) commercial flights between airports with their duration; (c) power sockets connected by cables in an office.

Using the course convention (A → B = B depends on A) and this lesson's TaskFlow DAG, answer: (a) what are the in-degree and out-degree of integration_tests? (b) which tasks can start on day one (without waiting for anyone)? (c) write a path from design_schema to launch and give its length.

Starting from the same DAG, add a single edge that creates a cycle, and explain — using the "depends on" reading — why the resulting project is impossible to execute.

Solution 1:

• (a) Directed (the "derived from" relation has a direction), unweighted, and it is a DAG: a version can't derive from a future version of itself.
• (b) Directed (outbound and return may differ or not exist), weighted (duration), and it is not a DAG: cycles (Madrid → Paris → Madrid) not only exist but are desirable.
• (c) Undirected (a cable connects both ways), weighted if we care about cable length; "DAG" doesn't apply to undirected graphs.

Solution 2:

• (a) In-degree 2 (deploy_api and implement_ui point at it), out-degree 1 (launch).
• (b) The ones with in-degree 0: design_schema, configure_server, and design_ui.
• (c) design_schema → migrate_db → deploy_api → integration_tests → launch, length 4 (four edges, five vertices).

Solution 3: For example launch → design_schema. Reading: "design_schema depends on launch". But launch depends (transitively) on design_schema, so each waits for the other through the chain: no task in the cycle ever reaches in-degree 0 and the entire project is blocked. Any "backward" edge over an existing path counts as a valid answer.

We now speak the language of graphs: vertices and edges; directed, weighted, degrees, paths, cycles, components, dense versus sparse, and the DAG as the faithful portrait of a well-formed project. We've placed lists and trees as graphs with restrictions, and we've fixed the convention that will govern the whole module: the arrow points at the task that gets unblocked. What we don't know yet is how to store a graph in memory: one big "who connects to whom" table, or a dictionary of neighbors? The answer — adjacency matrix versus adjacency list, with their costs and a reusable Graph class — is exactly the topic of the next lesson.