Course contentsShow
← Computer Science
Lesson 1418 of 2,87232. File SystemsFree lesson

Acyclic Graph Directories

Exploring shared subdirectories and files through links while preventing cycles in the directory structure.

Acyclic Graph Directories

You'll learn how file systems allow sharing of files and subdirectories between multiple directories without creating circular references.

The Sharing Problem

In tree-structured directories, each file or subdirectory has exactly one parent. But what if two users want to share the same file? Do we make a copy? That wastes space and creates synchronization headaches. The solution: allow the directory structure to become a directed acyclic graph (DAG) instead of a strict tree.

How Acyclic Graphs Work

In an acyclic graph directory structure, multiple directories can contain links to the same file or subdirectory. Think of it like having multiple shortcuts to the same document on your desktop and in your downloads folder—both point to one actual file.

For example:

  • /home/alice/project/report.txt
  • /home/bob/shared/report.txt

Both paths could reference the same physical file through links, not copies.

The "Acyclic" Requirement

The critical constraint is no cycles. If directory A contains directory B, and directory B contains directory A, you've created a cycle. This breaks algorithms that traverse directory trees (like search or deletion) because they could loop infinitely.

The file system must prevent cycles, typically by:

  • Allowing links only to files, not subdirectories
  • Or allowing subdirectory links but checking that no cycle is created before adding a link
  • Using reference counts to track how many directories reference each file

Deletion Complexity

When you delete a file that multiple directories reference, the file system must check if other links still exist. Only when the last link is removed should the actual file data be deleted.

Key Takeaway: Acyclic graph directories enable efficient file sharing through links while maintaining the "no cycles" invariant to prevent infinite loops in directory traversal and management operations.