Not sure which lesson to do first? Find your level and get a plan →

Math · Advanced Functions · Grade 9-12

Dependency Graphs

A dependency graph is a directed graph whose nodes are variables and whose arrows mean 'this variable directly influences that one.


Quick Answer

A dependency graph is a directed graph whose nodes are variables and whose arrows mean 'this variable directly influences that one.' Draw one node per quantity and an arrow from each input to every quantity computed directly from it. The picture answers three practical questions: what must be computed first, what changes when one input changes, and whether two quantities affect each other at all. Spreadsheets, build systems, recipes and course prerequisite charts are all dependency graphs.

Why This Matters

Once a system has more than a few formulas, you cannot hold the order of computation or the effect of a change in your head. The graph shows both: change the price and you can follow arrows to every quantity that must be recomputed, and to nothing else. Without it you either recompute everything or use a value before the value it depends on has been updated.

Intuitive Explanation

Picture a lemonade stand. The price affects how many cups sell, and price and cups sold together set the revenue. Cups sold also sets the cost of lemons and cups. Profit is revenue minus cost. Draw the arrows: Price → Cups, Price → Revenue, Cups → Revenue, Cups → Cost, Revenue → Profit, Cost → Profit. Price has no incoming arrows, so it is the free input; Profit has no outgoing arrows, so it is the final output.

Arrows point from what is known to what is computed from it: u→v means v depends on u. Following arrows shows indirect influence. Price has no direct arrow to Profit, but the paths Price → Revenue → Profit and Price → Cups → Cost → Profit show that a price change reaches profit two ways at once. Listing the nodes so that every arrow points forward gives a valid order of computation, the order in which a spreadsheet recalculates. If the arrows form a cycle, such as A → B → A, no variable can go first, and the quantities must be solved together as a system of equations.

A straight chain such as miles → kilometres → fare is a dependency graph too, but a trivial one: one path with no branches, which the composition fare(km(miles)) already says. The graph is worth drawing when variables branch and merge. A flowchart can look similar but means something else: its boxes are actions in time, and its arrows mean "do this next", not "is computed from".

Think of it like this. A recipe's prep plan: the sauce needs chopped onions and stock, the stock needs simmered bones, and the plated dish needs the sauce and the pasta. The arrows tell you what to start first and what a late delivery of onions will hold up. Unlike a kitchen plan, a dependency graph says nothing about how long each step takes.

Core idea. A dependency graph draws each variable as a node with arrows showing which variables directly drive which others.


When to Use

Draw a dependency graph when a problem has several linked quantities defined by formulas and asks what to compute first, what is affected if one value changes, or whether a circular definition is hiding somewhere. Spreadsheets, multi-step word problems and course or project prerequisites are typical. If the quantities form one chain with no branching, a composition of functions is simpler; if the links have no direction, as in a network of friendships, use an undirected graph.

Tip. Ask: Are you mapping which variables directly influence which others with directed arrows?

How to Recognize It

Before drawing a dependency graph, list the quantities in the problem and, for each one, the quantities that appear directly in its formula.

  1. Is each quantity computed from others, with some quantities used by several later ones?

    If yes, the branching makes a dependency graph worth drawing. If each result feeds exactly one next step in a single line, a composition chain says the same thing more simply.

  2. Does the problem ask what must be found first, or in what order to compute?

    If yes, compute any quantity with no unfinished arrows pointing into it, cross it off and repeat; this ordering is called a topological sort. A flowchart, by contrast, shows actions and decisions, not which value needs which.

  3. Does following the arrows ever bring you back to where you started?

    If yes, there is a cycle: A needs B and B needs A, so neither can be computed first, which a spreadsheet reports as a circular reference. Unless the problem is a feedback loop, a cycle means a definition is wrong.

  4. Does the link between two quantities have a direction, one computed from the other?

    If yes, draw an arrow from the input to the quantity computed from it. If the link is two-way, like two people being friends, an undirected graph fits instead.

Dependency Graphs compared with Composition chains, Undirected graph, and Flowchart of steps

All four rows draw dots joined by lines, so a picture of one can pass for another. Ask what a line means: a value computed from another, a two-way connection, the next step in a process, or one stage of a single pipeline.

Dependency Graphs

Meaning
Use this when you need to map which variables directly influence which others and in what order they compute.
Key test
Are you mapping which variables directly influence which others with directed arrows?
Example
A spreadsheet has Profit = Revenue − Cost, Revenue = Price × Units, Cost = Units × 2. Draw the dependencies and find what must be computed first.

Composition chains

Meaning
A single linear pipeline of functions, not a branching graph of variables.
Key test
Use when one output feeds straight into the next with no branching.
Formula
f(g(h(x)))
Example
Strictly h→g→f in a line

Undirected graph

Meaning
Edges show connection without a direction of influence.
Key test
Use when relationships are symmetric, like friendship, not 'depends on.'
Formula
G=(V,E) unordered
Example
Cities connected by two-way roads

Flowchart of steps

Meaning
Shows the order of actions/decisions, not variable dependencies.
Key test
Use to chart a process or algorithm's steps, not data dependencies.
Example
Decision diamonds and process boxes

Formula & Notation

How to read it: G=(V,E) where V is the set of variable nodes and E is the set of directed edges. An edge u→v means 'v depends on u.'

Worked Examples

Example 1 — Order of computation

Easy

A spreadsheet has Profit = Revenue − Cost, Revenue = Price × Units, Cost = Units × 2. Draw the dependencies and find what must be computed first.
Show the steps and the answer
  1. Draw an arrow from each variable to every formula that uses it: Price → Revenue, Units → Revenue, Units → Cost, Revenue → Profit, Cost → Profit.

    u→v means v is computed directly from u.

  2. Find the nodes with no incoming arrows: Price and Units.

    They depend on nothing in the sheet, so they must be known before anything else.

  3. Compute Revenue and Cost next: every arrow into them starts at Price or Units.

    A variable is ready as soon as all of its incoming arrows start at known values.

  4. Compute Profit last, from Revenue and Cost.

    It is the only node with no outgoing arrows, the final output.

  5. Test with numbers: Price 5 and Units 30 give Revenue 5⋅30=150, Cost 30⋅2=60, Profit 150−60=90.

    Following the order, each value is available exactly when it is needed.

Answer: Compute Price, Units → Revenue, Cost → Profit

Takeaway: Start from the nodes with no incoming arrows, and compute a node only when every arrow into it comes from a known value.

Example 2 — A line, not a graph

Standard

Convert miles to km, then km to a fare. Is a dependency graph the right tool?
Show the steps and the answer
  1. Draw the dependencies: miles → km → fare.

    Each quantity depends on exactly one other, so the graph is a single path.

  2. Look for branching: no variable feeds two others, and none receives two arrows.

    Without branches or merges the graph shows nothing a formula cannot.

  3. Write it as one composed function, for example km(m)=1.609m and fare(k)=3+2k, so fare(km(m))=3+3.218m.

    A chain of single dependencies is exactly function composition, evaluated inside out.

Answer: Use composition, not a dependency graph

Takeaway: A straight chain is composition; a dependency graph pays off when variables branch and merge.

Example 3 — Find the mistake: arrows pointing backward

Application

In a spreadsheet, Area = Length × Width and Paint = Area ÷ 10. Jamal draws Area → Length, Area → Width and Paint → Area, and concludes: "Paint has no arrows coming in, so it must be filled in first." Find the mistake and correct it.
Show the steps and the answer
  1. Read each formula: Area is computed from Length and Width; Paint is computed from Area.

    The variable on the left of each formula is the dependent one.

  2. Name the error: Jamal pointed each arrow from a result back to its inputs.

    The convention u→v means v depends on u, so arrows point toward the dependent variable.

  3. Redraw: Length → Area, Width → Area, Area → Paint.

    Now the arrows follow the flow of computation.

  4. Find the true starting points: Length and Width have no incoming arrows.

    They are filled in first; Paint, with no outgoing arrows, comes last.

  5. Test it: Length 6 and Width 5 give Area 30, so Paint =30÷10=3.

    Paint can only be found after Area, which confirms the corrected order.

Answer: The arrows go Length → Area, Width → Area, Area → Paint; fill in Length and Width first, then Area, then Paint.

Takeaway: Point every arrow from an input to the quantity computed from it; the nodes with no incoming arrows are what you need first.

Where You'll See It

  • Spreadsheet recalculation

    When you change one cell, a spreadsheet follows the arrows out of it and recalculates only the cells downstream, in dependency order. A formula that refers back to its own cell, directly or through other cells, creates a cycle, which is why the program warns about a circular reference.

  • Planning a course schedule

    If Calculus needs Precalculus, which needs Algebra 2 and Geometry, the arrows give valid schedules: any order that takes each course after all the courses pointing into it. A cycle, such as A requiring B while B requires A, would make the program impossible to complete.

  • Rebuilding software after an edit

    Build tools record which files each part of a program depends on. After you edit one file, they follow the arrows and rebuild only what lies downstream of it, which can turn a ten-minute full build into a few seconds.

Common Mistakes

  1. The slip: Drawing the arrow toward the variable that's known first

    Instead: u→v means v depends on u; the arrow points to the dependent.

  2. The slip: Allowing a cycle when one isn't intended

    Instead: a pure 'computes from' dependency graph should be acyclic (a DAG).

  3. The slip: Confusing direct with indirect dependence

    Instead: an arrow means a DIRECT influence; indirect ones come from following a path.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. A spreadsheet has C1 = A1 + B1, D1 = 2 × C1 and E1 = D1 − A1. List every arrow in the dependency graph. Which cells have no incoming arrows?

    Hint: Draw an arrow from each cell used in a formula to the cell that formula fills.

  2. In the same spreadsheet, C1 = A1 + B1, D1 = 2 × C1, E1 = D1 − A1. If B1 changes, which cells must be recomputed, and in what order?

    Hint: Follow every path of arrows leaving B1.

  3. Formulas: area = length × width, cost = area × price, tax = 0.08 × cost, total = cost + tax. Give a valid computing order. Which variables depend directly on cost?

    Hint: Start with variables that use no other variable.

  4. Formulas: X = Y + 1, Y = Z × 2, Z = X − 3. Can these be computed in some order, one after another?

    Hint: Draw the arrows and follow them around.

  5. A map shows which cities are linked by two-way roads. Is this a dependency graph or an undirected graph?

    Hint: Does anything in the map get computed from anything else? Do the links have a direction?

  6. For speed = distance ÷ time, a student draws the arrow speed → distance. Find and correct the mistake.

    Hint: Which variable is computed from the others?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Can a dependency graph show which input to measure most carefully?

It shows where to look. A quantity with many paths leading out of it, such as an interest rate used in five later formulas, spreads any error into everything downstream. Follow the arrows forward from each input and count what it reaches; an input that reaches the final answer by many routes deserves the most care. The graph shows that an influence exists, not how strong it is; sensitivity measures the strength.

How is a list of course prerequisites a dependency graph?

Each course is a node, and an arrow from Algebra 1 to Geometry means Geometry depends on Algebra 1. The longest path of arrows sets the minimum number of terms needed to reach a course, however many courses a student takes at once. If Calculus needs Precalculus, which needs Algebra 2, which needs Algebra 1, a student starting with Algebra 1 cannot reach Calculus before the fourth term.

How can a dependency graph show a feedback loop without a circular mistake?

Label each quantity with its time step. A bank balance this year, B1B_1, depends on last year's, B0B_0, and next year's, B2B_2, depends on B1B_1. Drawn this way, the arrows run B0→B1→B2B_0 \to B_1 \to B_2 and never loop back, so the graph has no cycle. Squash all the years into one node called BB and you get an arrow from BB to itself, which is how feedback looks when time is hidden.

Why does a spreadsheet recalculate only some cells when I edit one?

Spreadsheets keep a dependency graph of their cells. When you change one cell, the program follows the arrows forward from it and recalculates only the cells it reaches, each after the cells it uses. In a sheet with 10,000 formulas, an edit might touch only 20 of them. That is much faster than redoing everything, and it is why a circular reference, which has no valid order, is flagged with a warning.

Learning Path

Dependency Graphs

You are here

Next →

Nothing after this yet
You need Functional Dependency: the idea that one variable is determined by others. A dependency graph draws all those dependencies at once, so you can read an order of computation, trace indirect effects along paths and spot cycles. It leads to spreadsheet design, to the chain rule in calculus (which combines rates along the same paths), and in computer science to topological sorting and build tools.

See Also