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.