El programa tsort es una utilidad de línea de comandos en plataformas Unix y similares que realiza una ordenación topológica de su entrada. A partir de 2017 [actualizar], forma parte del estándar POSIX .1. [1]
Según su página de información [2] , este comando fue escrito inicialmente para proporcionar un ordenamiento de los archivos de objetos que permitiera al enlazador procesarlos secuencialmente (cada uno exactamente una vez y en orden). La página del manual de FreeBSD data su aparición en la versión 7 de Unix . [3]
Tenga en cuenta que la siguiente descripción describe el comportamiento de la implementación de tsort en FreeBSD y menciona las características de GNU cuando puedan existir. Otras implementaciones o versiones pueden diferir.
tsort [-dlq] [ARCHIVO]
Las opciones de FreeBSD pueden ser:
-d activa la depuración-l busca y muestra el ciclo más largo.-q No mostrar mensajes informativos sobre los ciclos.
GNU proporciona únicamente las siguientes opciones:
--help muestra el mensaje de ayuda y sale--version muestra información de la versión y sale
No hay opciones prescritas por POSIX.
tsort lee su entrada (del ARCHIVO dado, o la entrada estándar si no se proporciona ningún archivo de entrada o para un ARCHIVO de '-') como pares de cadenas, separadas por espacios en blanco, lo que indica un ordenamiento parcial. La salida es un ordenamiento total que corresponde al ordenamiento parcial dado. [4]
En otras palabras: para un gráfico acíclico dirigido (usado como un gráfico de dependencia ), tsort produce una lista de los vértices de modo que, para todas las aristas 'a->b', 'a' viene antes que 'b' en la lista.
tsort enumera los vértices de un gráfico acíclico dirigido en un orden tal que se respetan todas las relaciones de ordenamiento/dirección:
tsort puede ayudar a reorganizar funciones en un archivo fuente para que se definan la mayor cantidad posible antes de usarlas (interprete lo siguiente como: main()llamadas parse_options(), tail_file()y tail_forever(); tail_file()llamadas pretty_name(), y así sucesivamente. El resultado es que dump_remainder()deben definirse primero, start_lines()segundo, etc.):
El tradicional ld (Unix linker) requiere que sus entradas de biblioteca se ordenen en orden topológico, ya que procesa los archivos en una sola pasada. Esto se aplica tanto a las bibliotecas estáticas ( *.a) como a las bibliotecas dinámicas ( *.so), y en el caso de las bibliotecas estáticas, preferiblemente a los archivos de objetos individuales que contienen. [5]
BSD UNIX utiliza tsort como parte común de las invocaciones de comandos típicas de ar y ranlib (desde /usr/share/mk/bsd.lib.mk):
lib${LIB}.a : ${ OBJS } ${ STATICOBJS } @ ${ ECHO } construyendo la biblioteca estática ${ LIB } @ ${ AR } cq ${ . TARGET } ` lorder ${ OBJS } ${ STATICOBJS } | tsort -q ` ${ ARADD } ${ RANLIB } ${ . TARGET } Aquí lorderse utiliza ("orden de biblioteca") para generar la lista de dependencia entre archivos inspeccionando la tabla de símbolos.
Tenga en cuenta la intercambiabilidad de los separadores de espacios en blanco, por lo que las siguientes entradas son equivalentes:
Los pares de elementos idénticos indican la presencia de un vértice, pero no orden (por lo que lo siguiente representa un vértice sin aristas):
Automóvil club británico
Estrictamente hablando, no existe un ordenamiento topológico de un gráfico que contiene uno o más ciclos . Sin embargo, tsort imprime una advertencia y GNU tsort imprime los ciclos detectados en el error estándar (líneas que comienzan con 'tsort:'):
$ tsort <<EOF > ab > bc > ca > EOF UX: tsort: INFORM: ciclo en datos tsort: a tsort: b tsort: c a b cPágina del manual de tsort en
.svg/1280px-Free_and_open-source_software_logo_(2009).svg.png){kind=logo}