Graphs
18 problems from Rosalind — Algorithmic Heights. Press Run on any block to execute it in your browser.
DEG — Degree Array
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: DEG — Degree Array
# https://rosalind.info/problems/deg/
#
# Given: A simple graph with n vertices in the edge list format.
# Return: An array D[1..n] where D[i] is the degree of vertex i.
let n = 6
let edge_list = [[1, 2], [2, 3], [6, 3], [5, 6], [2, 5], [2, 4], [4, 1]]
# Each edge contributes one to both of its endpoints, so a single pass over the
# edge list is enough — the adjacency structure never has to be built.
let vertex_degree = []
for _ in range(0, n) {
vertex_degree = push(vertex_degree, 0)
}
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
vertex_degree[u] = vertex_degree[u] + 1
vertex_degree[v] = vertex_degree[v] + 1
}
let result = vertex_degree |> map(|d| str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 2 4 2 2 2 2")
fn test_deg_degree_array() {
assert result == "2 4 2 2 2 2", "DEG: got " + result
}DDEG — Double-Degree Array
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: DDEG — Double-Degree Array
# https://rosalind.info/problems/ddeg/
#
# Given: A simple graph with n vertices in the edge list format.
# Return: An array D[1..n] where D[i] is the sum of the degrees of i's neighbours.
let n = 5
let edge_list = [[1, 2], [2, 3], [4, 3], [2, 4]]
# Two passes rather than one: the neighbour sum for a vertex needs every degree
# to be final first, so the degrees are counted before anything is summed.
let vertex_degree = []
for _ in range(0, n) {
vertex_degree = push(vertex_degree, 0)
}
for edge in edge_list {
vertex_degree[edge[0] - 1] = vertex_degree[edge[0] - 1] + 1
vertex_degree[edge[1] - 1] = vertex_degree[edge[1] - 1] + 1
}
let neighbour_sum = []
for _ in range(0, n) {
neighbour_sum = push(neighbour_sum, 0)
}
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
neighbour_sum[u] = neighbour_sum[u] + vertex_degree[v]
neighbour_sum[v] = neighbour_sum[v] + vertex_degree[u]
}
let result = neighbour_sum |> map(|d| str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 3 5 5 5 0")
fn test_ddeg_neighbour_degree_sums() {
assert result == "3 5 5 5 0", "DDEG: got " + result
}BFS — Breadth-First Search
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: BFS — Breadth-First Search
# https://rosalind.info/problems/bfs/
#
# Given: A simple directed graph with n vertices in the edge list format.
# Return: An array D[1..n] where D[i] is the length of a shortest path from
# vertex 1 to vertex i, and -1 where i is unreachable.
let n = 6
let edge_list = [[4, 6], [6, 5], [4, 3], [3, 5], [2, 1], [1, 4]]
# Directed: each edge is added once, so 2 -> 1 does not make 2 reachable.
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in edge_list {
let u = edge[0] - 1
adjacent[u] = push(adjacent[u], edge[1] - 1)
}
let distance = []
for _ in range(0, n) {
distance = push(distance, -1)
}
distance[0] = 0
# The queue is a list plus a read cursor. Breadth-first order is what makes the
# first arrival at a vertex the shortest one, so a vertex is only ever assigned
# a distance once — the -1 test doubles as the visited check.
let queue = [0]
let queue_head = 0
while queue_head < len(queue) {
let current = queue[queue_head]
queue_head = queue_head + 1
for next in adjacent[current] {
if distance[next] == -1 {
distance[next] = distance[current] + 1
queue = push(queue, next)
}
}
}
let result = distance |> map(|d| str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 0 -1 2 1 3 2")
fn test_bfs_shortest_path_lengths() {
assert result == "0 -1 2 1 3 2", "BFS: got " + result
}CC — Connected Components
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: CC — Connected Components
# https://rosalind.info/problems/cc/
#
# Given: A simple graph with n vertices in the edge list format.
# Return: The number of connected components in the graph.
let n = 12
let edge_list = [
[1, 2], [1, 5], [5, 9], [5, 10], [9, 10],
[3, 4], [3, 7], [3, 8], [4, 8], [7, 11],
[8, 11], [11, 12], [8, 12],
]
# Undirected, so every edge goes in both directions. Vertex 6 appears in no
# edge and is still a component of its own, which is why the sweep below starts
# from every vertex rather than from the endpoints of the edge list.
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
adjacent[v] = push(adjacent[v], u)
}
let seen = []
for _ in range(0, n) {
seen = push(seen, false)
}
let components = 0
for start in range(0, n) {
if seen[start] == false {
components = components + 1
# Flood the whole component from this vertex before moving on.
let stack = [start]
seen[start] = true
while len(stack) > 0 {
let current = stack[len(stack) - 1]
stack = slice(stack, 0, len(stack) - 1)
for next in adjacent[current] {
if seen[next] == false {
seen[next] = true
stack = push(stack, next)
}
}
}
}
}
println("Result: " + str(components))
println("Expected: 3")
fn test_cc_component_count() {
assert components == 3, "CC: got " + str(components)
}BIP — Testing Bipartiteness
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: BIP — Testing Bipartiteness
# https://rosalind.info/problems/bip/
#
# Given: A positive integer k and k simple graphs in the edge list format.
# Return: For each graph, 1 if it is bipartite and -1 otherwise.
let graphs = [
{ vertices: 3, edges: [[1, 2], [3, 2], [3, 1]] },
{ vertices: 4, edges: [[1, 4], [3, 1], [1, 2]] },
]
# Two-colour by breadth-first search. A graph is bipartite exactly when this
# never has to give a vertex the colour its neighbour already has, so the odd
# cycle in the first graph — the triangle — is what forces the -1.
fn is_bipartite(graph) {
let n = graph.vertices
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in graph.edges {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
adjacent[v] = push(adjacent[v], u)
}
let colour = []
for _ in range(0, n) {
colour = push(colour, -1)
}
let consistent = true
# The graph need not be connected, so every uncoloured vertex starts a sweep.
for start in range(0, n) {
if colour[start] == -1 {
colour[start] = 0
let queue = [start]
let head = 0
while head < len(queue) {
let current = queue[head]
head = head + 1
for next in adjacent[current] {
if colour[next] == -1 {
colour[next] = 1 - colour[current]
queue = push(queue, next)
} else {
if colour[next] == colour[current] {
consistent = false
}
}
}
}
}
}
if consistent then 1 else -1
}
let result = graphs |> map(|g| str(is_bipartite(g))) |> join(" ")
println("Result: " + result)
println("Expected: -1 1")
fn test_bip_detects_odd_cycles() {
assert result == "-1 1", "BIP: got " + result
}DAG — Testing Acyclicity
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: DAG — Testing Acyclicity
# https://rosalind.info/problems/dag/
#
# Given: A positive integer k and k simple directed graphs in the edge list format.
# Return: For each graph, 1 if the graph is acyclic and -1 otherwise.
let graphs = [
{ vertices: 2, edges: [[1, 2]] },
{ vertices: 4, edges: [[4, 1], [1, 2], [2, 3], [3, 1]] },
{ vertices: 4, edges: [[4, 3], [3, 2], [2, 1]] },
]
# Kahn's algorithm, used as a test rather than to produce an order: repeatedly
# remove a vertex with no remaining incoming edge. Anything left over lies on a
# cycle, because every vertex in it keeps an incoming edge from the vertex
# before it. The second graph leaves 1, 2 and 3 behind.
fn is_acyclic(graph) {
let n = graph.vertices
let adjacent = []
let indegree = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
indegree = push(indegree, 0)
}
for edge in graph.edges {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
indegree[v] = indegree[v] + 1
}
let queue = []
for v in range(0, n) {
if indegree[v] == 0 {
queue = push(queue, v)
}
}
let removed = 0
let head = 0
while head < len(queue) {
let current = queue[head]
head = head + 1
removed = removed + 1
for next in adjacent[current] {
indegree[next] = indegree[next] - 1
if indegree[next] == 0 {
queue = push(queue, next)
}
}
}
if removed == n then 1 else -1
}
let result = graphs |> map(|g| str(is_acyclic(g))) |> join(" ")
println("Result: " + result)
println("Expected: 1 -1 1")
fn test_dag_detects_cycles() {
assert result == "1 -1 1", "DAG: got " + result
}DIJ — Dijkstra's Algorithm
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: DIJ — Dijkstra's Algorithm
# https://rosalind.info/problems/dij/
#
# Given: A simple directed graph with positive edge weights and n vertices in
# the edge list format.
# Return: An array D[1..n] of shortest path lengths from vertex 1, with -1 where
# a vertex is unreachable.
let n = 6
let edge_list = [
[3, 4, 4], [1, 2, 4], [1, 3, 2], [2, 3, 3], [6, 3, 2],
[3, 5, 5], [5, 4, 1], [3, 2, 1], [2, 4, 2], [2, 5, 3],
]
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in edge_list {
let u = edge[0] - 1
adjacent[u] = push(adjacent[u], [edge[1] - 1, edge[2]])
}
# Scanning for the nearest unsettled vertex rather than using a priority queue:
# quadratic, and clearer. Positive weights are what make the greedy choice safe
# — once a vertex is settled no later path can improve it.
let infinity = 1000000000
let distance = []
let settled = []
for _ in range(0, n) {
distance = push(distance, infinity)
settled = push(settled, false)
}
distance[0] = 0
let step = 0
while step < n {
let nearest = -1
for v in range(0, n) {
if settled[v] == false and distance[v] < infinity {
if nearest == -1 or distance[v] < distance[nearest] {
nearest = v
}
}
}
if nearest == -1 {
step = n
} else {
settled[nearest] = true
for link in adjacent[nearest] {
let next = link[0]
let weight = link[1]
if distance[nearest] + weight < distance[next] {
distance[next] = distance[nearest] + weight
}
}
step = step + 1
}
}
let result = distance |> map(|d| if d == infinity then "-1" else str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 0 3 2 5 6 -1")
fn test_dij_shortest_paths() {
assert result == "0 3 2 5 6 -1", "DIJ: got " + result
}SQ — Square in a Graph
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: SQ — Square in a Graph
# https://rosalind.info/problems/sq/
#
# Given: A positive integer k and k simple undirected graphs in the edge list format.
# Return: For each graph, 1 if it contains a simple cycle of length 4, and -1 otherwise.
let graphs = [
{ vertices: 4, edges: [[3, 4], [4, 2], [3, 2], [3, 1], [1, 2]] },
{ vertices: 4, edges: [[1, 2], [3, 4], [2, 4], [4, 1]] },
]
# A four-cycle is two vertices joined by two different paths of length two, so
# the question is whether any pair of vertices has two neighbours in common.
# Searching for the cycle directly would mean trying orderings; counting shared
# neighbours needs one pass over the pairs.
fn has_square(graph) {
let n = graph.vertices
let neighbours = []
for _ in range(0, n) {
neighbours = push(neighbours, [])
}
for edge in graph.edges {
let u = edge[0] - 1
let v = edge[1] - 1
neighbours[u] = push(neighbours[u], v)
neighbours[v] = push(neighbours[v], u)
}
let found = false
let u = 0
while u < n and found == false {
let v = u + 1
while v < n and found == false {
let shared = 0
for candidate in neighbours[u] {
if contains(neighbours[v], candidate) {
shared = shared + 1
}
}
if shared >= 2 {
found = true
}
v = v + 1
}
u = u + 1
}
if found then 1 else -1
}
let result = graphs |> map(|g| str(has_square(g))) |> join(" ")
println("Result: " + result)
println("Expected: 1 -1")
fn test_sq_finds_four_cycles() {
assert result == "1 -1", "SQ: got " + result
}BF — Bellman-Ford Algorithm
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: BF — Bellman-Ford Algorithm
# https://rosalind.info/problems/bf/
#
# Given: A simple directed graph with integer edge weights (possibly negative)
# and n vertices in the edge list format.
# Return: An array D[1..n] of shortest path lengths from vertex 1, with "x"
# where a vertex is unreachable.
let n = 9
let edge_list = [
[1, 2, 10], [3, 2, 1], [3, 4, 1], [4, 5, 3], [5, 6, -1],
[7, 6, -1], [8, 7, 1], [1, 8, 8], [7, 2, -4], [2, 6, 2],
[6, 3, -2], [9, 5, -10], [9, 4, 7],
]
# Dijkstra cannot be used here: a negative edge can improve a vertex after it
# has been settled. Bellman-Ford instead relaxes every edge n-1 times, which is
# enough because a shortest path visits at most n vertices.
let infinity = 1000000000
let distance = []
for _ in range(0, n) {
distance = push(distance, infinity)
}
distance[0] = 0
let sweep = 0
while sweep < n - 1 {
let changed = false
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
let weight = edge[2]
if distance[u] < infinity and distance[u] + weight < distance[v] {
distance[v] = distance[u] + weight
changed = true
}
}
# Nothing improved, so nothing will: the remaining rounds cannot change it.
if changed == false then sweep = n
sweep = sweep + 1
}
let result = distance |> map(|d| if d == infinity then "x" else str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 0 5 5 6 9 7 9 8 x")
fn test_bf_handles_negative_weights() {
assert result == "0 5 5 6 9 7 9 8 x", "BF: got " + result
}CTE — Shortest Cycle Through a Given Edge
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: CTE — Shortest Cycle Through a Given Edge
# https://rosalind.info/problems/cte/
#
# Given: A positive integer k and k simple directed graphs with positive edge
# weights, each with a first specified edge.
# Return: For each graph, the length of a shortest cycle through the first edge,
# or -1 if there is none.
let graphs = [
{ vertices: 4, edges: [[2, 4, 2], [3, 2, 1], [1, 4, 3], [2, 1, 10], [1, 3, 4]] },
{ vertices: 4, edges: [[3, 2, 1], [2, 4, 2], [4, 1, 3], [2, 1, 10], [1, 3, 4]] },
]
# A cycle through the edge u -> v is that edge plus a shortest path from v back
# to u, so the whole problem reduces to one Dijkstra run from v. Weights are
# positive here, which is what lets Dijkstra be used rather than Bellman-Ford.
let infinity = 1000000000
fn shortest_path(graph, source, target) {
let n = graph.vertices
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in graph.edges {
adjacent[edge[0] - 1] = push(adjacent[edge[0] - 1], [edge[1] - 1, edge[2]])
}
let distance = []
let settled = []
for _ in range(0, n) {
distance = push(distance, infinity)
settled = push(settled, false)
}
distance[source] = 0
let remaining = n
while remaining > 0 {
let nearest = -1
for v in range(0, n) {
if settled[v] == false and distance[v] < infinity {
if nearest == -1 or distance[v] < distance[nearest] {
nearest = v
}
}
}
if nearest == -1 {
remaining = 0
} else {
settled[nearest] = true
for link in adjacent[nearest] {
if distance[nearest] + link[1] < distance[link[0]] {
distance[link[0]] = distance[nearest] + link[1]
}
}
remaining = remaining - 1
}
}
distance[target]
}
fn shortest_cycle(graph) {
let first = graph.edges[0]
let back = shortest_path(graph, first[1] - 1, first[0] - 1)
if back == infinity then -1 else back + first[2]
}
let result = graphs |> map(|g| str(shortest_cycle(g))) |> join(" ")
println("Result: " + result)
println("Expected: -1 10")
fn test_cte_shortest_cycle_through_an_edge() {
assert result == "-1 10", "CTE: got " + result
}TS — Topological Sorting
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Any order with every edge pointing forwards is accepted, so that property is asserted rather than the sample text.
# Rosalind: TS — Topological Sorting
# https://rosalind.info/problems/ts/
#
# Given: A simple directed acyclic graph with n vertices in the edge list format.
# Return: A topological sorting of the graph.
let n = 4
let edge_list = [[1, 2], [3, 1], [3, 2], [4, 3], [4, 2]]
# Kahn's algorithm, the same sweep DAG uses to test for cycles — here the order
# in which vertices come off the queue is the answer rather than a by-product.
let adjacent = []
let indegree = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
indegree = push(indegree, 0)
}
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
indegree[v] = indegree[v] + 1
}
let order = []
for v in range(0, n) {
if indegree[v] == 0 {
order = push(order, v)
}
}
let queue_head = 0
while queue_head < len(order) {
let current = order[queue_head]
queue_head = queue_head + 1
for next in adjacent[current] {
indegree[next] = indegree[next] - 1
if indegree[next] == 0 {
order = push(order, next)
}
}
}
let result = order |> map(|v| str(v + 1)) |> join(" ")
# Any order with every edge pointing forwards is accepted. Taking the lowest
# numbered ready vertex first happens to reproduce the sample here.
let position = []
for _ in range(0, n) {
position = push(position, 0)
}
for i in range(0, len(order)) {
position[order[i]] = i
}
let backwards = edge_list |> filter(|e| position[e[0] - 1] >= position[e[1] - 1])
println("Result: " + result)
println("Expected: 4 3 1 2 (any valid order is accepted)")
fn test_ts_orders_every_edge_forwards() {
assert len(order) == n, "TS: expected " + str(n) + " vertices, got " + str(len(order))
assert len(backwards) == 0, "TS: these edges point backwards: " + str(backwards)
}HDAG — Hamiltonian Path in DAG
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Hard in general, easy on a DAG: a Hamiltonian path exists exactly when consecutive vertices of the topological order are joined by an edge.
# Rosalind: HDAG — Hamiltonian Path in DAG
# https://rosalind.info/problems/hdag/
#
# Given: A positive integer k and k simple directed acyclic graphs in the edge
# list format.
# Return: For each graph, "1" followed by a Hamiltonian path if one exists, and
# "-1" otherwise.
let graphs = [
{ vertices: 3, edges: [[1, 2], [2, 3], [1, 3]] },
{ vertices: 4, edges: [[4, 3], [3, 2], [4, 1]] },
]
# Finding a Hamiltonian path is hard in general and easy on a DAG, which is why
# the problem restricts to one. A DAG has a Hamiltonian path exactly when its
# topological order is unique, and that holds exactly when consecutive vertices
# in the order are joined by an edge. So: sort topologically, then check the
# n-1 consecutive pairs.
fn hamiltonian_path(graph) {
let n = graph.vertices
let adjacent = []
let indegree = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
indegree = push(indegree, 0)
}
for edge in graph.edges {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
indegree[v] = indegree[v] + 1
}
let order = []
for v in range(0, n) {
if indegree[v] == 0 {
order = push(order, v)
}
}
let head = 0
while head < len(order) {
let current = order[head]
head = head + 1
for next in adjacent[current] {
indegree[next] = indegree[next] - 1
if indegree[next] == 0 {
order = push(order, next)
}
}
}
let joined = true
for i in range(0, len(order) - 1) {
if contains(adjacent[order[i]], order[i + 1]) == false {
joined = false
}
}
if joined {
"1 " + (order |> map(|v| str(v + 1)) |> join(" "))
} else {
"-1"
}
}
let answers = graphs |> map(|g| hamiltonian_path(g))
let result = answers |> join(" / ")
println("Result: " + result)
println("Expected: 1 1 2 3 / -1")
fn test_hdag_finds_hamiltonian_paths() {
assert answers[0] == "1 1 2 3", "HDAG[1]: got " + answers[0]
assert answers[1] == "-1", "HDAG[2]: got " + answers[1]
}NWC — Negative Weight Cycle
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Every distance starts at 0, not just vertex 1, so a cycle unreachable from vertex 1 is still found.
# Rosalind: NWC — Negative Weight Cycle
# https://rosalind.info/problems/nwc/
#
# Given: A positive integer k and k simple directed graphs with integer edge
# weights in the edge list format.
# Return: For each graph, 1 if it contains a negative weight cycle, -1 otherwise.
let graphs = [
{ vertices: 4, edges: [[1, 4, 4], [4, 2, 3], [2, 3, 1], [3, 1, 6], [2, 1, -7]] },
{ vertices: 3, edges: [[1, 2, -8], [2, 3, 20], [3, 1, -1], [3, 2, -30]] },
]
# Bellman-Ford's other use. After n-1 rounds of relaxation every shortest path
# is final, so an edge that still improves on round n can only be doing it by
# going round a negative cycle. Every distance starts at 0 rather than only
# vertex 1, which is the same as adding a source joined to every vertex by a
# zero-weight edge: the cycle need not be reachable from vertex 1.
fn has_negative_cycle(graph) {
let n = graph.vertices
let distance = []
for _ in range(0, n) {
distance = push(distance, 0)
}
let sweep = 0
while sweep < n - 1 {
for edge in graph.edges {
let u = edge[0] - 1
let v = edge[1] - 1
if distance[u] + edge[2] < distance[v] {
distance[v] = distance[u] + edge[2]
}
}
sweep = sweep + 1
}
let improved = false
for edge in graph.edges {
if distance[edge[0] - 1] + edge[2] < distance[edge[1] - 1] {
improved = true
}
}
if improved then 1 else -1
}
let result = graphs |> map(|g| str(has_negative_cycle(g))) |> join(" ")
println("Result: " + result)
println("Expected: -1 1")
fn test_nwc_detects_negative_cycles() {
assert result == "-1 1", "NWC: got " + result
}SCC — Strongly Connected Components
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Kosaraju, both passes iterative: a recursive depth-first search reads better but its depth is the length of a path, and the track allows 10^3 vertices.
# Rosalind: SCC — Strongly Connected Components
# https://rosalind.info/problems/scc/
#
# Given: A simple directed graph with n vertices in the edge list format.
# Return: The number of strongly connected components in the graph.
let n = 6
let edge_list = [[4, 1], [1, 2], [2, 4], [5, 6], [3, 2], [5, 3], [3, 5]]
# Kosaraju's algorithm. Two passes: the first records the order in which
# vertices finish, the second walks the reversed graph taking vertices in the
# reverse of that order. Every tree of the second pass is exactly one component,
# because finishing last means nothing outside the component can reach back in.
#
# Both passes are iterative. A recursive depth-first search reads better but its
# depth is the length of a path, and this pack's problems allow 10^3 vertices.
let adjacent = []
let reversed = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
reversed = push(reversed, [])
}
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
reversed[v] = push(reversed[v], u)
}
# Pass one: push each vertex after every edge out of it has been followed.
let visited = []
for _ in range(0, n) {
visited = push(visited, false)
}
let finish_order = []
for start in range(0, n) {
if visited[start] == false {
visited[start] = true
let stack = [[start, 0]]
while len(stack) > 0 {
let top = stack[len(stack) - 1]
let vertex = top[0]
let next_child = top[1]
if next_child < len(adjacent[vertex]) {
stack[len(stack) - 1] = [vertex, next_child + 1]
let child = adjacent[vertex][next_child]
if visited[child] == false {
visited[child] = true
stack = push(stack, [child, 0])
}
} else {
finish_order = push(finish_order, vertex)
stack = slice(stack, 0, len(stack) - 1)
}
}
}
}
# Pass two: walk the reversed graph, latest finisher first.
let component = []
for _ in range(0, n) {
component = push(component, -1)
}
let components = 0
let position = len(finish_order) - 1
while position >= 0 {
let start = finish_order[position]
if component[start] == -1 {
component[start] = components
let stack = [start]
while len(stack) > 0 {
let current = stack[len(stack) - 1]
stack = slice(stack, 0, len(stack) - 1)
for previous in reversed[current] {
if component[previous] == -1 {
component[previous] = components
stack = push(stack, previous)
}
}
}
components = components + 1
}
position = position - 1
}
println("Result: " + str(components))
println("Expected: 3")
println("Membership (vertex -> component): " + str(component))
fn test_scc_component_count() {
assert components == 3, "SCC: got " + str(components)
# 1, 2 and 4 lie on a cycle, as do 3 and 5; 6 is on its own.
assert component[0] == component[1], "SCC: 1 and 2 should share a component"
assert component[0] == component[3], "SCC: 1 and 4 should share a component"
assert component[2] == component[4], "SCC: 3 and 5 should share a component"
assert component[5] != component[4], "SCC: 6 should be on its own"
}2SAT — 2-Satisfiability
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
The hardest problem in the track and the one that pays off the rest: the implication graph is solved with the same Kosaraju pass SCC uses. Answers are checked by substituting them back into the formula, since any satisfying assignment is accepted.
# Rosalind: 2SAT — 2-Satisfiability
# https://rosalind.info/problems/2sat/
#
# Given: A positive integer k and k 2SAT formulas, each a list of two-literal
# clauses over n variables, where -3 means "not x3".
# Return: For each formula, 0 if it cannot be satisfied, or 1 followed by a
# satisfying assignment.
let formulas = [
{ variables: 2, clauses: [[1, 2], [-1, 2], [1, -2], [-1, -2]] },
{ variables: 3, clauses: [[1, 2], [2, 3], [-1, -2], [-2, -3]] },
]
# Two literals per clause is what makes this tractable where 3SAT is not. A
# clause (a or b) is the pair of implications "not a => b" and "not b => a", so
# a formula is a directed graph on the 2n literals. It is unsatisfiable exactly
# when some variable and its negation are strongly connected — that would say
# each implies the other.
#
# The assignment falls out of the same components. Kosaraju numbers them in
# topological order, so making each variable agree with whichever of its two
# literals is numbered higher never points an implication from a true literal to
# a false one, which is what satisfies every clause at once.
# Literal l becomes a node: x_i is 2(i-1) and its negation 2(i-1)+1.
fn literal_node(literal) {
if literal > 0 {
2 * (literal - 1)
} else {
2 * (0 - literal - 1) + 1
}
}
fn negate_node(node) {
if node % 2 == 0 then node + 1 else node - 1
}
fn strong_components(size, links) {
let adjacent = []
let reversed = []
for _ in range(0, size) {
adjacent = push(adjacent, [])
reversed = push(reversed, [])
}
for link in links {
adjacent[link[0]] = push(adjacent[link[0]], link[1])
reversed[link[1]] = push(reversed[link[1]], link[0])
}
let visited = []
for _ in range(0, size) {
visited = push(visited, false)
}
let finish_order = []
for start in range(0, size) {
if visited[start] == false {
visited[start] = true
let stack = [[start, 0]]
while len(stack) > 0 {
let top = stack[len(stack) - 1]
let vertex = top[0]
let next_child = top[1]
if next_child < len(adjacent[vertex]) {
stack[len(stack) - 1] = [vertex, next_child + 1]
let child = adjacent[vertex][next_child]
if visited[child] == false {
visited[child] = true
stack = push(stack, [child, 0])
}
} else {
finish_order = push(finish_order, vertex)
stack = slice(stack, 0, len(stack) - 1)
}
}
}
}
let component = []
for _ in range(0, size) {
component = push(component, -1)
}
let count = 0
let position = size - 1
while position >= 0 {
let start = finish_order[position]
if component[start] == -1 {
component[start] = count
let stack = [start]
while len(stack) > 0 {
let current = stack[len(stack) - 1]
stack = slice(stack, 0, len(stack) - 1)
for previous in reversed[current] {
if component[previous] == -1 {
component[previous] = count
stack = push(stack, previous)
}
}
}
count = count + 1
}
position = position - 1
}
component
}
fn solve(formula) {
let n = formula.variables
let size = 2 * n
let links = []
for clause in formula.clauses {
let a = literal_node(clause[0])
let b = literal_node(clause[1])
links = push(links, [negate_node(a), b])
links = push(links, [negate_node(b), a])
}
let component = strong_components(size, links)
let satisfiable = true
for i in range(0, n) {
if component[2 * i] == component[2 * i + 1] {
satisfiable = false
}
}
if satisfiable == false {
"0"
} else {
let assignment = []
for i in range(0, n) {
# The literal in the later component is the one to make true.
if component[2 * i] > component[2 * i + 1] {
assignment = push(assignment, i + 1)
} else {
assignment = push(assignment, 0 - (i + 1))
}
}
"1 " + (assignment |> map(|v| str(v)) |> join(" "))
}
}
# Any satisfying assignment is accepted, so the answers are checked by putting
# them back into the formula rather than against the sample text.
fn satisfies(formula, answer) {
if answer == "0" {
true
} else {
let parts = answer |> split(" ")
let values = slice(parts, 1, len(parts)) |> map(|t| int(t))
let unmet = formula.clauses |> filter(|clause| {
let first = contains(values, clause[0])
let second = contains(values, clause[1])
first == false and second == false
})
len(unmet) == 0
}
}
let answers = formulas |> map(|f| solve(f))
let verdicts = range(0, len(formulas)) |> map(|i| satisfies(formulas[i], answers[i]))
for i in range(0, len(formulas)) {
println("Formula " + str(i + 1) + ": " + answers[i] + " satisfied: " + str(verdicts[i]))
}
println("Sample output: 0 / 1 1 -2 3")
fn test_2sat_solves_and_refutes() {
assert answers[0] == "0", "2SAT[1]: this formula is unsatisfiable, got " + answers[0]
assert verdicts == [true, true], "2SAT: an answer does not satisfy its formula: " + str(verdicts)
assert substr(answers[1], 0, 1) == "1", "2SAT[2]: expected a satisfying assignment, got " + answers[1]
}GS — General Sink
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: GS — General Sink
# https://rosalind.info/problems/gs/
#
# Given: A positive integer k and k simple directed graphs in the edge list format.
# Return: For each graph, a vertex from which all other vertices are reachable,
# or -1 if there is none.
let graphs = [
{ vertices: 3, edges: [[3, 2], [2, 1]] },
{ vertices: 3, edges: [[3, 2], [1, 2]] },
]
# Reachability from each vertex in turn. At this size that is the clear way to
# say it; the linear answer condenses the strongly connected components and
# checks whether the single source of the condensation reaches everything, which
# is the same test done once instead of n times.
fn reachable_from(adjacent, start, n) {
let seen = []
for _ in range(0, n) {
seen = push(seen, false)
}
seen[start] = true
let stack = [start]
let reached = 1
while len(stack) > 0 {
let current = stack[len(stack) - 1]
stack = slice(stack, 0, len(stack) - 1)
for next in adjacent[current] {
if seen[next] == false {
seen[next] = true
reached = reached + 1
stack = push(stack, next)
}
}
}
reached
}
fn general_sink(graph) {
let n = graph.vertices
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in graph.edges {
adjacent[edge[0] - 1] = push(adjacent[edge[0] - 1], edge[1] - 1)
}
let answer = -1
for v in range(0, n) {
if answer == -1 and reachable_from(adjacent, v, n) == n {
answer = v + 1
}
}
answer
}
let result = graphs |> map(|g| str(general_sink(g))) |> join(" ")
println("Result: " + result)
println("Expected: 3 -1")
fn test_gs_finds_the_source_vertex() {
assert result == "3 -1", "GS: got " + result
}SC — Semi-Connected Graph
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: SC — Semi-Connected Graph
# https://rosalind.info/problems/sc/
#
# Given: A positive integer k and k simple directed graphs in the edge list format.
# Return: For each graph, 1 if the graph is semi-connected and -1 otherwise.
let graphs = [
{ vertices: 3, edges: [[3, 2], [2, 1]] },
{ vertices: 3, edges: [[3, 2], [1, 2]] },
]
# Semi-connected means every pair of vertices is comparable: one of the two
# reaches the other. The second graph fails on the pair 1 and 3 — both reach 2
# and neither reaches the other. Reachability is computed from every vertex and
# the pairs are then checked directly, which says the definition out loud.
fn reachable_set(adjacent, start, n) {
let seen = []
for _ in range(0, n) {
seen = push(seen, false)
}
seen[start] = true
let stack = [start]
while len(stack) > 0 {
let current = stack[len(stack) - 1]
stack = slice(stack, 0, len(stack) - 1)
for next in adjacent[current] {
if seen[next] == false {
seen[next] = true
stack = push(stack, next)
}
}
}
seen
}
fn is_semi_connected(graph) {
let n = graph.vertices
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in graph.edges {
adjacent[edge[0] - 1] = push(adjacent[edge[0] - 1], edge[1] - 1)
}
let reaches = []
for v in range(0, n) {
reaches = push(reaches, reachable_set(adjacent, v, n))
}
let comparable = true
for u in range(0, n) {
for v in range(u + 1, n) {
if reaches[u][v] == false and reaches[v][u] == false {
comparable = false
}
}
}
if comparable then 1 else -1
}
let result = graphs |> map(|g| str(is_semi_connected(g))) |> join(" ")
println("Result: " + result)
println("Expected: 1 -1")
fn test_sc_checks_every_pair() {
assert result == "1 -1", "SC: got " + result
}SDAG — Shortest Paths in DAG
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Relaxing once in topological order is linear, where Bellman-Ford needs n-1 rounds; acyclicity is what buys that.
# Rosalind: SDAG — Shortest Paths in DAG
# https://rosalind.info/problems/sdag/
#
# Given: A weighted DAG with integer edge weights and n vertices in the edge
# list format.
# Return: An array D[1..n] of shortest path lengths from vertex 1, with "x"
# where a vertex is unreachable.
let n = 5
let edge_list = [[2, 3, 4], [4, 3, -2], [1, 4, 1], [1, 5, -3], [2, 4, -2], [5, 4, 1]]
# Weights can be negative, so Dijkstra is out; but the graph is acyclic, so
# Bellman-Ford's n-1 rounds are unnecessary. Relaxing the edges once in
# topological order is enough, because a vertex is only ever reached from
# vertices that come before it. That makes this linear where BF is quadratic.
let adjacent = []
let indegree = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
indegree = push(indegree, 0)
}
for edge in edge_list {
adjacent[edge[0] - 1] = push(adjacent[edge[0] - 1], [edge[1] - 1, edge[2]])
indegree[edge[1] - 1] = indegree[edge[1] - 1] + 1
}
let order = []
for v in range(0, n) {
if indegree[v] == 0 {
order = push(order, v)
}
}
let queue_head = 0
while queue_head < len(order) {
let current = order[queue_head]
queue_head = queue_head + 1
for link in adjacent[current] {
indegree[link[0]] = indegree[link[0]] - 1
if indegree[link[0]] == 0 {
order = push(order, link[0])
}
}
}
let infinity = 1000000000
let distance = []
for _ in range(0, n) {
distance = push(distance, infinity)
}
distance[0] = 0
for v in order {
if distance[v] < infinity {
for link in adjacent[v] {
if distance[v] + link[1] < distance[link[0]] {
distance[link[0]] = distance[v] + link[1]
}
}
}
}
let result = distance |> map(|d| if d == infinity then "x" else str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 0 x -4 -2 -3")
fn test_sdag_shortest_paths() {
assert result == "0 x -4 -2 -3", "SDAG: got " + result
}