package Ġio . github . ms eng bus ch . units ystem . util Ċ Ċ import Ġjava . util .* Ċ Ċ // ĠFrom Ġhttps :// gist . github . com / w ade j ason / 3 6 bfe 5 fb 0 f 1 1 9 de 4 0 9 4 9 2 dd 7 b 1 4 d 6 1 2 0 Ċ class ĠGraph Node < T >( val Ġid : ĠT ) Ġ{ ĊĠĠĠ Ġval Ġne ighbours Ġ= Ġmutable ListOf < Graph Node < T >>() Ċ } Ċ Ċ object ĠTop ological Sort Ġ{ ĊĠĠĠ Ġfun Ġ< T > Ġtopo logical Sort ( graph : ĠList < Graph Node < T >> ): ĠList < Graph Node < T >> Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġin degree Ġ= Ġmutable Map Of < Graph Node < T >, ĠInt >() ĊĠĠĠĠĠĠĠ Ġfor ( node Ġin Ġgraph ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġin degree [ node ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfor ( node Ġin Ġgraph ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor ( ne ighbour Ġin Ġnode . ne ighbours ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġin degree [ ne ighbour ] Ġ= Ġin degree [ ne ighbour ] !!. plus ( 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġorder Ġ= Ġmutable ListOf < Graph Node < T >>() ĊĠĠĠĠĠĠĠ Ġval Ġqueue Ġ= ĠLinkedList < Graph Node < T >>() ĊĊĠĠĠĠĠĠĠ Ġfor ( node Ġin Ġgraph ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif ( in degree [ node ] Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . offer ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġorder . add ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġwhile (! queue . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġqueue . poll () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor ( ne ighbour Ġin Ġnode . ne ighbours ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġin degree [ ne ighbour ] Ġ= Ġin degree [ ne ighbour ] !!. minus ( 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif ( in degree [ ne ighbour ] Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . offer ( ne ighbour ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġorder . add ( ne ighbour ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif ( order . size Ġ!= Ġgraph . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠIllegalArgumentException (" Failed Ġto Ġcreate Ġdependency Ġgraph . ĠThere Ġmust Ġbe Ġa Ġcycle ") ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġorder ĊĠĠĠ Ġ} Ċ }