Re: topological sorting

[Greg Troxel <gdt%lexort.com@localhost>]

tlaronde%polynum.com@localhost writes:

> 1) To display the topological sorted graph of the dependencies for a
> package one wants to install (one can parse a Makefile for buildlink
> inclusions, emitting pairs, recurse and then tsort(1); so the question
> is not about a problem of feasability);

I am not sure about display, but I think pkgin has this information, and
pbulk-scan creates it.

Note that dependencies can mean

  - runtime dependencies (other package must be installed to install this one)

  - build dependencies (other package must be installed on target to build)

  - tool dependencies (other package must be installed on build host to build)

with the 2nd/3rd being newly more likely to be distinguished correctly
with Taylor's recent cross improvemenqts.

> 2) To verify that there is no version problems about dependencies:
> package P is wanted; it depends on packages M and N; M depends on
> runtime package O v1; N depends on runtime package O v2; and it is not
> possible to have simultaneously Ov1 and Ov2; and same question about
> incompatible building dependencies;

Again pkgin/pbulk-scan have/should-have the info.

> 3) To instruct to build and install (alternatively to add binary)
> in reverse topological order (independant from others to be installed
> first).

I don't follow that.  Both "pkgin add" and "make package" do this.

Note that there is no single "topological order".  There is only a set
of installation orders which are topologically correct.