Topological sort: Difference between revisions

{{trans|Python}}

‘des_system_lib’ = Set(‘std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee’.split(‘ ’)),

‘dw01’ = Set(‘ieee dw01 dware gtech’.split(‘ ’)),

R r

{{out}}

The specification:

package Digraphs is

type Graph_Type is new Conn_Vec.Vector with null record;

The implementation:

function Node_Count(Graph: Graph_Type) return Node_Idx_With_Null is

end Top_Sort;

'''Set_of_Names: Translating strings into numbers and vice versa'''

The specification:

generic

type Set is new Vecs.Vector with null record;

The implementation

use type Ada.Containers.Count_Type, Vecs.Cursor;

end Name;

'''Toposort: Putting things together for the main program'''

procedure Toposort is

TIO.Put_Line("There is no topological sorting -- the Graph is cyclic!");

end;

{{out}}

=={{header|Bracmat}}==

(dw01.ieee dw01 dware gtech)

(dw02.ieee dw02 dware)

& out$("

compile order:" !indeps !res "\ncycles:" !cycles)

{{out}}

<pre>compile order:

=={{header|C}}==

Parses a multiline string and show the compile order. Note that four lines were added to the example input to form two separate cycles. Code is a little ugly.

#include <stdlib.h>

#include <string.h>

return 0;

[unorderable] cycle_21 cycle_22

[unorderable] cycle_11 cycle_12

2: std_cell_lib ramlib dware gtech

3: dw02 dw01 dw05 dw06 dw07

=={{header|C sharp}}==

namespace Algorithms

{

}

D - depends on none

G - depends on none

C - depends on D and E

A - depends on B and C

=={{header|C++}}==

===C++11===

#include <set>

display_results(string(iterator(file), iterator()));

}

===C++17===

#include <unordered_set>

#include <vector>

return 0;

H - depends on none

G - depends on none

G - destroyed

H - destroyed

exiting...

A - destroyed

G - destroyed

H - destroyed

=={{header|Clojure}}==

=====Implementation=====

(use 'clojure.contrib.seq-utils)

[items]

(topo-sort-deps (deps items)))

Examples of sortable and non-sortable data:

'(:des_system_lib (:std :synopsys :std_cell_lib :des_system_lib :dw02 :dw01 :ramlib :ieee)

:dw01 (:ieee :dw01 :dware :gtech)

(def bad-sample

====={{out}}=====

1:1 user=> #<Namespace topo>

1:2 topo=> (topo-sort good-sample)

(:std :synopsys :ieee :gtech :ramlib :dware :std_cell_lib :dw07 :dw06 :dw05 :dw01 :dw02 :des_system_lib :dw03 :dw04)

1:3 topo=> (topo-sort bad-sample)

=={{header|CoffeeScript}}==

toposort = (targets) ->

# targets is hash of sets, where keys are parent nodes and

console.log toposort targets

=={{header|Common Lisp}}==

"Graph is an association list whose keys are objects and whose

values are lists of objects on which the corresponding key depends.

all-sorted-p

(unless all-sorted-p

Provided example in which all items can be sorted:

'((des-system-lib std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee)

(dw01 ieee dw01 dware gtech)

(IEEE DWARE DW02 DW05 DW06 DW07 GTECH DW01 DW04 STD-CELL-LIB SYNOPSYS STD DW03 RAMLIB DES-SYSTEM-LIB)

T

Provided example with <code>dw04</code> added to the dependencies of <code>dw01</code>. Some vertices are ordered, but the second return is <code>nil</code>, indicating that not all vertices could be sorted. The third return value is the hash table containing entries for the four vertices that couldn't be sorted. (The variable <code>[http://www.lispworks.com/documentation/HyperSpec/Body/v_sl_sls.htm /]</code> stores the list of values produced by the last form, and <code>[http://www.lispworks.com/documentation/HyperSpec/Body/f_descri.htm describe]</code> prints information about an object.)

'((des-system-lib std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee)

(dw01 ieee dw01 dw04 dware gtech)

DW04 (1 DW01)

DW03 (1)

=={{header|Crystal}}==

if permanent.includes?(n)

return

puts ""

puts dfs_topo_sort(build_graph(data + circular_deps)).join(" -> ")

{{out}}

=={{header|D}}==

{{trans|Python}}

final class ArgumentException : Exception {

foreach (const subOrder; depw.topoSort) // Should throw.

subOrder.writeln;

{{out}}

<pre>#1 : ["ieee", "std", "synopsys"]

=={{header|E}}==

def topoSort(data :Map[any, Set[any]]) {

return result

def dataText := "\

def data := accum [].asMap() for rx`(@item.{17})(@deps.*)` in dataText.split("\n") { _.with(item.trim(), deps.split(" ").asSet()) }

{{out}}

''' Data

(define dependencies

'((des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee)

(define (add-dependencies g dep-list)

(for* ((dep dep-list) (b (rest dep))) (a->b g b (first dep))))

'''Implementation

Remove all vertices with in-degree = 0, until to one left. (in-degree = number of arrows to a vertex)

;; topological sort

;;

(error " ♻️ t-sort:cyclic" (map vertex-label (graph-cycle g))))))

{{Out}}

(define g (make-graph "VHDL"))

(add-dependencies g dependencies)

t-sort (std synopsys ieee dware dw02 dw05 dw06 dw07 gtech ramlib std_cell_lib)

⛔️ error: ♻️ t-sort:cyclic (dw04 dw01)

=={{header|Elixir}}==

{{trans|Erlang}}

def sort(library) do

g = :digraph.new

IO.puts ""

bad_libraries = Keyword.update!(libraries, :dw01, &[:dw04 | &1])

{{out}}

=={{header|Erlang}}==

-module(topological_sort).

-compile(export_all).

digraph:add_vertex(G,D), % noop if dependency already added

digraph:add_edge(G,D,L). % Dependencies represented as an edge D -> L

{{out}}

62> topological_sort:main().

synopsys -> std -> ieee -> dware -> dw02 -> dw05 -> ramlib -> std_cell_lib -> dw06 -> dw07 -> gtech -> dw01 -> des_system_lib -> dw03 -> dw04

dw04 -> dw01 -> dw04

dw01 -> dw04 -> dw01

Erlang has a built in digraph library and datastructure. ''digraph_utils'' contains the ''top_sort'' function which provides a topological sort of the vertices or returns false if it's not possible (due to circular references).

{{works with|Gforth}}

: node. ( body -- )

deps dw01 ieee dw01 dware gtech dw04

{{out}}

This implementation is not optimal: for each ''level'' of dependency (for example A -> B -> C counts as three levels), there is a loop through all dependencies in IDEP.

It would be possible to optimize a bit, without changing the main idea, by first sorting IDEP according to first column, and using more temporary space, keeping track of where is located data in IDEP for each library (all dependencies of a same library being grouped).

IMPLICIT NONE

INTEGER NL,ND,NO,IDEP(ND,2),IORD(NL),IPOS(NL),I,J,K,IL,IR,IPL,IPR

IF(K.GT.J) GO TO 20

NO=J-1

An example. Dependencies are encoded to make program shorter (in array ICODE).

IMPLICIT NONE

INTEGER NL,ND,NC,NO,IDEP,IORD,IPOS,ICODE,I,J,IL,IR

DO 50 I=NO+1,NL

50 PRINT*,LABEL(IORD(I))

{{out}}

===Modern Fortran===

A modern Fortran (95-2008) version of the TSORT subroutine is shown here (note that the IPOS array is not an input).

implicit none

end subroutine tsort

=={{header|FunL}}==

val L = seq()

val S = seq()

case topsort( graph ) of

None -> println( 'un-orderable' )

{{out}}

=={{header|Go}}==

===Kahn===

import (

}

return L, nil

{{out}}

<pre>

Topological sort only, this function can replace topSortKahn in above program. The

in-degree list is not needed.

// library dependencies. Also adapted from Wikipedia pseudo code.

func topSortDFS(g graph) (order, cyclic []string) {

}

return L, nil

{{out}}

(when used in program of Kahn example.)

=={{header|Haskell}}==

import Data.Bifunctor (bimap, first)

main :: IO ()

{{out}}

["std","synopsys","ieee","std_cell_lib","dware","dw02","gtech","dw01","ramlib","des_system_lib","dw03","dw04","dw05","dw06","dw07"]

*Main> toposort $ (\(xs,(k,ks):ys) -> xs++ (k,ks++" dw04"):ys) $ splitAt 1 depLibs

=={{header|Huginn}}==

import Text as text;

dfs = DepthFirstSearch();

print( "{}\n".format( dfs.topological_sort( dg ) ) );

==Icon and Unicon==

elements have been built.

global ex_name, in_name

g.arcs ? while arc := move(2) do if arc[1] == f then t ++:= arc[2]

return t

{{out}}

in parallel once the elements in the preceding lines have been built.

procedure main()

while (af := @cp, at := @cp) do if af == f then insert(t, at)

return t

=={{header|J}}==

parsed=. <@;:;._2 y

names=. {.&>parsed

assert.-.1 e. (<0 1)|:depends

(-.&names ~.;parsed),names /: +/"1 depends

With the sample data set:

We would get:

std

ieee

dw04

dw03

If we tried to also make dw01 depend on dw04, the sort would fail because of the circular dependency:

|assertion failure: dependencySort

Here is an alternate implementation which uses a slightly different representation for the dependencies (instead of a boolean connection matrix to represent connections, we use a list of lists of indices to represent connections):

parsed=. <@;:;._2 y

names=. {.&>parsed

assert.-.1 e. (i.@# e.S:0"0 ])depends

(-.&names ~.;parsed),names /: #@> depends

It's results are identical to the first implementation, but this might be more efficient in typical cases.

=={{header|Java}}==

{{works with|Java|7}}

public class TopologicalSort {

return false;

}

<pre>[std, ieee, dware, dw02, dw05, dw06, dw07, gtech, dw01, dw04, ramlib, std_cell_lib, synopsys, des_system_lib, dw03]</pre>

====ES6====

`des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee

dw01 ieee dw01 dware gtech

console.log('Solution:', S);

Output:

Solution: [

'ieee',

'dw03',

'des_system_lib' ]

=={{header|jq}}==

To solve and print the solution to the given problem on a 1GHz machine takes about 5ms.

# Input: an object representing a normalized dependency graph

def independent:

normalize | [[], .] | _tsort ;

Data:

"dw01": [ "ieee", "dw01", "dware", "gtech"],

"dw02": [ "ieee", "dw02", "dware"],

"synopsys": []

}

{{Out}}

$ jq -c -f tsort.jq tsort.json

["ieee","std","synopsys","dware","gtech","ramlib","std_cell_lib","dw01","dw02","des_system_lib","dw03","dw04","dw05","dw06","dw07"]

=={{header|Julia}}==

{{trans|Python}}

data = copy(data)

for (k, v) in data

)

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

val s = "std, ieee, des_system_lib, dw01, dw02, dw03, dw04, dw05, " +

println("Following the addition of dw04 to the dependencies of dw01:")

println(g2.topoSort())

{{out}}

This version follows python implementation and returns List of Lists which is useful for parallel execution for example

</pre>

val graph = mapOf(

"des_system_lib" to "std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee".split(" ").toSet(),

}

{{out}}

<pre>

=={{header|M2000 Interpreter}}==

\\ empty stack

Flush

}

testthis

{{out}}

<pre>

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Work in Mathematica 8 or higher versions.

Graph[Flatten[# /. {l_, ld_} :>

Map[# -> l &,

{"ramlib", {"std", "ieee"}},

{"std_cell_lib", {"ieee", "std_cell_lib"}},

{{Out}}

<pre>{"ieee", "std_cell_lib", "gtech", "dware", "dw07", "dw06", "dw05", \

=={{header|Mercury}}==

:- module topological_sort.

print(CompileOrder,!IO).

=={{header|Nim}}==

type StringSet = HashSet[string]

for key in data.keys: echo key

except ValueError:

=={{header|Object Pascal}}==

Written for Free Pascal, but will probably work in Delphi if you change the required units.

program topologicalsortrosetta;

InputList.Free;

end.

=={{header|OCaml}}==

("des_system_lib", ["std"; "synopsys"; "std_cell_lib"; "des_system_lib"; "dw02"; "dw01"; "ramlib"; "ieee"]);

("dw01", (*"dw04"::*)["ieee"; "dw01"; "dware"; "gtech"]);

print_string "result: \n ";

print_endline (String.concat ", " res);

If dw04 is added to the set of dependencies of dw01 to make the data un-orderable (uncomment it), an exception is raised:

=={{header|OxygenBasic}}==

'TOPOLOGICAL SORT

next

ret

=={{header|Oz}}==

Using constraint propagation and search:

Deps = unit(

des_system_lib: [std synopsys std_cell_lib des_system_lib

{System.showInfo "\nBONUS - grouped by parallelizable compile jobs:"}

{PrintSolution Sol}

Output:

The algorithm used allows the output to be clustered; libraries on the same line are all independent (given the building of any previous lines of libraries), and so could be built in parallel.

my %deps = @_;

print_topo_sort(%deps);

push @{ $deps{'dw01'} }, 'dw04'; # Add unresolvable dependency

Output:<pre>ieee std synopsys

=={{header|Phix}}==

Implemented as a trivial normal sort.

<span style="color: #004080;">sequence</span> <span style="color: #000000;">names</span>

<span style="color: #008080;">enum</span> <span style="color: #000000;">RANK</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">NAME</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">DEP</span> <span style="color: #000080;font-style:italic;">-- content of names

<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nbad input:\n"</span><span style="color: #0000FF;">)</span>

<span style="color: #000000;">topsort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input</span><span style="color: #0000FF;">&</span><span style="color: #008000;">"\ndw01 dw04"</span><span style="color: #0000FF;">)</span>

{{out}}

Items on the same line can be compiled at the same time, and each line is alphabetic.

=={{header|Picat}}==

Edges = [K=V : [K,V] in Precedences],

% deletes all pairs in L where a key is X

% (this is lessf on a multi-map in GNU SETL)

The approach was inspired by a SETL snippet:

===Test without cycles===

Identify and remove the cycles.

deps(1,Deps),

Prec=[],

std_cell_lib=[ieee,std_cell_lib],

synopsys=[]

{{out}}

===Test with cycles===

deps(with_cycle,Deps),

Prec=[],

cycle_3=[dw01,cycle_4,dw02,daw03],

cycle_4=[cycle_3,dw01,dw04]

{{out}}

=={{header|PicoLisp}}==

(setq Lst # Build a flat list

(uniq

(del (link @) 'Lst) # Yes: Store in result

(for This Lst # and remove from 'dep's

Output:

<pre>: (sortDependencies

=={{header|PowerShell}}==

$a=@"

des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee

"{0,-14} $($_."Library Dependencies")" -f $_.Library

}

=={{header|PureBasic}}==

DataSection

;"LIBRARY: [LIBRARY_DEPENDENCY_1 LIBRARY_DEPENDENCY_2 ... LIBRARY_DEPENDENCY_N]

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")

Input()

Sample output for no dependencies:

<pre>Compile order:

===Python 3===

from functools import reduce

except:

assert not data, "A cyclic dependency exists amongst %r" % data

'''Ordered output'''<br>

===Python 3.9 graphlib===

# LIBRARY mapped_to LIBRARY DEPENDENCIES

ts = TopologicalSorter(data)

{{out}}

First make the list

deps <- list(

"des_system_lib" = c("std", "synopsys", "std_cell_lib", "des_system_lib", "dw02", "dw01", "ramlib", "ieee"),

"std_cell_lib" = c("ieee", "std_cell_lib"),

"synopsys" = c())

Topological sort function. It will throw an error if it cannot complete, printing the list of items which cannot be ordered.

If it succeeds, returns the list of items in topological order.

tsort <- function(deps) {

nm <- names(deps)

s

}

On the given example :

tsort(deps)

# [1] "std" "ieee" "dware" "gtech" "ramlib"

# [6] "std_cell_lib" "synopsys" "dw01" "dw02" "dw03"

#[11] "dw04" "dw05" "dw06" "dw07" "des_system_lib"

If dw01 depends on dw04 as well :

Unorderable items :

des_system_lib

dw04

dw03

=={{header|Racket}}==

#lang racket

(topo-sort (clean G))

Output:

'(synopsys ieee dware gtech std_cell_lib std ramlib dw07 dw06 dw05 dw01 dw04 dw02 dw03 des_system_lib)

=={{header|Raku}}==

{{trans|Perl}}

{{Works with|rakudo|2016.01}}

my %ba;

for %deps.kv -> $before, @afters {

print_topo_sort(%deps);

%deps<dw01> = <ieee dw01 dware gtech dw04>; # Add unresolvable dependency

Output:<pre>ieee std synopsys

Some of the FORTRAN 77 statements were converted to &nbsp; '''do''' &nbsp; loops (or &nbsp; '''do''' &nbsp; structures), &nbsp; and

<br>some variables were &nbsp; [https://en.wikipedia.org/wiki/Camel_case <u>''camel capitalized]''</u>.

iDep.= 0; iPos.= 0; iOrd.= 0 /*initialize some stemmed arrays to 0.*/

nL= 15; nd= 44; nc= 69 /* " " "parms" and indices.*/

end /*i*/

end /*until*/

{{out|output}}

<pre>

=={{header|Ruby}}==

Uses the [http://www.ruby-doc.org/stdlib/libdoc/tsort/rdoc/classes/TSort.html TSort] module from the Ruby stdlib.

class Hash

include TSort

ramlib std ieee

std_cell_lib ieee std_cell_lib

{{out}}

<pre>

=={{header|Rust}}==

use std::collections::{HashMap, HashSet};

}

}

Output:

<pre>

=={{header|Scheme}}==

{{trans|Python}}

(import (chezscheme))

(import (srfi srfi-1))

(newline)

(write (topological-sort unsortable))

=={{header|Sidef}}==

{{trans|Perl}}

var ba = Hash.new;

deps.each { |before, afters|

print_topo_sort(deps);

deps{:dw01}.append('dw04'); # Add unresolvable dependency

{{out}}

<pre>

{{trans|Rust}}

("des_system_lib", ["std", "synopsys", "std_cell_lib", "des_system_lib", "dw02", "dw01", "ramlib", "ieee"]),

("dw01", ["ieee", "dw01", "dware", "gtech"]),

}

{{out}}

=={{header|Tailspin}}==

data node <'.+'>, from <node>, to <node>

synopsys

' -> lines -> collectDeps -> topologicalSort -> !OUT::write

{{out}}

=={{header|Tcl}}==

{{works with|Tcl|8.5}}

proc topsort {data} {

# Clean the data

}

}

Demonstration code (which parses it from the format that the puzzle was posed in):

des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee

dw01 ieee dw01 dware gtech

dict set parsedData [lindex $line 0] [lrange $line 1 end]

}

Sample output:

<pre>ieee std synopsys dware gtech ramlib std_cell_lib dw01 dw02 dw05 dw06 dw07 des_system_lib dw03 dw04</pre>

{{works with|Bourne Shell}}

> des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee

> dw01 ieee dw01 dware gtech

dw03

ramlib

If the graph of dependencies contains a cycle, [[BSD]]'s tsort(1) will print messages to standard error, break the cycle (by deleting one of the dependencies), continue the sort, and exit 0. So if dw04 becomes a dependency of dw01, then tsort(1) finds the cycle between dw01 and dw04.

unorderable libraries, if any, on the right. Self-dependences are

ignored and unlisted libraries are presumed independent.

test program:

dependence_table = -[

#show+

With the given table, the output is

<pre>

=={{header|VBScript}}==

=====Implementation=====

class topological

dim dictDependencies

end property

end class

=====Invocation=====

dim toposort

set toposort = new topological

toposort.reset

next

=====Output=====

=={{header|Visual Basic .NET}}==

Adapted from http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html which was itself an adaptation of Java code. I added the Rosetta code specific format of dependencies, as well as checks for references to self.

' http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html

' added/changed:

#End Region

End Class

=====Output=====

<pre>

=={{header|Wren}}==

{{trans|Kotlin}}

construct new(s, edges) {

_vertices = s.split(", ")

var g2 = Graph.new(s, deps)

System.print("Following the addition of dw04 to the dependencies of dw01:")

{{out}}

{{trans|Wikipedia}}

Input data is munged

allDs:=data.pump(List,fcn(rds){ T(Void.Write,Void.Write,rds[1]) }).copy();

roots:=Dictionary(data); // dictionary of root:leaves

if(roots) throw(Exception.ValueError("Cycle: "+roots.keys));

L

"des_system_lib", "std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee",

"dw01", "ieee dw01 dware gtech",

T( r, ds.replace(r,"").strip().split().copy() ) // leaves writable 'cause they will be

});

{{out}}

<pre>