Topological sort/Extracted top item: Difference between revisions
Content added Content deleted
m (→{{header|Java}}: added comment, changed adjacency to boolean) |
(Added Kotlin) |
||
Line 450: | Line 450: | ||
Compile order for top2 [extra1, des1c1, des1a2, des1a1, des1c, des1b, des1a, ipcommon, ip2c, ip2b, ip2a, des1, ip3, ip2, top2] |
Compile order for top2 [extra1, des1c1, des1a2, des1a1, des1c, des1b, des1a, ipcommon, ip2c, ip2b, ip2a, des1, ip3, ip2, top2] |
||
Compile order for ip1 [extra1, ipcommon, ip1a, ip1]</pre> |
Compile order for ip1 [extra1, ipcommon, ip1a, ip1]</pre> |
||
=={{header|Kotlin}}== |
|||
{{trans|Java}} |
|||
<lang scala>// version 1.1.51 |
|||
import java.util.LinkedList |
|||
val s = "top1, top2, ip1, ip2, ip3, ip1a, ip2a, ip2b, ip2c, ipcommon, des1, " + |
|||
"des1a, des1b, des1c, des1a1, des1a2, des1c1, extra1" |
|||
val deps = mutableListOf( |
|||
0 to 10, 0 to 2, 0 to 3, |
|||
1 to 10, 1 to 3, 1 to 4, |
|||
2 to 17, 2 to 5, 2 to 9, |
|||
3 to 6, 3 to 7, 3 to 8, 3 to 9, |
|||
10 to 11, 10 to 12, 10 to 13, |
|||
11 to 14, 11 to 15, |
|||
13 to 16, 13 to 17 |
|||
) |
|||
val files = listOf("top1", "top2", "ip1") |
|||
class Graph(s: String, edges: List<Pair<Int, Int>>) { |
|||
val vertices = s.split(", ") |
|||
val numVertices = vertices.size |
|||
val adjacency = List(numVertices) { BooleanArray(numVertices) } |
|||
init { |
|||
for (edge in edges) adjacency[edge.first][edge.second] = true |
|||
} |
|||
fun topLevels(): List<String> { |
|||
val result = mutableListOf<String>() |
|||
// look for empty columns |
|||
outer@ for (c in 0 until numVertices) { |
|||
for (r in 0 until numVertices) { |
|||
if (adjacency[r][c]) continue@outer |
|||
} |
|||
result.add(vertices[c]) |
|||
} |
|||
return result |
|||
} |
|||
fun compileOrder(item: String): List<String> { |
|||
val result = LinkedList<String>() |
|||
val queue = LinkedList<Int>() |
|||
queue.add(vertices.indexOf(item)) |
|||
while (!queue.isEmpty()) { |
|||
val r = queue.poll() |
|||
for (c in 0 until numVertices) { |
|||
if (adjacency[r][c] && !queue.contains(c)) queue.add(c) |
|||
} |
|||
result.addFirst(vertices[r]) |
|||
} |
|||
return result.distinct().toList() |
|||
} |
|||
} |
|||
fun main(args: Array<String>) { |
|||
val g = Graph(s, deps) |
|||
println("Top levels: ${g.topLevels()}") |
|||
for (f in files) println("\nCompile order for $f: ${g.compileOrder(f)}") |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Top levels: [top1, top2] |
|||
Compile order for top1: [extra1, des1c1, des1a2, des1a1, des1c, des1b, des1a, ip2c, ip2b, ip2a, ipcommon, ip1a, des1, ip2, ip1, top1] |
|||
Compile order for top2: [extra1, des1c1, des1a2, des1a1, des1c, des1b, des1a, ipcommon, ip2c, ip2b, ip2a, des1, ip3, ip2, top2] |
|||
Compile order for ip1: [extra1, ipcommon, ip1a, ip1] |
|||
</pre> |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |