Julia Language while Loops Breadth-first search

(Although this example is written using syntax introduced in version v0.5, it can work with few modifications on older versions also.)

This implementation of breadth-first search (BFS) on a graph represented with adjacency lists uses while loops and the return statement. The task we will solve is as follows: we have a sequence of people, and a sequence of friendships (friendships are mutual). We want to determine the degree of the connection between two people. That is, if two people are friends, we will return 1; if one is a friend of a friend of the other, we will return 2, and so on.

First, let’s assume we already have an adjacency list: a Dict mapping T to Array{T, 1}, where the keys are people and the values are all the friends of that person. Here we can represent people with whatever type T we choose; in this example, we will use Symbol. In the BFS algorithm, we keep a queue of people to “visit”, and mark their distance from the origin node.

function degree(adjlist, source, dest)
    distances = Dict(source => 0)
    queue = [source]

    # until the queue is empty, get elements and inspect their neighbours
    while !isempty(queue)
        # shift the first element off the queue
        current = shift!(queue)

        # base case: if this is the destination, just return the distance
        if current == dest
            return distances[dest]
        end

        # go through all the neighbours
        for neighbour in adjlist[current]
            # if their distance is not already known...
            if !haskey(distances, neighbour)
                # then set the distance
                distances[neighbour] = distances[current] + 1

                # and put into queue for later inspection
                push!(queue, neighbour)
            end
        end
    end

    # we could not find a valid path
    error("$source and $dest are not connected.")
end

Now, we will write a function to build an adjacency list given a sequence of people, and a sequence of (person, person) tuples:

function makeadjlist(people, friendships)
    # dictionary comprehension (with generator expression)
    result = Dict(p => eltype(people)[] for p in people)

    # deconstructing for; friendship is mutual
    for (a, b) in friendships
        push!(result[a], b)
        push!(result[b], a)
    end

    result
end

We can now define the original function:

degree(people, friendships, source, dest) =
    degree(makeadjlist(people, friendships), source, dest)

Now let’s test our function on some data.

const people = [:jean, :javert, :cosette, :gavroche, :éponine, :marius]
const friendships = [
    (:jean, :cosette),
    (:jean, :marius),
    (:cosette, :éponine),
    (:cosette, :marius),
    (:gavroche, :éponine)
]

Jean is connected to himself in 0 steps:

julia> degree(people, friendships, :jean, :jean)
0

Jean and Cosette are friends, and so have degree 1:

julia> degree(people, friendships, :jean, :cosette)
1

Jean and Gavroche are connected indirectly through Cosette and then Marius, so their degree is 3:

julia> degree(people, friendships, :jean, :gavroche)
3

Javert and Marius are not connected through any chain, so an error is raised:

julia> degree(people, friendships, :javert, :marius)
ERROR: javert and marius are not connected.
 in degree(::Dict{Symbol,Array{Symbol,1}}, ::Symbol, ::Symbol) at ./REPL[28]:27
 in degree(::Array{Symbol,1}, ::Array{Tuple{Symbol,Symbol},1}, ::Symbol, ::Symbol) at ./REPL[30]:1