build system
A tool that works out which parts of a software project must be rebuilt, and in what order, from a graph of dependencies.
In more detail
It performs a topological sort so each target is built after everything it depends on, and reports an error if the dependencies form a cycle. Make, which reads targets and their prerequisites from a Makefile, is the classic example.
Related terms
- topological sort — An ordering of a directed graph's vertices in which every edge points from an earlier vertex to a later one.
- directed acyclic graph — A directed graph with no cycles, so following edges can never bring you back to where you started.
Taught in
- Arrays: Contiguous Memory And Constant-Time Access — Algorithms & Data Structures for Working Engineers
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers
- Backtracking: Search With Pruning — Algorithms & Data Structures for Working Engineers