Hello!
I have been recently trying to improve the performance of the classic brute force algorithm for k-centers in a simple graph. My reasons for this are not really that serious, I was only trying to reach the speed of C++ using the same algorithm or see how close I could get.
The definition of problem goes like this: for a given simple graph G, with weighted edges find k vertices K such that the maximum length of the shortest path from a vertex in G to any vertex in K is as short as possible.
For example imagine trying to build k shops on a grid of n lots so that the customers living on those lots will be able to get to a shop as quickly as possible.
The algorithm that solves that and is implemented below does this by recursively going through all the possible combinations of vertices in set K of size k, rating them and then selecting the best one (the one with smallest distance to centers, that appears first).
using StaticArrays
#Input graph as a list - to conserve space
L = [[(2, 30), (29, 6), (95, 31), (100, 88)],[(1, 30), (3, 46)],[(2, 46), (4, 1), (79,57), (99, 49)],[(3, 1), (5, 28), (27, 27), (33, 45), (68, 28), (73, 41)],[(4, 28), (6, 31), (7, 8), (80, 90), (96, 87)],[(5, 31), (7, 69), (63, 83)],[(5, 8), (6, 69), (8, 39), (19, 9), (35, 7), (62, 55)],[(7, 39), (9, 14), (13, 77), (49, 96), (52, 31), (53, 66)],[(8, 14), (10, 84), (48, 92), (83, 75), (99, 28)],[(9, 84), (11, 59)],[(10, 59), (12, 10), (37, 4)],[(11, 10), (13, 28), (44, 56)],[(8, 77), (12, 28), (14, 63), (42, 3), (85, 22)],[(13, 63), (15, 9), (21, 82), (27, 48), (85, 90)],[(14, 9), (16, 100), (50,31), (69, 46)],[(15, 100), (17, 98), (38, 70), (79, 96)],[(16, 98), (18, 70), (54, 45), (58, 60)],[(17, 70),(19, 94), (38, 27), (75, 100)],[(7, 9), (18, 94), (20, 30), (60, 53), (92, 70)],[(19, 30), (21, 14), (93, 35)],[(14, 82), (20, 14), (22, 87), (39, 59), (81, 34)],[(21, 87),(23, 82), (52, 11), (75, 48)],[(22, 82), (24, 55)],[(23, 55), (25, 2), (59, 63)],[(24, 2), (26, 32), (99, 19)],[(25, 32), (27, 77), (29, 20), (32, 26)],[(4, 27), (14, 48), (26, 77), (28, 95), (50, 16), (60, 86)],[(27,95), (29, 29)],[(1, 6), (26, 20), (28, 29), (30, 59)],[(29, 59), (31, 91), (56, 76), (57, 37), (70, 74), (81, 99), (95, 96)],[(30, 91), (32, 89), (63, 82), (69, 53)],[(26, 26), (31, 89), (33, 50), (99, 35)],[(4, 45), (32, 50), (34, 40),(49, 77), (73, 88), (88, 8)],[(33, 40), (35, 88), (94, 52)],[(7, 7), (34, 88), (36, 94), (60, 5), (80, 46)],[(35, 94), (37, 60)],[(11, 4), (36, 60), (38, 21), (81, 14)],[(16, 70), (18, 27), (37, 21), (39, 89), (62, 56)],[(21, 59), (38, 89), (40, 47), (76, 89)],[(39, 47), (41, 63),(54, 52)],[(40, 63), (42, 45), (44, 80), (76, 42)],[(13, 3), (41, 45), (43, 46), (45, 68), (57, 5), (85, 34)],[(42, 46), (44, 24)],[(12, 56), (41, 80), (43, 24), (45, 77)],Tuple{Int64,Int64}[(42, 68), (44, 77), (46, 60), (59, 33), (68, 19)],[(45, 60), (47, 45)],[(46, 45), (48, 50), (58, 68)],[(9, 92), (47, 50), (49, 93), (98, 53)],[(8, 96), (33, 77), (48, 93), (50, 22)],[(15, 31), (27, 16), (49, 22), (51,84)],[(50, 84), (52, 16), (64, 89)],[(8, 31), (22, 11), (51, 16), (53, 85), (60, 34), (95, 96)],[(8, 66), (52, 85), (54, 68), (74, 50)],[(17, 45), (40, 52), (53, 68), (55, 93), (59, 75), (86, 35)],[(54, 93), (56, 37), (95, 47)],[(30, 76), (55, 37), (57, 26)],[(30, 37), (42, 5), (56, 26), (58, 29)],[(17, 60), (47, 68), (57, 29), (59, 38), (73, 37)],[(24, 63), (45, 33), (54, 75), (58, 38), (60, 10)],[(19, 53), (27, 86), (35, 5), (52, 34), (59, 10), (61, 32)],[(60, 32), (62, 67), (65, 73)],[(7, 55), (38, 56), (61, 67), (63, 66), (94, 96)],[(6, 83), (31, 82), (62, 66), (64, 52)],Tuple{Int64,Int64}[(51, 89), (63, 52), (65, 19)],[(61, 73), (64, 19), (66, 39), (94, 61)],[(65, 39), (67, 12), (97, 81)],[(66, 12), (68, 86)],[(4, 28), (45, 19), (67, 86), (69, 72)],[(15, 46), (31, 53), (68, 72), (70, 73), (85, 51)],[(30, 74), (69, 73), (71, 65)],[(70, 65), (72, 2)],[(71, 2), (73, 8)],[(4, 41), (33, 88), (58, 37), (72, 8), (74, 96)],[(53, 50), (73, 96), (75, 43)],[(18, 100), (22, 48), (74, 43), (76, 39), (91, 33)],[(39, 89), (41, 42), (75, 39), (77, 61), (91, 51)],[(76, 61), (78, 90)],[(77, 90), (79, 8), (91, 32)],[(3, 57), (16, 96), (78, 8), (80, 58)],[(5, 90), (35, 46), (79, 58), (81, 91), (91, 84)],[(21, 34), (30, 99), (37, 14), (80, 91), (82, 58), (95, 54)],[(81, 58), (83, 13)],[(9, 75),(82, 13), (84, 79)],[(83, 79), (85, 59)],[(13, 22), (14, 90), (42, 34), (69, 51), (84, 59), (86, 28)],[(54, 35), (85, 28), (87, 46)],[(86, 46), (88, 24), (91, 17)],[(33, 8), (87, 24), (89, 63)],[(88, 63), (90, 81)],[(89, 81), (91, 14), (94, 63), (95, 96)],[(75, 33), (76, 51), (78, 32), (80, 84), (87, 17), (90, 14), (92, 52)],[(19, 70), (91, 52), (93, 64)],[(20, 35), (92, 64), (94, 75)],[(34, 52), (62, 96), (65, 61), (90, 63), (93, 75), (95, 71)],[(1, 31), (30, 96), (52, 96), (55, 47), (81, 54), (90, 96), (94, 71), (96, 51)],[(5, 87), (95, 51), (97, 75)],[(66, 81), (96, 75), (98, 57)],[(48, 53), (97, 57), (99, 31)],[(3, 49), (9, 28), (25, 19), (32, 35), (98, 31), (100, 49)],[(1, 88), (99, 49)]]
#A Function to read this list.
function graphListToMatrix(L)
n = length(L)
G = zeros(Int, n, n)
for el in enumerate(L)
j, links = el
for link in links
G[link[1], j] = link[2]
end
end
return G
end
#A classic Floyd Warshall algorithm.
@inbounds function floydWarshall(G)
const n = size(G, 1)
D = copy(G)
for k = 1:n
for j = 1:(n - 1)
for i = (j + 1):n
if (D[i, k] != 0) & (D[j, k] != 0)
newDist = D[i, k] + D[j, k]
if D[i, j] == 0
D[i, j] = newDist
D[j, i] = newDist
else
if D[i, j] > newDist
D[i, j] = newDist
D[j, i] = newDist
end
end
end
end
end
end
return D
end
#The main function
@inbounds function findBestKCenters(G, k)
n = size(G, 1)
bestScore = typemax(Int)
bestChoice = MVector{k, Int}(zeros(k))
D = floydWarshall(G)
bestScore = useBruteForceRec(MVector{k, Int}(zeros( k)), D, 1, 1, k, n, bestScore, bestChoice)
return bestScore
end
#The recursive function
@inbounds function useBruteForceRec(vec, D, i, d, k, n, bestScore, bestChoice)
if d == (k + 1)
score = rateAChoice(D, vec)
if bestScore < score
bestScore = score
bestChoice = vec
end
else
for j = i:n
vec[d] = j
bestScore = useBruteForceRec(vec, D, i + 1, d + 1, k, n, bestScore, bestChoice)
end
end
return bestScore
end
#Function to evaluate a choice of center
@views @inbounds function rateAChoice(D, vec)
const n = size(D, 1)
score = 0
for j = 1:n
distanceToCenter = typemax(Int)
for i in vec
distanceToCenter = min(distanceToCenter, D[i, j])
end
score = max(score, distanceToCenter)
end
return score
end
#Benchmark
function repeatedTest(k, r)
t = 0
G = graphListToMatrix(L)
for j = 1:r
t += @elapsed findBestKCenters(G, k)
end
println("Average time: $(t/r)")
return t/r
end
repeatedTest(3, 5)
On my computer I get (2nd run and after that) arround 0.27 s.
Similar C++ code however runs 4x as fast.
If you happen to have any ideas on how to improve this code, please share them!
Those without special non-standard packages will be especially welcom!
The C++ code I’m comparing Julia with can be found here.
The same algorithm can be executed by
./main -i "samples/pmed/pmed1.txt" -f "pmed" -m "bf" -c 3