File Dependencies - Topological Sort (BGL Book Chapter 3)

Based on “The Boost Graph Library” by Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine

Overview

A common use of the graph abstraction is to represent dependencies. One common type of dependency that we programmers deal with on a routine basis is that of compilation dependencies between files in programs that we write. Information about these dependencies is used by programs such as make, or by IDEs such as Visual C++, to determine which files must be recompiled to generate a new version of a program (or, in general, of some target) after a change has been made to a source file.

Consider a graph that has a vertex for each source file, object file, and library that is used in a program. An edge in the graph shows that a target depends on another target in some way (such as a dependency due to inclusion of a header file in a source file, or due to an object file being compiled from a source file).

Answers to many of the questions that arise in creating a build system such as make can be formulated in terms of the dependency graph:

If all of the targets need to be made, in what order should that be accomplished?
Are there any cycles in the dependencies? A dependency cycle is an error, and an appropriate message should be emitted.
How many steps are required to make all of the targets? How many steps are required to make all of the targets if independent targets are made simultaneously in parallel?

Algorithm Description

The first question—specifying an order in which to build all of the targets—requires ensuring that before building a given target, all the targets that it depends on are already built. This is the problem of computing a topological ordering.

A topological ordering can be computed using a depth-first search (DFS). A DFS visits all of the vertices in a graph by starting at any vertex and then choosing an edge to follow. At the next vertex another edge is chosen to follow. This process continues until a dead end (a vertex with no out-edges that lead to a vertex not already discovered) is reached. The algorithm then backtracks to the last discovered vertex that is adjacent to a vertex that is not yet discovered.

In the context of topological sorting, we record each vertex as it is finished (when the DFS backtracks from that vertex). The reverse of this finish order is the topological order.

NWGraph Implementation

NWGraph provides modern C++20 implementations of DFS and topological sorting that differ from the BGL approach by using range adaptors instead of visitors.

Listing 1 Complete source code

/**
 * @file ch3_toposort.cpp
 *
 * @brief File Dependencies - Topological Sort (BGL Book Chapter 3)
 *
 * This example demonstrates topological sorting using DFS on a makefile
 * dependency graph.
 *
 * @copyright SPDX-FileCopyrightText: 2022 Battelle Memorial Institute
 * @copyright SPDX-FileCopyrightText: 2022 University of Washington
 *
 * SPDX-License-Identifier: BSD-3-Clause
 *
 * @authors
 *   Andrew Lumsdaine
 *
 */

#include <fstream>
#include <iostream>
#include <string>
#include <vector>

#include "nwgraph/adjacency.hpp"
#include "nwgraph/adaptors/dfs_range.hpp"
#include "nwgraph/edge_list.hpp"
#include "nwgraph/io/mmio.hpp"

using namespace nw::graph;

int main() {
  std::cout << "=== Topological Sort for Makefile Dependencies ===" << std::endl;
  std::cout << "Based on BGL Book Chapter 3" << std::endl << std::endl;

  edge_list<directedness::directed> E = read_mm<directedness::directed>("makefile-dependencies.mmio");
  adjacency<0>                      A(E);

  std::vector<std::string> name;
  std::ifstream            name_in("makefile-target-names.dat");
  while (!name_in.eof()) {
    std::string buffer;
    name_in >> buffer;
    if (!buffer.empty()) {
      name.push_back(buffer);
    }
  }

  std::cout << "DFS traversal order:" << std::endl;
  std::vector<size_t> order;
  for (auto&& j : dfs_range(A, 0)) {
    if (j < name.size()) {
      std::cout << "  " << name[j] << std::endl;
    }
    order.push_back(j);
  }

  return 0;
}

Building and Running the Example

First, configure and build the example:

# From the NWGraph root directory
mkdir -p build && cd build
cmake .. -DNWGRAPH_BUILD_EXAMPLES=ON
make ch3_toposort

Then run the example:

./examples/bgl-book/ch3_toposort

The program reads a makefile dependency graph from a file and outputs the compilation order (files listed in order such that each file appears before any files that depend on it).

Sample Output

Compilation order:
dax.h
yow.h
zow.h
boz.h
zig.cpp
zig.o
zag.cpp
zag.o
libzigzag.a
foo.cpp
foo.o
bar.cpp
bar.o
libfoobar.a
killerapp

Key NWGraph Features Demonstrated

Edge list construction: Building graphs from edge pairs
DFS range adaptor: Using dfs_range to traverse the graph
Topological sorting: Computing a valid build order for dependencies
Modern C++ idioms: Range-based for loops and structured bindings

References

Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 4th Edition (2022), Chapter 20.4: Topological Sort and Chapter 20.3: Depth-First Search
Siek, Lee, and Lumsdaine. The Boost Graph Library (2002), Chapter 3