Analyzing a dependency graph in Swift

I published my solution to Dave Thomas’s Transitive Dependencies programming exercise, known as a kata, to GitHub:

The Challenge

This exercise involves analyzing a graph data structure which contains nodes that “depend on” other nodes. A graph is represented as direct dependencies between nodes:


The objective is to find all of a node’s dependencies, both direct and indirect, like so:


An interesting complication is that a graph might contain cyclical dependencies, where a node indirectly depends upon itself. A proper solution to this problem must be able to cope with a graph like this:


If this programming challenge interests you, stop reading now and solve the puzzle for yourself! Check out the kata for more information.

My Solution

My solution relies on three things:

  1. An instance of Swift’s Set<T> collection keeps track of which nodes have been visited.
  2. The higher-order function reduce accumulates nodes into a Set as they are visited.
  3. Recursion is used to visit dependencies from the reduce method’s combine logic.

Here’s how I solved this little puzzle:


You can download the Xcode project here.

This entry was posted in Swift and tagged , . Bookmark the permalink.

1 Response to Analyzing a dependency graph in Swift

  1. Pingback: Dew Drop – June 9, 2016 (#2268) | Morning Dew

Comments are closed.