0.5.0

(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
```

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow