This page gives an overview over the dependency graphs used by botch. Consider the following dependency situation:

$ cat Sources
Package: a
Version: 1.0
Architecture: any
Build-Depends: binaryB

Package: b
Version: 1.0
Architecture: any
Build-Depends: binaryA
$ cat Packages
Package: binaryA
Version: 1.0
Architecture: amd64
Source: a
Depends: binaryB

Package: binaryB
Version: 1.0
Architecture: amd64
Source: b

Three different types of package interdependencies are expressed:

• build dependencies (Build-Depends field in Sources)
• binary or runtime dependencies (Depends field in Packages)
• builds-from relationship (Source field in Packages or implicitly the same name as the binary package)

We can visualize this situation as the following graph:

Source package vertices are displayed as rectangles while binary package vertices are displayed as ellipses. Build dependencies are represented by dashed edges, binary dependencies by dotted edges and builds-from relationships by solid edges.

Binary dependencies (the dependency of binaryA on binaryB) cannot conditionally be broken so we merge the two vertices for binaryA and binaryB into a single vertex to simplify the graph.

The new vertex now contains all vertices that represent an installation set of binaryA. This is why this type of vertex is called installation set vertex. The vertex of binaryB was also turned into an installation set vertex but since binaryB does not depend on any other binary packages it is the only binary package in its installation set.

The next figure shows the final graph which we call "build graph". The information about interdependencies between binary packages within an installation set is removed.

The build graph allows to easily spot the two dependency cycles in this setup. A build graph only has two edge types (build dependency and builds-from dependency) and two vertex types (source vertex and installation set vertex). Since an installation set vertex can represent more than one binary package, it can have more than one outgoing builds-from edge.

A so called source graph reduces the graph even further by removing the installation set vertices but keeping the interdependencies between source vertices intact. Here is the source graph of the build graph above:

A source graph is required to reason about strong dependencies between source packages.