Given a mapping between items, and items they depend on, a [[wp:Topological sorting|topological sort]] orders items so that no item precedes an item it depends upon.

The compiling of a library in the [[wp:VHDL|VHDL]] language has the constraint that a library must be compiled after any library it depends on.

A tool exists that extracts library dependencies.


;Task:
Write a function that will return a valid compile order of VHDL libraries from their dependencies.

* Assume library names are single words.
* Items mentioned as only dependents, (sic), have no dependents of their own, but their order of compiling must be given.
* Any self dependencies should be ignored.
* Any un-orderable dependencies should be flagged.

<br>
Use the following data as an example:
<pre>
LIBRARY          LIBRARY DEPENDENCIES
=======          ====================
des_system_lib   std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01             ieee dw01 dware gtech
dw02             ieee dw02 dware
dw03             std synopsys dware dw03 dw02 dw01 ieee gtech
dw04             dw04 ieee dw01 dware gtech
dw05             dw05 ieee dware
dw06             dw06 ieee dware
dw07             ieee dware
dware            ieee dware
gtech            ieee gtech
ramlib           std ieee
std_cell_lib     ieee std_cell_lib
synopsys
</pre>

<br>
<small>Note: the above data would be un-orderable if, for example, <code>dw04</code> is added to the list of dependencies of <code>dw01</code>.</small>


;C.f.:
:* &nbsp; [[Topological sort/Extracted top item]].

<br>
There are two popular algorithms for topological sorting:
:* &nbsp; Kahn's 1962 topological sort <ref> [[wp: topological sorting]] </ref>
:* &nbsp; depth-first search <ref> [[wp: topological sorting]] </ref> <ref> Jason Sachs
[http://www.embeddedrelated.com/showarticle/799.php "Ten little algorithms, part 4: topological sort"] </ref>
<br><br>